yukicon-196 行列のできるフィボナッチ数列道場 (2)

問題URL

この問題文中の数列 $F_i$ はその定義よりフィボナッチ数列です。
フィボナッチ数列の $k$ 項を求めるには次の有名な方法があります。
　$A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ とおいたとき、 $F_k = $ 行列 $A^k$ の左下の数
よって、この問題で求めるものは
　$\biggl(\displaystyle \sum_{i=1}^nA^{im}\biggr)$ の左下の数
となります。ここで、
　$S_k = \displaystyle \sum_{i=1}^kA^{im}$
とおきます。この問題で求めるものは $S_n$ の左下の数ですが、これを普通に求めると $O(n)$ かかってしまいます。
この $S_k$ に関して次の式が成り立ちます。
　$S_0 = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$
　$S_{2k + 1} = S_{2k} + A^{(2k + 1)m}$
　$S_{2k} = S_k + S_k \times A^{km}$
これらから、$S_n$ は繰り返し二乗法を使うことで高速に求められることがわかります。
$A^k$ を求めるのは繰り返し二乗法を使うことで $O(\log k)$ で計算できるので、 $S_n$ を求めるのにかかる時間は $O(\log^2n\times\log m)$ となります。

ソースコード