\(N \leq 10^4, K \leq 10^6\) のとき:

\[\begin{align} F(k) &= F(k-1) + F(k-2) + \cdots + F(k-N) \\ &= F(k-1) + F(k-1) - F(k-N-1) \\ &= 2F(k-1) - F(k-N-1) \\ \end{align}\]

とすれば \(O(K)\) で計算できる.

\(N \leq 30, K \leq 10^{12}\) のとき:

以下のような行列を使った形式で考える.

\[\begin{bmatrix} F(k-N+1) \\ F(k-N+2) \\ F(k-N+3) \\ \vdots \\ F(k-1) \\ F(k) \\ S(k) \end{bmatrix} = \begin{bmatrix} & 1 & & & & & 0 \\ & & 1 & & & & 0 \\ & & & \ddots & & & 0 \\ & & & & \ddots & & \vdots \\ & & & & & 1 & 0 \\ 1 & 1 & 1 & \cdots & 1 & 1 & 0 \\ 1 & 1 & 1 & \cdots & 1 & 1 & 1 \end{bmatrix} \begin{bmatrix} F(k-N) \\ F(k-N+1) \\ F(k-N+2) \\ \vdots \\ F(k-2) \\ F(k-1) \\ S(k-1) \end{bmatrix}\]

これで繰り返し2乗法を使えば \(O(N^3 \log K)\) で計算できる.