前置知识
矩阵快速幂，聪明的头脑。
引入
这篇文章旨在记录丰富的矩阵快速幂应用。
多项式
如果在递推式中加入一个和当前项相关的多项式，应该如何解决呢？
如： \[F_n=F_{n-1}+F_{n-2}+n^3\] 或者： \[F_n=F_{n-1}+F_{n-2}+114514n^3+1919810n^2+123n+999\]
其实在复杂矩阵快速幂中已经有过这样的思想了，只不过加的只是一个常数。
我们可以对每一项分开考虑。
从 \(1\) 到 \(1\) 的转换只需要乘 \(1\) 就好了。
从 \(n\) 到 \(n+1\) 的转换，首先加上 \(1\times n\)，然后加上 \(1\times1\)。
从 \(n^2\) 到 \((n+1)^2\) 的转换，则是 \(1\times n^2+2\times n+1\times 1\)。
然后从 \(n^3\) 到 \((n+1)^3\) 是 \(1\times n^3+3\times n^2+3\times n+1\times 1\)。
所以上面的例子的转移矩阵很轻松就求出来了：
\[ \left[ \begin{array}{cc} 1&1&1&0&0&0\\ 1&0&0&0&0&0\\ 0&0&1&3&3&1\\ 0&0&0&1&2&1\\ 0&0&0&0&1&1\\ 0&0&0&0&0&1\\ \end{array} \right]\times\left[ \begin{array}{c} F_{n-1}\\F_{n-2}\\n^3\\n^2\\n\\1 \end{array} \right] =\left[ \begin{array}{c} F_n\\F_{n-1}\\(n+1)^3\\(n+1)^2\\n+1\\1 \end{array} \right] \]
当然，对于那个花里胡哨的例子，转移矩阵也没有差太多：
\[ \left[ \begin{array}{cc} 1&1&114514&1919810&123&999\\ 1&0&0&0&0&0\\ 0&0&1&3&3&1\\ 0&0&0&1&2&1\\ 0&0&0&0&1&1\\ 0&0&0&0&0&1\\ \end{array} \right]\times\left[ \begin{array}{c} F_{n-1}\\F_{n-2}\\n^3\\n^2\\n\\1 \end{array} \right] =\left[ \begin{array}{c} F_n\\F_{n-1}\\(n+1)^3\\(n+1)^2\\n+1\\1 \end{array} \right] \]
图论
其实图论和矩阵渊源挺深的，当我们刚刚开始学习图论时，一般都会接触到一个“邻接矩阵”，可以用来存储一张图。但是随着深入的学习，用到它的地方越来越少，因为它的存储效率属实很低。但是令人意想不到的是，这个矩阵可以用来计算一个看似很复杂的图论题：
给定一个 \(n\) 个节点 \(m\) 条边的图，求从 \(1\) 号点出发到达 \(n\) 号点，恰好走 \(k\) 步的路径条数。
这道题的答案异常简单：只要把邻接矩阵转置一下，当成转移矩阵，直接套用矩阵快速幂就好了。
为什么是这样呢？看看一开始的邻接矩阵，它存储的实际上是所有长度为 \(1\) 的路径。考虑从第 \(i-1\) 个状态转移到第 \(i\) 个状态，意思就是将所有路径都延长一步，由于路径只能沿着开始的邻接矩阵上的边走，所以乘上一个转置的邻接矩阵刚好就是一次成功的转移。
循环
考虑这样一个数列
\[F_n=\left\{\begin{array}{cc}0&n=0\\1&n=1\\F_{n-1}+F_{n-2}+114&n\bmod3=0\\F_{n-1}+F_{n-2}+514&n\bmod3=1\\F_{n-1}+F_{n-2}+123&n\bmod3=2\end{array}\right.\]
它的常数项是循环的。这样的转移，如果按照常规方式做会很难想，甚至完全不可能。但是有一种很巧妙的方法，就是让列向量里的常数也跟着旋转。
假设当前 \(n\bmod3=0\)，我们先构造一个列向量：
\[ \left[ \begin{array}{c} F_{n-1}\\F_{n-2}\\114\\514\\123 \end{array} \right] \]
然后想办法通过设计转移矩阵，让这个列向量的下面三行“旋转”，也就是轮流来到第三行的位置。事实证明这并不难，只要按照下面的方式构造矩阵：
\[ \left[ \begin{array}{cc} 1&1&1&0&0\\ 1&0&0&0&0\\ 0&0&0&1&0\\ 0&0&0&0&1\\ 0&0&1&0&0\\ \end{array} \right]\times\left[ \begin{array}{c} F_{n-1}\\F_{n-2}\\114\\514\\123 \end{array} \right] =\left[ \begin{array}{c} F_n\\F_{n-1}\\514\\123\\114 \end{array} \right] \]