矩阵相关内容是线性代数的基础知识，在算法竞赛中最主要的应用是矩阵快速幂加速递推。本文从矩阵乘法的定义与实现细节讲起，介绍矩阵快速幂的原理，并通过斐波那契数列等经典例题展示转移矩阵的构造方法；随后延伸到图论中的应用——邻接矩阵的幂计数定长路径，以及用 $(\min, +)$ 广义矩阵乘法处理恰好经过 $k$ 条边的最短路。

矩阵乘法

一个 $m \times n$ 的矩阵是由 $m$ 行 $n$ 列元素排列成的矩形阵列，记作 $A = (a_{i,j})$。两个大小分别为 $m \times n$ 和 $n \times p$ 的矩阵 $A, B$ 相乘的结果是一个 $m \times p$ 的矩阵 $C$，其中

$$ C_{i,j} = \sum_{k = 1}^{n} A_{i,k} B_{k,j} $$

通俗地，$C$ 第 $i$ 行第 $j$ 列的元素，就是 $A$ 的第 $i$ 行与 $B$ 的第 $j$ 列对应相乘再相加，口诀是"左行右列"。如果 $A$ 的列数与 $B$ 的行数不相等，则无法进行乘法。

矩阵乘法满足结合律，即 $(AB)C = A(BC)$，却不满足交换律。结合律是矩阵快速幂的理论基础，而交换律不成立意味着用行向量乘转移矩阵递推时，矩阵必须放在向量的右侧，顺序不能随意交换。

计算一次矩阵乘法的时间复杂度为 $O(mnp)$，对 $n \times n$ 的方阵即 $O(n^3)$。

循环顺序对实际运行速度的影响很大。对比下面两种写法：

1
2
3
4
5
6
7
8
9
10
11
// 慢：求和下标 k 在最内层，B[k][j] 按列跳跃访问
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
    C[i][j]+=A[i][k]*B[k][j];

// 快：j 在最内层，B[k][j] 与 C[i][j] 都沿行连续访问
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
    C[i][j]+=A[i][k]*B[k][j];

下面的写法明显更快。原因是 C++ 的二维数组按行存储，最内层循环枚举 $j$ 时，$B[k][j]$ 和 $C[i][j]$ 都是沿行连续访问，缓存命中率高；把求和下标 $k$ 放在最内层，$B[k][j]$ 每次都要跨一整行跳跃访问，缓存几乎不命中。代码模板中的 $i, k, j$ 顺序同理，此时三种数组的访问都是连续的。

代码模板

例题：B2105 矩阵乘法 - 洛谷，按定义三重循环实现即可，时间复杂度 $O(nmk)$。本题 $n, m, k \le 100$ 且元素绝对值不超过 $1000$，乘积的绝对值不超过 $10^8$，int 足够。代码见 代码模板-矩阵。

矩阵快速幂

因为矩阵乘法具有结合律，所以可以使用类似快速幂的思想，来计算矩阵的幂。把整数快速幂中的乘法换成矩阵乘法，初始值从 $1$ 换成单位矩阵 $I$（$A^0 = I$），就能在 $O(n^3 \log k)$ 的时间内求出 $n \times n$ 矩阵的 $k$ 次幂。

代码模板

例题：P3390 【模板】矩阵快速幂 - 洛谷。注意本题 $k \le 10^{12}$，指数需要用 long long 存储，取模用 int 也有溢出风险。代码见 代码模板-矩阵。

基本应用：斐波那契数列

例题：P1962 斐波那契数列 - 洛谷。数列满足 $F_1 = F_2 = 1$，$F_n = F_{n-1} + F_{n-2}$（$n \ge 3$），求 $F_n \bmod 10^9 + 7$，其中 $n < 2^{63}$。朴素递推是 $O(n)$ 的，在 $10^{18}$ 级别的数据范围下无法通过，考虑用矩阵快速幂加速递推。

构造转移矩阵，使相邻两项可以递推：

$$ \begin{bmatrix} F_{i-1} & F_i \end{bmatrix} A = \begin{bmatrix} F_i & F_{i+1} \end{bmatrix}, \quad A = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix} $$

规定 $F_0 = 0$，用数学归纳法可以证明

$$ A^n = \begin{bmatrix} F_{n-1} & F_n \\ F_n & F_{n+1} \end{bmatrix} \quad (n \ge 1) $$

$n = 1$ 时 $A = \begin{bmatrix} F_0 & F_1 \\ F_1 & F_2 \end{bmatrix}$ 成立；假设上式对 $n$ 成立，则 $A^{n+1} = A^n \cdot A = \begin{bmatrix} F_n & F_{n-1} + F_n \\ F_{n+1} & F_n + F_{n+1} \end{bmatrix} = \begin{bmatrix} F_n & F_{n+1} \\ F_{n+1} & F_{n+2} \end{bmatrix}$，依然成立。
所以 $F_n$ 就是 $A^n$ 第 1 行第 2 列的元素，直接计算 $A^n$ 读出即可，$n \ge 1$ 恒成立，不需要特判边界。时间复杂度 $O(k^3 \log n)$，本题 $k = 2$。

拓展：矩阵加速数列

同样的方法可以推广到更一般的线性递推。例题：P1939 矩阵加速（数列） - 洛谷，数列满足 $a_1 = a_2 = a_3 = 1$，$a_n = a_{n-1} + a_{n-3}$（$n \ge 4$），$T \le 100$ 组询问，每组 $n \le 2 \times 10^9$。

此时递推需要用到最近三项，构造 $3 \times 3$ 的转移矩阵，使连续三项递推：

$$ \begin{bmatrix} a_i & a_{i+1} & a_{i+2} \end{bmatrix} M = \begin{bmatrix} a_{i+1} & a_{i+2} & a_{i+3} \end{bmatrix}, \quad M = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{bmatrix} $$

对每组询问计算 $\begin{bmatrix} a_1 & a_2 & a_3 \end{bmatrix} M^{n-1}$，$a_n$ 就是结果的第 1 个元素，$n \ge 1$ 恒成立，不需要特判边界，单组询问的复杂度是 $O(3^3 \log n)$。

综上所述，矩阵快速幂加速递推适用于形如 $f_n = \sum c_i f_{n-i}$ 的线性递推：把状态打包成向量，把递推关系写成转移矩阵，答案就是转移矩阵的某次幂与初始向量的乘积中的某个元素。转移矩阵的规模等于状态包含的项数，总复杂度 $O(k^3 \log n)$。

矩阵快速幂在图论中的应用

应用：定长路径计数

矩阵幂在图论中还有一个经典应用。设 $S$ 是有向图的邻接矩阵，$S_{i,j}$ 表示 $i \to j$ 的边数，则 $(S^k)_{i,j}$ 等于从 $i$ 到 $j$ 恰好走 $k$ 步的方案数（允许重复经过点和边）。用数学归纳法证明：$k = 1$ 时 $(S^1)_{i,j} = S_{i,j}$ 就是边数；假设结论对 $k - 1$ 成立，展开

$$ (S^k)_{i,j} = \sum_{t = 1}^{n} S_{i,t} (S^{k-1})_{t,j} $$

组合意义是从 $i$ 先走一步到 $t$（$S_{i,t}$ 种选择），再从 $t$ 走 $k - 1$ 步到 $j$（$(S^{k-1})_{t,j}$ 种方案），对所有中间点 $t$ 求和，不重不漏地枚举了所有长度为 $k$ 的路径。

于是"从 $a$ 到 $b$ 恰好走 $k$ 步的方案数"就是 $(S^k)_{a,b}$，直接用矩阵快速幂计算即可，时间复杂度 $O(n^3 \log k)$。这里的 $S$ 不必是 $0/1$ 矩阵，重边记成边数即可。

把这套框架中的"乘积求和"换成"求和取 $\min$"，还能进一步处理定长最短路问题（见下文）。

拓展：恰好经过 $k$ 条边的最短路

设 $G$ 是"走恰好 1 条边"的距离矩阵：$G_{i,j}$ 为 $i \to j$ 的最小边权（重边取最小），无直接边则为 $+\infty$，对角线同样保持 $+\infty$。记 $L_k[i][j]$ 为 $i \to j$ 恰好走 $k$ 条边的最短路，有转移

$$ L_{k+1}[i][j] = \min_{1 \le p \le n} \{ L_k[i][p] + G[p][j] \} $$

把普通矩阵乘法中"乘积求和"换成"求和取 $\min$"，定义 $(\min, +)$ 广义乘法

$$ (A \odot B)_{i,j} = \min_{1 \le p \le n} \{ A_{i,p} + B_{p,j} \} $$

则 $L_{k+1} = L_k \odot G$，归纳可得 $L_k = G^{\odot k}$。$\min$ 与 $+$ 组合满足结合律，"先走 $a$ 条边再走 $b$ 条边"可以任意分段，所以同样能用二进制快速幂计算 $G^{\odot k}$，$(G^{\odot k})_{a,b}$ 即答案，时间复杂度 $O(n^3 \log k)$。代码实现见 代码模板-矩阵。

两个细节要注意：对角线若设成 $0$，相当于加入"原地停留"的假边，“恰好 $k$ 条边"会退化成"不超过 $k$ 条边”；快速幂累乘器的单位元是对角线为 $0$、其余为 $+\infty$ 的"0 条边"矩阵，而不是全 $0$ 矩阵。

例题：洛谷 P2886 [USACO07NOV] Cow Relays G

题意：给定一个无向图，共 $T$ 条边，第 $i$ 条边连接交叉路口 $I_{1,i}$ 与 $I_{2,i}$、长度为 $\text{len}_i$；求从起点 $S$ 到终点 $E$ 恰好经过 $N$ 条边的最短行走（walk，允许重复经过点和边）长度：

$$ \min_{v_0=S,\; v_N=E,\; \forall k\,(v_{k-1},v_k)\in E}\ \sum_{k=1}^{N} \text{len}(v_{k-1},v_k) $$

数据范围：$1\le N\le 10^6$，$2\le T\le 100$，点编号 $\le 1000$，$1\le \text{len}_i\le 1000$，无重边无自环，每个点至少是两条边的端点。

这正是上文 $(\min,+)$ 框架的直接应用：把无向边写成对称的"恰好 1 条边"距离矩阵，答案即 $(G^{\odot N})_{S,E}$。一个实现细节是点编号到 $1000$ 但实际出现的路口至多 $2T\le 200$ 个，需要离散化压缩，否则 $O(1000^3\log N)$ 会超时，压缩后为 $O(T^3\log N)$。

参考资料 && 拓展阅读 && 推荐题目

  • OI Wiki 矩阵
  • 《算法竞赛进阶指南》，李煜东著，0x34 矩阵乘法

推荐题目：

  • P1349 广义斐波那契数列 提示：构造转移矩阵
  • P3193 [HNOI2008] GT考试 提示：KMP + 矩阵快速幂
  • P2151 [SDOI2009] HH去散步 提示：把边转化为点后矩阵快速幂
  • P4159 [SCOI2009] 迷路 提示：边权大于 1，按边权拆点后矩阵快速幂
  • P3758 [TJOI2017] 可乐 提示：停留、自爆都是状态转移，矩阵快速幂
  • P2579 [ZJOI2005] 沼泽鳄鱼 提示：障碍按周期变化，预处理各时刻转移矩阵分段快速幂
  • P6772 [NOI2020] 美食家 提示：拆点 + 矩阵快速幂（$(\max, +)$）
动态规划线性代数矩阵乘法快速幂最短路Fibonacci数列
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

本站由 zaochen 使用 Stellar 1.44.0 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
全站访问量 - 次 · 访客数 - 人 · 本页面浏览 - 次