矩阵快速幂，听起来很难，模板题也都是绿色的，令人望而却步。我在发呆时突然想起了矩阵快速幂，于是花了一个下午去学习它。于是，就有了这篇文章。
ACGO 主题库上似乎还没有矩阵快速幂的题目，我从洛谷上搬运了几道。数据自造，强度应该是够的，如果搬的题目或数据有什么问题还请联系我。题单：矩阵模板题。原题分别为洛谷 P3390，P1939 和 P1962。
正文从此开始。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前置知识：
* 快速幂
* 矩阵
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
概念
先从矩阵的乘法讲起。矩阵乘法 AB=CAB=CAB=C 的定义为：
cij=∑k=1naikbkj,(1≤i≤m, 1≤j≤p).c_{i j} = \sum_{k = 1}^{n} a_{i k} b_{k j} \text{,\qquad($1 \le i \le m$, $1 \le j \le p$).} cij =k=1∑n aik bkj ,(1≤i≤m, 1≤j≤p).
其中 AAA 的大小为 m×nm\times nm×n，BBB 的大小为 n×pn\times pn×p，结果 CCC 的大小为 m×pm\times pm×p。如果 AAA 的列数与 BBB 的行数不同，则他们无法进行矩阵乘法。 是不是有点抽象？举个例子你就明白了。当 AAA 的大小为 2×22\times 22×2，BBB 的大小为 2×32\times 32×3 时，则
C=[a11b11+a12b21a11b12+a12b22a11b13+a12b23a21b11+a22b21a21b12+a22b22a21b13+a22b23]. C = \begin{bmatrix} a_{11}b_{11}+a_{12}b_{21} & a_{11}b_{12}+a_{12}b_{22} & a_{11}b_{13}+a_{12}b_{23}\\ a_{21}b_{11}+a_{22}b_{21} & a_{21}b_{12}+a_{22}b_{22} & a_{21}b_{13}+a_{22}b_{23} \end{bmatrix} \text{.} C=[a11
b11 +a12 b21 a21 b11 +a22 b21 a11 b12 +a12 b22 a21 b12 +a22 b22 a11 b13 +a12 b23 a21 b13 +a22 b23 ].
同时，我们可以证明矩阵乘法满足结合律，但在一般情况下不满足交换律。
我们立刻写出了这样的矩阵乘法代码：
这个代码的时间复杂度是 O(n3)O(n^3)O(n3) 的，可以接受。事实上，《算法导论》给出了一种时间复杂度 O(nlog27)O(n^{\log_2 7})O(nlog2 7) 的矩阵乘法算法，但似乎并没有在 OI 界得到广泛运用，因此这里暂不介绍。
现在，我们回到正题：矩阵快速幂。由于矩阵乘法满足结合律，我们把它当作一般的快速幂打代码即可，只不过数字变成了矩阵，乘法变成了矩阵乘法。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
实现
先放出 AC 模板题的代码：
整个代码的精髓是这几行：
最令人疑惑的是第三行。按照第三行的定义，我们构造出的矩阵是：
Ans=[10⋯001⋯⋮⋮⋮⋱⋮0⋯⋯1]. Ans = \begin{bmatrix} 1 & 0 & \cdots & 0\\ 0 & 1 & \cdots & \vdots\\ \vdots & \vdots & \ddots & \vdots\\ 0 & \cdots & \cdots & 1\\ \end{bmatrix} \text{.} Ans= 10⋮0 01⋮⋯ ⋯⋯⋱⋯ 0⋮⋮1 .
这个矩阵我们称其为单位矩阵。任何矩阵与单位矩阵相乘，得到的依然是原矩阵。 因此，单位矩阵就类似数的乘法中的 111，起到基的作用。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
应用
例题：斐波那契数列（洛谷）或斐波那契数列（ACGO 搬运）。
题面非常简单，就是让你求斐波那契数列的第 nnn 项。但是看到数据范围，1≤n<2631\leq n<2^{63}1≤n<263，显然事情并不是那么简单。现在，我们先从斐波那契数列的本质想起。它的递推式是这样的：
fi=fi−1+fi−2f_i=f_{i-1}+f_{i-2} fi =fi−1 +fi−2
发现 fif_ifi 的值只与前两项有关。我们只需要保存两项的值就够了。我们把接下来需要保存的两项 fi,fi−1f_i,f_{i-1}fi ,fi−1 通过现在已知的两项 fi−1,fi−2f_{i-1},f_{i-2}fi−1 ,fi−2 表达出来，形成一个线性方程组：
{1×fi−1+1×fi−2=fi1×fi−1+0×fi−2=fi−1\begin{cases} 1\times f_{i-1}+1\times f_{i-2} &= f_i\\ 1\times f_{i-1}+0\times f_{i-2} &= f_{i-1} \end{cases}{1×fi−1 +1×fi−2 1×fi−1 +0×fi−2 =fi =fi−1
根据矩阵乘法，我们可以把这个方程组表达成两个矩阵相乘：
[1110][fi−1fi−2]=[fifi−1]\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} f_{i-1}\\ f_{i-2} \end{bmatrix}=\begin{bmatrix} f_i\\ f_{i-1} \end{bmatrix}[11 10 ][fi−1 fi−2 ]=[fi fi−1 ]
这是线性代数中十分常见的变换。是不是非常神奇？别急，还有更神奇的。我们发现矩阵 [fi−1fi−2]\begin{bmatrix}f_{i-1}\\f_{i-2}\end{bmatrix}[fi−1 fi−2 ] 也可以用这个式子求出来。于是，我们可以把它展开：
[1110]([1110][fi−2fi−3])=[fifi−1]\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\left(\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} f_{i-2}\\ f_{i-3} \end{bmatrix}\right)=\begin{bmatrix} f_i\\ f_{i-1} \end{bmatrix}[11 10 ]([11 10 ][fi−2 fi−3 ])=[fi fi−1 ]
继续展开直到已知项 [f2f1]\begin{bmatrix}f_2\\f_1\end{bmatrix}[f2 f1 ]：
[1110]([1110](⋯[1110][f2f1]⋯ ))=[fifi−1]\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\left(\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\left(\cdots\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} f_2\\ f_1 \end{bmatrix}\cdots\right)\right)=\begin{bmatrix} f_i\\ f_{i-1} \end{bmatrix}[11 10
]([11 10 ](⋯[11 10 ][f2 f1 ]⋯))=[fi fi−1 ]
又根据矩阵乘法的结合律：
[1110]i−2[f2f1]=[fifi−1]\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{i-2}\begin{bmatrix} f_2\\ f_1 \end{bmatrix}=\begin{bmatrix} f_i\\ f_{i-1} \end{bmatrix}[11 10 ]i−2[f2 f1 ]=[fi fi−1 ]
（为什么是 i−2i-2i−2 次？因为乘 iii 次的时候结果矩阵的首项就是 fi+2f_{i+2}fi+2 了，所以乘 i−2i-2i−2 次的时候结果矩阵的首项就刚好是 fif_ifi 了，如果不理解手推一下就明白了。）
现在，你一定发现了：[1110]i−2\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^{i-2}[11 10 ]i−2 这一项，直接使用矩阵快速幂即可。最后再乘上 [f2f1]\begin{bmatrix}f_2\\f_1\end{bmatrix}[f2 f1 ] 即 [11]\begin{bmatrix}1\\1\end{bmatrix}[11 ]，得到的结果矩阵首项即为所求的 fif_ifi 。由于矩阵的大小为常数，所以可以把单次矩阵乘法视为 O(1)O(1)O(1)，矩阵快速幂的时间复杂度即为 O(logn)O(\log n)O(logn)，轻松跑过
long long 范围。注意特判 n≤2n\leq 2n≤2 即可（本搬题人好心地加上了这两个极限情况）。AC 代码如下：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
总结
总结一下，用矩阵快速幂优化此类递推（动态规划）的步骤：
1. 确定哪些状态对结果状态或过程状态有贡献。只保留有贡献的状态。
2. 确定上一次得到的状态转移到当前状态使用的递推式（方程组）。
3. 提取方程组的各项系数为转移矩阵。
4. 计算转移矩阵的次数。
5. 写下矩阵快速幂和矩阵乘法模板。
接下来大家可以尝试一下矩阵加速（数列）（洛谷）、矩阵加速（数列）（ACGO 搬运）和广义斐波那契数列（洛谷）。如果你会数论，还可以尝试斐波那契公约数（我不会）。
祝大家暑假快乐！
看在我搬题，打 LaTeX\LaTeX{}LATE X，写 Markdown 这么努力，可否留个赞支持一下 qwq。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Upd on 2024/6/30：ACGO主题库已有广义斐波那契数列与斐波那契公约数。
