No.194

$K$ が小さい ($K \leq 10^6$) 場合:

最初から順番に $F(k), S(k)$ を計算していく.

$$\begin{align} F(k) &= F(k - 1) + F(k - 2) + \dots + F(k - N) \\ &= F(k - 1) + F(k - 1) - F(k - N - 1) \\ &= 2F(k - 1) - F(k - N - 1) \end{align}$$

を使って計算量を減らす. 計算量は $O(N + K)$ である.

$K$ が大きい ($K \gt 10^6$) 場合:

$N$ が小さいので行列を使う.

$$\left( \begin{array}{c} F(k + N) \\ F(k + N - 1) \\ F(k + N - 2) \\ \vdots \\ F(k + 2) \\ F(k + 1) \end{array} \right) = \left( \begin{array}{ccccccc} 1 & 1 & 1 & \cdots & 1 & 1 & 1 \\ 1 & 0 & 0 & \cdots & 0 & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 & 0 \\ 0 & 0 & 0 & \cdots & 0 & 1 & 0 \\ \end{array} \right) \left( \begin{array}{c} F(k + N - 1) \\ F(k + N - 2) \\ F(k + N - 3) \\ \vdots \\ F(k + 1) \\ F(k) \end{array} \right)$$

となる. また $S(k)$ は

$$\begin{align} S(k) &= S(k - 1) + F(k) \\ &= S(k - 1) + F(k - 1) + F(k - 2) + \dots + F(k - N) \\ &= S(k - 1) + S(k - 1) - S(k - N - 1) \\ &= 2S(k - 1) - S(k - N - 1) \end{align}$$

となるので,

$$\left( \begin{array}{c} S(k + N + 1) \\ S(k + N) \\ S(k + N - 1) \\ \vdots \\ S(k + 2) \\ S(k + 1) \end{array} \right) = \left( \begin{array}{ccccccc} 2 & 0 & 0 & \cdots & 0 & 0 & -1 \\ 1 & 0 & 0 & \cdots & 0 & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 & 0 \\ 0 & 0 & 0 & \cdots & 0 & 1 & 0 \\ \end{array} \right) \left( \begin{array}{c} S(k + N) \\ S(k + N - 1) \\ S(k + N - 2) \\ \vdots \\ S(k + 1) \\ S(k) \end{array} \right)$$

となる. あとは No.147 と同様に計算すればいい. 計算量は $O(N^3 \log K)$ である.