考虑如下式子：fn=fn−1+fn−2f_n=f_{n-1}+f_{n-2}，其中 f0=0,f1=1f_0=0,f_1=1。使用递推方法，时间复杂度为 O(n)O(n)。考虑优化。

再考虑如下矩阵：

[fnfn−1]\begin{bmatrix}f_n\\f_{n-1}\end{bmatrix}

基于第一个式子，可知这个矩阵等于

[fn−1+fn−2fn−1]\begin{bmatrix}f_{n-1}+f_{n-2}\\f_{n-1}\end{bmatrix}

提取出系数矩阵，可知这个矩阵又等于

[1110][fn−1fn−2]\begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}f_{n-1}\\f_{n-2}\end{bmatrix}

在以上矩阵乘法式中的第一个矩阵（系数矩阵）中，第一行的 11 表示上一个矩阵的第一行 fn−1+fn−2f_{n-1}+f_{n-2} 包含乘式中第二个矩阵的第一项 fn−1f_{n-1}，且系数为 11。系数矩阵的其他元素同理。由于

[fn−1fn−2]=[1110][fn−2fn−3]\begin{bmatrix}f_{n-1}\\f_{n-2}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}\begin{bmatrix}f_{n-2}\\f_{n-3}\end{bmatrix}

所以

[fnfn−1]=[1110]2[fn−2fn−3]\begin{bmatrix}f_n\\f_{n-1}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^2\begin{bmatrix}f_{n-2}\\f_{n-3}\end{bmatrix}

类似的，可以得出

[fnfn−1]=[1110]n−1[f1f0]=[1110]n−1[10]\begin{bmatrix}f_n\\f_{n-1}\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1}\begin{bmatrix}f_1\\f_0\end{bmatrix}=\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1}\begin{bmatrix}1\\0\end{bmatrix}

因为矩阵乘法的结合律（也就是 (AB)C=A(BC)(AB)C=A(BC)，其中 AA、BB、CC皆为矩阵），于是可以用快速幂优化矩阵乘法，称之为矩阵快速幂。复杂度为 O(log⁡n)O(\log n)，常数 ∝\propto 矩阵大小。

练习：写出如下式子的矩阵转移式：fn=fn−1+fn−2+kf_n=f_{n-1}+f_{n-2}+k。

矩阵快速幂优化含有变量的递推

再考虑优化如下式子：fn=fn−1+fn−2+nf_n=f_{n-1}+f_{n-2}+n，其中 f0=0,f1=1f_0=0,f_1=1。对于其中的变量 nn，它的转移为 n=(n−1)+1n=(n-1)+1，不能像常数一样直接转移，所以需要这样做：

[fnfn−1n1]=[fn−1+fn−2+(n−1)+1fn−1(n−1)+11]=[1111100000110001][fn−1fn−2n−11]\begin{bmatrix}f_n\\f_{n-1}\\n\\1\end{bmatrix}=\begin{bmatrix}f_{n-1}+f_{n-2}+(n-1)+1\\f_{n-1}\\(n-1)+1\\1\end{bmatrix}=\begin{bmatrix}1&1&1&1\\1&0&0&0\\0&0&1&1\\0&0&0&1\end{bmatrix}\begin{bmatrix}f_{n-1}\\f_{n-2}\\n-1\\1\end{bmatrix}

练习：写出如下式子的矩阵转移式：fn=fn−1+fn−2+n2f_n=f_{n-1}+f_{n-2}+n^2。

答案：

  1. [fnfn−1k]=[111100001][fn−1fn−2k]\begin{bmatrix}f_n\\f_{n-1}\\k\end{bmatrix}=\begin{bmatrix}1&1&1\\1&0&0\\0&0&1\end{bmatrix}\begin{bmatrix}f_{n-1}\\f_{n-2}\\k\end{bmatrix}
  2. [fnfn−1n2n1]=[1112110000001210001100001][fn−1fn−2(n−1)2n−11]\begin{bmatrix}f_n\\f_{n-1}\\n^2\\n\\1\end{bmatrix}=\begin{bmatrix}1&1&1&2&1\\1&0&0&0&0\\0&0&1&2&1\\0&0&0&1&1\\0&0&0&0&1\end{bmatrix}\begin{bmatrix}f_{n-1}\\f_{n-2}\\(n-1)^2\\n-1\\1\end{bmatrix}

本人线性代数基础极其不扎实，如有谬误，欢迎指正！