矩阵乘法递推加速
警告，本文KaTex排版较多，请耐心等待页面加载完成再浏览。
如果有不想看的章节，请查看左侧 TOC 跳过。
0x00 什么是矩阵乘法
这是一个 $\rm 2\times 3$ 的矩阵。
$\rm A =\begin{bmatrix}a_{1,1} & a_{1,2} & a_{1,3} \cr a_{2,1} & a_{2,2} & a_{2,3}\end{bmatrix}$
这是另一个 $\rm 3\times 4$ 的矩阵。
$
\rm B =
\begin{bmatrix}
b_{1,1} & b_{1,2} & b_{1,3} & b_{1,4} \\
b_{2,1} & b_{2,2} & b_{2,3} & b_{2,4} \\
b_{3,1} & b_{3,2} & b_{3,3} & b_{3,4}
\end{bmatrix}
$
矩阵乘法的定义是，对于两个矩阵 $\rm m \times p$ 的矩阵 $A$ 和 $\rm p \times n$ 的矩阵 $B$，令矩阵 $C = A\times B$，则矩阵 $C$ 中的第 $i$ 行 $j$ 列的元素可以表示为：
$
C_{ij} = \sum\limits_{k = 1}^{p} a_{ik}\times b_{kj}
$
最后乘出来的矩阵是一个 $\rm m \times n$ 的矩阵。
用稍微通俗一点的语言说，就是对于矩阵 $C$ 的第 $i$ 行 $j$ 列的元素值就是 $A$ 矩阵第 $i$ 行的元素和 $B$ 矩阵第 $j$ 列元素一一对应相乘的和。
如果你看不明白，那我就以矩阵 $C \rm(2 \times 4)$ 的一个元素（$c_{1,2}$）举个例子。
长公式不想打了啊啊啊
$$
c_{1,2} = \sum\limits_{k = 1}^{p} a_{1,k}\times b_{k,2} = a_{1,1}\times b_{1,2} + a_{1,2}\times b_{2,2} + a_{1,3}\times b_{3,2}
$$
好，现在你知道什么是矩阵乘法了。尝试一下 Hydro H1005.【模板】矩阵乘法。
0x01 矩阵乘法和递推式之间的关系
先来看一道题：洛谷 P1962 斐波那契数列
这个东西不就是暴力循环就能拿分的题吗？
如果你是这么想的，那么就去逝逝罢，$\sf\color{#fadb14} 60\space \color{white}\colorbox{#e74c3c}{Unaccpted}$。
$1\le n < 2^{63}$ 的范围不卡死你才怪。
接下来的思路有点奇妙。
记斐波那契数列第 $n$ 项为 $F_n$。
我们假定一个矩阵：
$\begin{bmatrix}
F_n & F_{n – 1}
\end{bmatrix}$
根据斐波那契数列的递推式，$F_n = F_{n – 1} + F_{n – 2}$。
我们希望有一个矩阵 $\rm base$，达到如下效果：
$\begin{bmatrix}
F_n & F_{n – 1}
\end{bmatrix} =
\begin{bmatrix}
F_{n – 1} & F_{n – 2}
\end{bmatrix}
\times \rm base
$
此时 $\rm base =
\begin{bmatrix}
1 & 1 \cr
1 & 0
\end{bmatrix}$。
因此，只需要把 $\rm base$ 推出来就可以了。
又由于矩阵乘法有结合律（在此不做证明），故可以将 $F_n$ 表示如下：
$\begin{aligned}
\begin{bmatrix}
F_n & F_{n – 1}
\end{bmatrix} &=
\begin{bmatrix}
F_{n – 1} & F_{n – 2}
\end{bmatrix}\times \rm base\cr
&= \begin{bmatrix}
F_{n – 2} & F_{n – 3}
\end{bmatrix}
\times\rm base \times\rm base\cr &=\cdots\cr&=
\begin{bmatrix}
F_1 & F_2
\end{bmatrix}
\times \rm base^{n – 1}\cr &=
\begin{bmatrix}
1 & 1
\end{bmatrix}
\times\rm base^{n – 1}
\end{aligned}$
矩阵/递推式练习
做几道练习题感受一下：（递推式转矩阵）
$F_n = 3F_{n-1} + 2F_{n-2}$
答案
$\begin{bmatrix}
F_n & F_{n – 1}
\end{bmatrix} = \begin{bmatrix}
F_{n – 1} & F_{n – 2}
\end{bmatrix}
\times\begin{bmatrix}
3 & 1 \cr
2 & 0
\end{bmatrix}$
$F_n = 15F_{n-1} – 2F_{n-2}$
答案
$\begin{bmatrix}
F_n & F_{n – 1}
\end{bmatrix} =\begin{bmatrix}
F_{n – 1} & F_{n – 2}
\end{bmatrix} \times
\begin{bmatrix}
15 & 1 \cr
-2 & 0
\end{bmatrix}$
$F_n = 3F_{n-1} + 2F_{n-2} + F_{n-3}$
答案
$\begin{bmatrix}
F_n & F_{n – 1} & F_{n-2}
\end{bmatrix} = \begin{bmatrix}
F_{n – 1} & F_{n – 2} & F_{n-3}
\end{bmatrix} \times \begin{bmatrix}
3 & 1 & 0 \cr
2 & 0 & 1 \cr
1 & 0 & 0
\end{bmatrix}$
$F_n = 3F_{n-1} + 2F_{n-2} + F_{n-3}$
答案
$\begin{bmatrix}
F_n & F_{n – 1} & F_{n-2}
\end{bmatrix} =
\begin{bmatrix}
F_{n – 1} & F_{n – 2} & F_{n-3}
\end{bmatrix} \times \begin{bmatrix}
3 & 1 & 0 \cr
2 & 0 & 1 \cr
1 & 0 & 0
\end{bmatrix}$
$F_n = 3F_{n-1} + 2F_{n-2} + 114514$
答案
$\begin{bmatrix}
F_n & F_{n – 1} & 114514
\end{bmatrix} = \begin{bmatrix}
F_{n – 1} & F_{n – 2} & 114514
\end{bmatrix} \times
\begin{bmatrix}
3 & 1 & 0 \cr
2 & 0 & 0 \cr
1 & 0 & 1
\end{bmatrix}$
还可以将多个递推式合成一个矩阵。
$F_n = F_{n-1} + F_{n-2}$
$S_n = S_{n-1} + F_n$
答案
$S_n = S_{n-1} + F_n = S_{n-1} + F_{n-1} + F_{n-2}$
$\begin{bmatrix}
F_n & F_{n – 1} & S_n
\end{bmatrix} = \begin{bmatrix}
F_{n – 1} & F_{n – 2} & S_{n-1}
\end{bmatrix} \times
\begin{bmatrix}
3 & 1 & 1 \cr
2 & 0 & 1 \cr
1 & 0 & 1
\end{bmatrix}$
0x03 矩阵快速幂
现在我们已经推出了 $\begin{bmatrix}
F_n & F_{n – 1}
\end{bmatrix} = \begin{bmatrix}
1 & 1
\end{bmatrix} \times base^{n – 1}
$。
这么做的时间复杂度还是 $\rm O(n)$（甚至更高），因此我们需要特殊手段进行优化。
这时候，我们就可以搬出矩阵快速幂了。矩阵快速幂与整数快速幂思路基本相同，唯一的不同就是将整数换成了矩阵。
建议封装一下矩阵结构体/类，这样写起来方便一点。注意取模。
总体时间复杂度：$\rm O(\log n)$
0x04 练习题
| 题目链接 | 名称 |
|---|---|
| 洛谷 P1962 | 斐波那契数列 |
| 洛谷 P1349 | 广义斐波那契数列 |
| 洛谷 P5789 | [TJOI2017]可乐（数据加强版） |
| 洛谷 P1707 | 刷题比赛 |
| 洛谷 P1397 | [NOI2013] 矩阵游戏 |
| 洛谷 P2151 | [SDOI2009] HH去散步 |
| 洛谷 P3216 | [HNOI2011]数学作业 |
| 洛谷 P4159 | [SCOI2009] 迷路 |
以及模板题。