一.前置芝士

1.矩阵乘法

最一般的矩阵乘法是一个 $n * p$ 的矩阵，记为 $A$，和一个 $p * m$ 的矩阵，记为 $B$，相乘，乘出来是一个 $n * m$ 的矩阵,记为 $C$，
用公式表达就是

\[C_{i, j} = \sum\limits_{k = 1} ^ p A_{i, k} + B_{k, j} \]

代码就直接模拟

貌似有时间复杂度为 $O(n^{log(7)})$ 的矩阵乘

~~但貌似除了用来卡常并没有什么用~~

inline void mul(int A[N][P], int B[P][M], int C[N][M]){
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= M; j++)
           for(int k = 1; k <= P; k++)
               C[i][j] += A[i][k] * B[k][j];     
}

2.矩阵快速幂

求一个矩阵的$N$次方

这是一个求 $a^b \bmod p$ 的程序

inline int fast_power(int a, int b, int p){
    int ret = 1;
    while(b){
        if(b & 1) ret = (ret * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return ret;
}

那么对于一个矩阵求快速幂只要把上面的代码魔改一通就好了。

首先代码中的 $ret$ 肯定不是 $1$ 了，那么在矩阵乘法中的 "$1$" 是什么呢？

考虑如下的一个方阵 $I$ (注意是方阵，是 $n * n$ 的矩阵)

\[I = \begin{bmatrix}1&0&\cdots&0&0\\0&1&\cdots&0&0\\\vdots&\vdots& \ddots&\vdots&\vdots\\0&0&\cdots&1&0\\0&0&\cdots&0&1\end{bmatrix}\]

随便找几个矩阵和它相乘（如果能的话）,会发现与它相乘的矩阵还是那个矩阵，没有变，所以这个矩阵就相当于 “$1$”。

把上面的两个代码结合起来就好了。代码就不放了

二.矩阵加速

1.基本原理

拿斐波那契数列来举例子

\[f_{i} = f_{i - 1} + f_{i - 2}(i \ge 2 ,f_1 = 1, f_2 = 1) \]

现在要求这个序列的第 $k$ 项。

我们把 $f_{i - 1}$ 和 $f_{i - 2}$ 放入如下所示的一个矩阵A中（其实是个向量，这里把缺的补成一个方阵）

\[\begin{bmatrix}f_{i - 1}&f_{i - 2}\\0&0\end{bmatrix} \]

然后我们就需要最重要的东西——转移矩阵了。

如果我们构造一个矩阵 $B$，使 $A * B$ 得到的矩阵为如下矩阵

\[\begin{bmatrix}f_{i}&f_{i - 1}\\0&0\end{bmatrix} \]

那么我们就可以一直乘上 $B$ 得到的矩阵就是

\[\begin{bmatrix}f_{i + 1}&f_{i}\\0&0\end{bmatrix} \]

\[\begin{bmatrix}f_{i + 2}&f_{i + 1}\\0&0\end{bmatrix} \]

\[... \]

但我们只要求第 $k$ 项，式子可以变成 $A * B^{k - 2}$ ，而
$B^{k - 2}$ 可以用矩阵快速幂来快速求出。问题解决了。

2.转移矩阵的构造方法

乱搞

常规型

非常简单，每一项只跟前几项有关系。

先放一个矩阵加速入门题。

根据题目给的递推式，我们很容易可以列出递推的矩阵。（就是上面的矩阵 $A$ ）

\[\begin{bmatrix}a_{x - 1}&a_{x - 2}&a_{x - 3}\\0&0&0\\0&0&0\end{bmatrix} \]

这个矩阵中 $a_{x - 1}$, $a_{x - 2}$, $a_{x - 3}$ 的初值就是 $a_1$, $a_2$, $a_3$ 。

现在来推矩阵 $B$。

$A * B$ 得到的矩阵 $C$ 应该是

\[\begin{bmatrix}a_{x}&a_{x - 1}&a_{x - 2}\\0&0&0\\0&0&0\end{bmatrix} \]

已知 $ a_x = a_{x - 1} + a_{x - 3} $。
所以这个新矩阵可以改成

\[\begin{bmatrix}a_{x - 1} + a_{x - 3}&a_{x - 1}&a_{x - 2}\\0&0&0\\0&0&0\end{bmatrix} \]

根据矩阵乘法的公式可知

$C_{1, 1} = A_{1, 1} * B_{1, 1} + A_{1, 2} * B_{2, 1} + A_{1, 3} * B_{3, 1}$

$C_{1, 2} = A_{1, 1} * B_{1, 2} + A_{1, 2} * B_{2, 2} + A_{1, 3} * B_{3, 2}$

$C_{1, 3} = A_{1, 1} * B_{1, 3} + A_{1, 2} * B_{2, 3} + A_{1, 3} * B_{3, 3}$

~~然后根据上面的式子可以凑出转移方程~~

其实还是很好凑的

找找规律，可以得出一条~~算阶上的~~结论

如果原矩阵的第 $i$ 项会对转移后矩阵的第 $j$ 项产生影响，那么就在转移矩阵的第 $i$ 行第 $j$ 列写上适当的常数。(可以结合这个例子理解一下)

含常数型

类似于这样的递推式

\[f_{i} = f_{i - 1} + f_{i - 2} + k \]

把它塞到一个矩阵 $A$ 里面

\[\begin{bmatrix}f_{i - 1}& f_{i - 2}& k\\ 0& 0& 0\\ 0& 0& 0 \end{bmatrix} \]

乘上转移矩阵 $B$ 后应该得到这样的一个矩阵

\[\begin{bmatrix}f_{i}& f_{i - 1}& k\\ 0& 0& 0\\ 0& 0& 0 \end{bmatrix} \]

发现常数项根本没变，就在原来的位置所以矩阵 $B$ 的最后一列就是

\[\begin{bmatrix}0\\ 0\\ 1 \end{bmatrix} \]

所以这种形式的递推式常数直接搬到下一个矩阵就好了。

转移矩阵就是

\[\begin{bmatrix}1& 1& 0\\ 1& 0& 0\\ 1& 0& 1 \end{bmatrix} \]

总结一下，这种带常数的递推式直接把常数放到矩阵里，转移的时候直接搬到下一个矩阵就行了。

含未知数型

类似与这样的形式

\[f_i = f_{i - 1} + f_{i - 2} + i \]

这个时候有点麻烦，不仅要推 $f_{i}$, 还要推 $i$。

这种情况中递推矩阵要同时递推 $f_{i}$ 和 $i$。

要把 $i$ 看成另一个递推式 $g_i$ 这样可能会好理解一点。

原式变成了这个样子

\[f_i = f_{i - 1} + f_{i - 2} + g_{i} \]

先推 $g_{i}$，递推式显然

$g_{i} = g_{i - 1} + 1$

那么这个递推式就是一个很简单的含常数型递推式，容易得出递推矩阵和转移矩阵

递推矩阵：

\[\begin{bmatrix}g_{i - 1}& 1\\ 0& 0 \end{bmatrix} \]

转移矩阵：

\[\begin{bmatrix}1& 0\\1& 1 \end{bmatrix} \]

其实这两个矩阵做题时不用构造

现在构造 $f$ 的递推矩阵

\[\begin{bmatrix}f_{i - 1}& f_{i - 2}& g_{i}& 1\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0 \end{bmatrix} \]

乘上转移矩阵之后应该是这个样子的

\[\begin{bmatrix}f_{i}& f_{i - 1}& g_{i + 1}& 1\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0 \end{bmatrix} \]

$f_i$ 受 $f_{i - 1}$, $f_{i - 2}$, $g_{i}$ 的影响。

$f_{i - 1}$ 直接转移。（也可以说受 $f_{i - 1}$ 的影响）

$g_{i}$ 受 $g_{i - 1}$ 和 $1$ 的影响。

$1$ 直接转移。（受 $1$ 的影响）

上面四句话“翻译”一下

新矩阵第 $1$ 项受原矩阵第 $1$、$2$、$3$ 项的影响。

新矩阵第 $2$ 项受原矩阵第 $1$ 项的影响。

新矩阵第 $3$ 项受原矩阵第 $3$、$4$ 项的影响。

新矩阵第 $4$ 项受原矩阵第 $4$ 项的影响。

之前说过

如果原矩阵的第 $i$ 项会对转移后矩阵的第 $j$ 项产生影响，那么就在转移矩阵的第 $i$ 行第 $j$ 列写上适当的常数

这句话改一下

如果新矩阵的第 $j$ 项受原矩阵的第 $i$ 的影响，那么就在转移矩阵的第 $i$ 行第 $j$ 列写上适当的常数

再根据上面翻译的四句话，很容易写出转移矩阵

\[\begin{bmatrix}1& 1& 0& 0\\ 1& 0& 0& 0\\1& 0& 1& 0\\ 0& 0& 1& 1 \end{bmatrix} \]

遇到难推的矩阵，可以用上面的方法去想。

再放一个比较难的递推式

\[f_i = f_{i - 1} + f_{i - 2} + i^2 \]

和上面一样，设 $g_{i} = i^2$。

这要递推 $g_i$ ，怎么推呢?

我们知道 $(i - 1)^2 = i^2 - 2i + 1$。那么$i^2 = (i - 1)^2 + 2i -1$。

所以$g_{i} = g_{i - 1} + 2i - 1$。

那么要推出 $g_{i}$，矩阵中就要保存 $g_{i - 1}$，$i$，$1$

这个 $i$ 也是要递推的，设 $h_{i} = i = h_{i - 1} + 1$

递推矩阵是

\[\begin{bmatrix}f_{i - 1}& f_{i - 2}& g_i& h_i& 1\\0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0 \end{bmatrix} \]

乘上转移矩阵后应得到

\[\begin{bmatrix}f_{i }& f_{i - 1}& g_{i + 1}& h_{i + 1}& 1\\0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0\\ 0& 0& 0& 0& 0 \end{bmatrix} \]

用之前的方法，转移矩阵也很好构造，注意 $g$
转移时，$h_i$ 的常数

\[\begin{bmatrix}1& 1& 0& 0& 0\\ 1& 0& 0& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 0& 2& 1& 0\\ 0& 0& 1& 1& 1 \end{bmatrix} \]

貌似矩阵还能转移带 $min/max$ 函数的。~~但本蒟蒻不会~~。就先放着

参考资料

算法竞赛进阶指南

526互联

矩阵加速递推与转移矩阵构造方法