愚直に毎回 \(A_i\) を求めると \(\mathrm{O}(NK)\) かかってしまい実行時間制限に間に合いません。

ここで、\(A_n\) を計算するときには \(S:=A_{n-K}+\ldots+A_{n-1}\) をデータとして保持することにして、\(S\) を適宜更新することを考えます。

まず、\(S=K\) で初期化します。次に、\(n=K,K+1,\ldots,N\) の順に以下を行います。

• \(A_n=S\) とする
• \(S\) から \(A_{n-K}\) を引く
• \(S\) に\(A_n\) を足す。

以上の手続きにより \(\mathrm{O}(N)\) で答えを求めることができます。実装例も参考にしてください。

実装例(Python):

n, k = map(int, input().split())
s = k
a = [1 for i in range(n + 1)]
for i in range(k, n + 1):
    a[i] = s
    s -= a[i-k]
    s += a[i]
    s %= 1000000000
print(a[n])