在前一篇文章《从快速幂到矩阵快速幂》中介绍了一种$O(\log n)$求解斐波那契数列的方法，其中使用的就是矩阵快速幂。
而使用矩阵快速幂的前提就是将递推式转为矩阵乘法的形式，例如前文所提到的斐波那契数列：
$$ f(n)=f(n-1)+f(n-2) $$
就可以转换为一下矩阵乘法的形式：
$$ \left[\begin{matrix}1 & 1\\1 & 0\end{matrix}\right]\left[\begin{matrix}f(n-1)\\f(n-2)\end{matrix}\right]=\left[\begin{matrix}f(n)\\f(n-1)\end{matrix}\right] $$
那么对于其他更加特殊的递推式，我们需要如何改写呢？这需要一定的数学直觉
例如对于下式：
$$ f(n)=f(n-1)+f(n-3) $$
我们可以观察，其当前项依赖于前一项和前三项之和，对此，我们可以进行如下改写：
$$ \left[\begin{matrix}1 & 0 & 1\\1 & 0 & 0\\0 & 1 & 0\end{matrix}\right]\left[\begin{matrix}f(n-1)\\f(n-2)\\ f(n-3)\end{matrix}\right]=\left[\begin{matrix}f(n)\\f(n-1)\\f(n-2)\end{matrix}\right] $$
再增加一点难度：
$$ f(n)=2f(n-1)+f(n-3)+n-3 $$
其可以改写为：
$$ \left[\begin{matrix}2 & 0 & 1 & 1 & 0\\1 & 0 & 0 & 0 & 0\\0 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 1 & 1\\0 & 0 & 0 & 0 & 1\end{matrix}\right]\left[\begin{matrix}f(n-1)\\f(n-2)\\f(n-3)\\n-3\\1\end{matrix}\right]=\left[\begin{matrix}f(n)\\f(n-1)\\f(n-2)\\n-2\\1\end{matrix}\right] $$
注意，在改写的时候要注意不能将变量写成恒等的形式，例如这样是不行的：
$$ \left[\begin{matrix}1 & 0\\0 & 1\end{matrix}\right]\left[\begin{matrix}f(n)\\f(n-1)\end{matrix}\right]=\left[\begin{matrix}f(n)\\f(n-1)\end{matrix}\right] $$
很粗暴的来说，不能直接让左右两个列向量中某元素直接相等（常量除外）。
对于含有指数的递推式：
$$ f(n)=f(n-1)+3^n $$
我们可以可以这样处理
$$ \left[\begin{matrix}1 & 1\\0 & 3\end{matrix}\right]\left[\begin{matrix}f(n-1)\\3^n\end{matrix}\right]=\left[\begin{matrix}f(n)\\3^{n+1}\end{matrix}\right] $$
