No.718

\(S_N = \sum F_i^2\) とすると, 以下の計算式が成り立つ.

\[\begin{align} S_{i+1} &= S_i + F_{i+1}^2 \\ F_{i+2}^2 &= (F_{i+1}+F_i)^2 = F_{i+1}^2+F_i^2+2F_{i+1}F_i \\ F_{i+2}F_{i+1} &= (F_{i+1}+F_i)F_{i+1} = F_{i+1}^2 + F_{i+1}F_i \\ \end{align}\]

これを行列形式で表すと,

\[\begin{pmatrix} S_{i+1} \\ F_{i+2}^2 \\ F_{i+1}^2 \\ F_{i+2}F_{i+1} \end{pmatrix} = \begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 2 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix} \begin{pmatrix} S_i \\ F_{i+1}^2 \\ F_i^2 \\ F_{i+1}F_i \end{pmatrix}\]

よって,

\[\begin{pmatrix} S_N \\ F_{N+1}^2 \\ F_N^2 \\ F_{N+1}F_N \end{pmatrix} = \begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 2 \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix} ^N \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}\]

となるので, 行列の累乗を繰り返し2乗法で計算すればいい.