「K ボナッチ数列」を解くために:part5 Scala編（paizaランク A 相当）

説明

前の問題では累積和を用いて N 項目を求める方法を紹介しました。
ここでは別の方法を紹介します。
前の問題と同様に、K ボナッチ数列の i 項目を KB_i とします。
N ≦ K の場合は K ボナッチ数列の定義より KB_N = 1 であるため、以下 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 を高速に求める方法を考えてみましょう。

問題

整数 K と N が与えられるので、 K ボナッチ数列の N 項目を 10000 で割ったあまりを求めてください。