K ボナッチ数列

今回は paiza の「K ボナッチ数列」の問題に挑戦！

🧩 問題概要

• K ボナッチ数列とは
  • 1 ～ K 項目：すべて 1
  • K+1 項目以降：直前 K 項の和

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

• 入力
  • 整数 K
  • 整数 N
• 出力
  • K ボナッチ数列の N 項目
  • ただし 10000 で割ったあまり
• 制約条件
  • 1 ≤ K ≤ 100,000
  • K ≤ N ≤ 200,000

※ 単純に K 個ずつ足すと 計算量オーバー

入力例：

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]; // Kボナッチ数列
    const C = [0]; // 累積和
    
    for (let i = 1; i <= K; i++) {
        KB[i] = 1;
        C[i] = (C[i-1] + KB[i]) % MOD
    }
    
    for (let i = K+1; i <= N; i++) {
        KB[i] = (C[i-1] - C[i-K-1] + MOD) % MOD;
        C[i] = (C[i-1] + KB[i]) % MOD
    }
    
    console.log(KB[N]);
});

解法

• 定義

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

• これを 累積和 C で表す

C_i = KB_1 + KB_2 + ... + KB_i

• 区間和として書き換える

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

✅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]; // Kボナッチ数列
    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-1-K] + MOD) % MOD;
    }
    
    console.log(KB[N]);
});

解法

• 2つの式を比較する：

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

• 差を取ると

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

• 整理すると：

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

📝まとめ

「累積和（区間和）」 や 「差分による漸化式」を使うことで、K ボナッチ数列 の N 項目を高速に求めることができる！

注意点は、数が大きくなり過ぎないように毎回細かく % MOD をとること！