讨论一下两个 \(1\times1\) 的方格是否在同一行可以发现答案就是 \(2\times\sum\limits_{i=1}^{n-3}f_i\times sum_{n-i-3}\),其中 \(f_i\) 为斐波那契数列的第 \(i\) 项,\(sum_i=\sum\limits_{j=1}^i f_j\)。直接计算可以得到 \(50\) 分。
容易发现 \(sum_i=f_{i+2}-1\),证明的话可以移项拆式子。
那么问题就变成了求解 \(2\times\sum\limits_{i=1}^{n-3}f_i\times(f_{n-i-1} - 1)=2\times\sum\limits_{i=1}^{n-3}(f_i\times f_{n-i-1}-f_i)\)。
设 \(G_i=\sum\limits_{j=1}^i f_j\times f_{n-j}\),则答案可以被表示为 \(2\times(G_{n-3}-f_{n-1}\times f_0-f_{n-2}\times f_1-f_{n-1}+1)\)。
考虑如何化简 \(G_n\):
\[\begin{aligned}
G_{n}&=\sum\limits_{i=1}^n f_i\times f_{n-i}\\
&=\sum\limits_{i=1}^{n-2}f_i\times f_{n-i}+f_n+f_{n-1}\\
&=\sum\limits_{i=1}^{n-2}f_i\times(f_{n-i-1}+f_{n-i-2})+f_n+f_{n-1}\\
&=\sum\limits_{i=1}^{n-2}f_i\times f_{n-i-1}+\sum\limits_{i=1}^{n-2}f_i\times f_{n-i-2}+f_n+f_{n-1}\\
&=\sum\limits_{i=1}^{n-1}f_i\times f_{n-i-1}+\sum\limits_{i=1}^{n-2}f_i\times f_{n-i-2}+f_n\\
&=G_{n-1}+G_{n-2}+f_n
\end{aligned}\]
这样就可以用矩阵乘法了。
具体的,转移矩阵是:
\[\begin{bmatrix}
G_{i-1}&G_{i-2}&f_{i-1}& f_{i-2}
\end{bmatrix}
\times
\begin{bmatrix}
1&1&0&0\\
1&0&0&0\\
1&0&1&1\\
1&0&1&0
\end{bmatrix}
=
\begin{bmatrix}
G_{i}&G_{i-1}&f_{i}& f_{i-1}
\end{bmatrix}
\]
代码链接:link