Yukicoder No.720 行列のできるフィボナッチ数列道場 (2)
問題
No.720 行列のできるフィボナッチ数列道場 (2) - yukicoder
アルゴリズム
$$ s[n] = \sum_{i = 0}^{n} {F[i*m]} $$
$$ B = {\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}}^m $$
$$ A = { \begin{bmatrix} 1 & 0 & 1 \\ 0 & B[0][0] & B[0][1] \\ 0 & B[1][0] & B[1][1] \end{bmatrix} } $$
とおいたとき
$$ \begin{bmatrix} s[n+1] \\ F[m(n+2)+1] \\ F[m(n+2)] \end{bmatrix} = A \begin{bmatrix} s[n] \\ F[m(n+1)+1] \\ F[m(n+1)] \end{bmatrix} $$
が成立してこれで行列累乗すればよい。 計算量は$O(\log{n}+\log{m})$
