「K ボナッチ数列」を解くために:part5 KB_N を高速に求める方法（漸化式）

今回は paiza の「「K ボナッチ数列」を解くために:part5」の問題に挑戦！

🧩 問題概要

• K ボナッチ数列を考える問題
• 定義：
  • 1 項目〜 K 項目まではすべて 1
  • K+1 項目以降は直前 K 項の和
• 入力：
  • 整数 K
  • 整数 N
• 出力：
  • K ボナッチ数列の N 項目
  • ただし 10000 で割ったあまり
• 制約：
  • 1 ≦ K ≦ 100000
  • K ≦ N ≦ 200000

この問題では：

N > K の場合

KB_N = KB_{N-K} + KB_{N-K+1} + ... + KB_{N-2} + KB_{N-1} 
KB_{N-1} = KB_{N-K-1} + KB_{N-K} + KB_{N-K+1} + ... + KB_{N-2} 

この 2 つの式を用いて KB_N を高速に求める方法を考える。

入力例:

3
10

出力例:

105

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];
rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const K = Number(lines[0]);
    const N = Number(lines[1]);
    const MOD = 10000;
    
    const KB = [0];
    for (let i = 1; i <= K; i++) {
        KB[i] = 1;
    }
    KB[K+1] = K % MOD;
    
    for (let i = K+2; i <= N; i++) {
        KB[i] = (2 * KB[i-1] - KB[i-K-1] + MOD) % MOD;
    }
    
    console.log(KB[N])
});

💡式変形：

2つの式：

KB_N     = KB_{N-K}   + KB_{N-K+1} + ... + KB_{N-2} + KB_{N-1}
KB_{N-1} = KB_{N-K-1} + KB_{N-K}   + ... + KB_{N-2}

見比べると…

• 共通している部分
  • KB_{N-K} ～ KB_{N-2}
• 違う部分
  • KB_N には KB_{N-1} がある
  • KB_{N-1} には KB_{N-K-1} がある

差を取る（KB_N − KB_{N-1}）

KB_N - KB_{N-1} = (KB_{N-K} + ~ + KB_{N-2} + KB_{N-1}) 
                    - (KB_{N-K-1} + KB_{N-K} + ~ + KB{N-2})

共通部分が消える！

KB_N - KB_{N-1} = KB_{N-1} - KB_{N-K-1}

KB_N の形に整理する

移項：

KB_N = (KB_{N-1} - KB_{N-K-1}) + KB{N-1}

↓

KB_N = 2 * KB_{N-1} - KB_{N - K - 1} 

この漸化式を使って計算する！

🔍コードの流れ

入力の読み込み

• 標準入力から
  • K（何項和か）
  • N（求めたい項番号）
    剰余計算用に MOD = 10000 を用意

K ボナッチ数列の初期化

• 配列 KB を用意（1-indexed）
• 定義より
  • KB[1] ～ KB[K] = 1
• KB[K+1] = K
  （最初の K 個がすべて 1 なので、その和）

計算

• i = K+2 ～ N まで順に計算
• 次の式を使う：

KB[i] = 2 * KB[i-1] - KB[i-K-1]

• 引き算で負にならないように + MOD してから % MOD

出力

• KB[N] を出力
• すでに 10000 で割ったあまりになっている

📝まとめ

〇 計算の限界

• 毎回「直前 K 項の和」を計算すると
  • 計算量：O(N × K)
  • K, N が最大 10⁵〜20万では 間に合わない

〇 高速化のアイデア

• 連続する項の和には 共通部分が多い
• 2 つの式を並べる：

KB_N = KB_{N-K} + ... + KB_{N-2} + KB_{N-1}
KB_{N-1} = KB_{N-K-1} + KB_{N-K} + ... + KB_{N-2}

• 差を取ると共通部分が消える

〇 導かれる漸化式

KB_N = 2 × KB_{N-1} − KB_{N-K-1}

この式を使って計算することで、N 項目を高速に求めることが可能。

〇 実装上のポイント

• 初期値
  • KB[1] ~ KB[K] = 1
  • KB[K+1] = K
• 負の数対策
  • (a - b + MOD) % MOD
• 漸化式
  • KB[i] = 2 * KB[i-1] - KB[i-K-1]