
矩阵在竞赛里有两种用途。一种是把线性递推式写成矩阵乘法,再用快速幂把 O(n) 的递推降到 O(\log n);另一种是解线性方程组。两者都建立在一个基础运算上:矩阵乘法。
本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。
| 考试 | 大纲要求 | 本章位置 |
|---|---|---|
| NOI 提高级 | 2.5.4 线性代数:向量与矩阵的概念、向量的运算、矩阵的初等变换、矩阵的运算(加减乘与转置)、特殊矩阵、高斯消元法 | 全章 |
向量
向量是一组有序的数。二维向量 (x, y) 可以看成一个点,也可以看成从原点出发的一个箭头。
基本运算:
| 运算 | 定义 | 几何意义 |
|---|---|---|
| 加法 | (x_1 + x_2, y_1 + y_2) |
首尾相接 |
| 数乘 | k(x, y) = (kx, ky) |
方向不变,长度变成 k 倍 |
| 点积 | (x_1, y_1) \cdot (x_2, y_2) = x_1x_2 + y_1y_2 |
= 0 表示两向量垂直 |
| 模 | \sqrt{x^2 + y^2} |
向量的长度 |
点积的几何意义是 |a||b|\cos\theta,所以点积为零就是夹角 90^\circ。它在判断垂直、算投影时很有用。
矩阵的概念与运算
矩阵是排成矩形的数表。n 行 m 列的矩阵记作 n \times m 的矩阵,第 i 行第 j 列的元素记作 a_{ij}。
加法与数乘
两个同型矩阵相加,对应位置相加;矩阵乘一个数,每个元素都乘这个数。这两种运算都很直观。
转置
把矩阵的行和列互换,得到转置矩阵,记作 A^T。n \times m 的矩阵转置后是 m \times n。
乘法
矩阵乘法规则稍复杂,也是最重要的一个:
C_{ij} = \sum_{k=1}^{p} A_{ik} \times B_{kj}
其中 A 是 n \times p 的矩阵,B 是 p \times m 的矩阵,乘积 C 是 n \times m 的矩阵。左矩阵的列数必须等于右矩阵的行数,否则不能相乘。
一句话记忆:结果的第 i 行第 j 列,等于左矩阵第 i 行与右矩阵第 j 列逐项相乘再求和。
struct Matrix {
static const int N = 105;
long long a[N][N];
int n;
Matrix(int n = 0) : n(n) { memset(a, 0, sizeof(a)); }
};
Matrix mul(const Matrix &A, const Matrix &B, long long mod) {
Matrix C(A.n);
for (int i = 0; i < A.n; i++) {
for (int k = 0; k < A.n; k++) {
if (A.a[i][k] == 0) continue; // 跳过零元素,稀疏时能省不少时间
for (int j = 0; j < A.n; j++) {
C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % mod;
}
}
}
return C;
}三重循环的次序写成 i, k, j 而不是 i, j, k,是因为这样访问内存更连续,速度更快,而且能顺手跳过零元素。
矩阵乘法不满足交换律:一般情况下 AB \neq BA。这一点和普通乘法不同,推导时要注意顺序。它满足结合律,这正是快速幂能用的前提。
特殊矩阵
| 名称 | 特征 |
|---|---|
| 零矩阵 | 所有元素都是 0 |
单位矩阵 I |
主对角线是 1,其余是 0;AI = IA = A |
| 对角矩阵 | 除主对角线外都是 0 |
| 上(下)三角矩阵 | 主对角线一侧全为 0 |
| 对称矩阵 | 满足 a_{ij} = a_{ji},即 A^T = A |
| 稀疏矩阵 | 大部分元素为 0 |
单位矩阵在矩阵快速幂里的角色,相当于数字 1 在普通快速幂里的角色,是初始的「答案矩阵」。
矩阵快速幂
这是矩阵在竞赛里最主要的用途。以斐波那契数列为例:
F_n = F_{n-1} + F_{n-2}
把状态写成向量 \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix},那么递推可以写成一次矩阵乘法:
\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix}
不断展开,就得到
\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-1} \begin{pmatrix} F_1 \\ F_0 \end{pmatrix}
矩阵的幂可以用快速幂在 O(\log n) 内算出来,于是 F_n 的计算从 O(n) 降到 O(\log n)。n 到 10^{18} 时,普通循环不可能跑完,矩阵快速幂却能秒出。
Matrix mpow(Matrix base, long long e, long long mod) {
int n = base.n;
Matrix res(n);
for (int i = 0; i < n; i++) res.a[i][i] = 1; // 单位矩阵
while (e > 0) {
if (e & 1) res = mul(res, base, mod);
base = mul(base, base, mod);
e >>= 1;
}
return res;
}用法和普通快速幂完全一样,只是把「乘」换成了矩阵乘法,「1」换成了单位矩阵。
任何形如
f(n) = c_1 f(n-1) + c_2 f(n-2) + \cdots + c_k f(n-k)
的线性递推,都能用矩阵快速幂加速,构造出 k \times k 的转移矩阵即可。
高斯消元
高斯消元用来解线性方程组:
\begin{cases}
a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1 \\
a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2 \\
\vdots \\
a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n = b_n
\end{cases}
把系数和常数项写成增广矩阵,然后做初等行变换(交换两行、某行乘非零常数、把一行的倍数加到另一行),这些变换不改变方程组的解。
步骤是:
- 在当前列找一个非零元素作为主元。
- 把主元所在行换到当前处理的行。
- 用这一行把该列其它行的元素消成 0。
- 处理下一列。
消完以后矩阵接近单位阵,解就出来了。
const double EPS = 1e-9;
double a[105][105]; // 增广矩阵,第 n 列是常数项
int n;
bool gauss() {
for (int col = 0; col < n; col++) {
// 选列主元:当前列绝对值最大的那一行
int pivot = col;
for (int i = col + 1; i < n; i++) {
if (fabs(a[i][col]) > fabs(a[pivot][col])) pivot = i;
}
if (fabs(a[pivot][col]) < EPS) return false; // 这一列全是 0,无唯一解
for (int j = 0; j <= n; j++) swap(a[col][j], a[pivot][j]);
double div = a[col][col];
for (int j = col; j <= n; j++) a[col][j] /= div; // 主元化成 1
for (int i = 0; i < n; i++) {
if (i == col) continue;
double factor = a[i][col];
if (fabs(factor) < EPS) continue;
for (int j = col; j <= n; j++) a[i][j] -= factor * a[col][j];
}
}
return true; // 此时 a[i][n] 就是 x_i
}上面第一步就是列主元:不是随便找一个非零元素,而是在当前列中挑绝对值最大的那一个。如果直接用第一个非零元素,一旦它很小(比如 10^{-8}),后面要拿它作除数,误差会被放大很多倍。
代码里把主元化成 1、再消掉该列所有其它元素,这种做法叫高斯-约当消元,比「先消成上三角、再回代」写起来更短。
复杂度
| 运算 | 复杂度 |
|---|---|
| 矩阵加法、转置 | O(n^2) |
矩阵乘法(n \times n) |
O(n^3) |
| 矩阵快速幂 | O(n^3 \log k) |
| 高斯消元 | O(n^3) |
朴素矩阵乘法是 O(n^3),所以转移矩阵的阶数不能太大。n = 100 时一次乘法就是 10^6 次运算,\log k 次下来还算能接受;n 到 500 就悬了。
常见易错点
- 矩阵乘法要求左矩阵的列数等于右矩阵的行数,维度对不上直接乘不了。
- 矩阵乘法没有交换律,
AB和BA一般不同,递推顺序写反结果就错。 - 快速幂的初始矩阵必须是单位矩阵,不是全零矩阵。
- 取模时注意中间结果溢出,两个
10^9级别的数相乘要用long long。 - 高斯消元没有选列主元,浮点误差会累积到解完全不能用。
- 用
fabs(x) < EPS判断浮点数的零,不能写x == 0。
初赛选择题精选
下面 8 道题中,题 1 选自 GESP 八级真题,其余 7 道按本章考点编写。向量的运算(点积、叉积)在《平面几何基础》那一章有专门的真题解析,这里不重复。
题 1(GESP 八级,2023 年 12 月)
使用邻接矩阵表达 n 个顶点的有向图,则该矩阵的大小为( )。
A. n B. n \times n C. \dfrac{n(n-1)}{2} D. \dfrac{n(n+1)}{2}
答案:B
解析:邻接矩阵是 n 行 n 列的方阵,a_{ij} 表示从 i 到 j 有没有边。不管图是稀疏还是稠密,都要占 n^2 个位置,这也是它相比邻接表的劣势。
题 2(矩阵乘法·维度)
已知 A 是 3 \times 4 的矩阵,B 是 4 \times 5 的矩阵,则 A \times B 是( )。
A. 3 \times 4 B. 4 \times 5 C. 3 \times 5 D. 不能相乘
答案:C
解析:左矩阵的列数(4)等于右矩阵的行数(5),可以相乘;结果的行数取自左矩阵(3),列数取自右矩阵(5),所以是 3 \times 5。
题 3(单位矩阵与对称矩阵)
设 I 是 n 阶单位矩阵,下列关于它的说法错误的是( )。
A. 主对角线上的元素都是 1
B. 其余位置的元素都是 0
C. 对任意可以进行乘法的矩阵 A,都有 AI = IA = A
D. 单位矩阵的转置不再是单位矩阵
答案:D
解析:单位矩阵是对称矩阵,转置之后还是它自己。A、B、C 都是单位矩阵的基本性质。
题 4(矩阵乘法的性质)
关于矩阵乘法,下列说法正确的是( )。
A. 满足交换律 B. 满足结合律
C. 只有方阵之间才能相乘 D. 结果矩阵的行数等于右矩阵的行数
答案:B
解析:矩阵乘法满足结合律 (AB)C = A(BC),这正是快速幂能用的前提;但不满足交换律,AB 和 BA 一般不等。维度只要求左矩阵的列数等于右矩阵的行数,不必是方阵;结果矩阵的行数等于左矩阵的行数。
题 5(单位矩阵的作用)
设 I 是 n 阶单位矩阵,A 是任意的 n \times n 矩阵,则下列正确的是( )。
A. AI = A,且 IA = A B. AI = I,且 IA = I
C. A + I = A D. AI \neq IA
答案:A
解析:单位矩阵在矩阵乘法里的作用相当于数字 1。加法不满足这个性质,A + I \neq A;AI 和 IA 都等于 A,所以 D 也不对。
题 6(矩阵快速幂复杂度)
用矩阵快速幂求斐波那契数列的第 n 项(n \le 10^{18}),时间复杂度是( )。
A. O(n) B. O(\log n) C. O(n \log n) D. O(n^3)
答案:B
解析:斐波那契的转移矩阵是 2 \times 2 的常数矩阵,一次矩阵乘法是 O(1),一共做 O(\log n) 次。如果递推式要开 k 阶矩阵,就是 O(k^3 \log n)。
题 7(矩阵转置)
设 A 是一个 3 \times 4 的矩阵,则它的转置矩阵 A^T 的维度是( )。
A. 3 \times 4 B. 4 \times 3 C. 3 \times 3 D. 4 \times 4
答案:B
解析:转置就是把矩阵的行列互换,A^T_{ij} = A_{ji}。所以 3 \times 4 的矩阵转置后变成 4 \times 3。
两个要记住的性质:
(A^T)^T = A(转置两次回到原样);(AB)^T = B^T A^T(注意顺序要反过来,这是最容易错的地方)。
题 8(高斯消元与行列式)
用高斯消元法解 n 元线性方程组,时间复杂度是( )。
A. O(n) B. O(n^2) C. O(n^3) D. O(n^4)
答案:C
解析:高斯消元有两层结构:对每一行(n 次)都要消去它下面所有行的对应列(每次 O(n) 行 × O(n) 列),所以是 O(n^3)。
直观理解:消元过程要处理的是一个 n \times n 的系数矩阵,每次消元都要更新矩阵的一个 O(n^2) 的子块,一共 n 轮,合计 O(n^3)。
和矩阵快速幂的区别:矩阵快速幂是 O(k^3 \log n)(k 是矩阵阶数,\log n 来自快速幂),高斯消元是 O(n^3)(n 是方程个数)。两者的 n^3 含义不同,别混。
练习
练习 1:矩阵乘法
题目描述
给定两个矩阵 A(n \times m)和 B(m \times k),求 A \times B。
输入格式
第一行三个整数 n、m、k;接下来 n 行,每行 m 个整数,表示矩阵 A;再接下来 m 行,每行 k 个整数,表示矩阵 B。
输出格式
输出 n 行,每行 k 个整数,表示乘积矩阵。
数据范围
1 \le n, m, k \le 100,矩阵元素的绝对值不超过 1000。
输入输出样例
输入
2 3 2
1 2 3
4 5 6
7 8
9 10
11 12输出
58 64
139 154题目分析
按定义直接三重循环。结果矩阵是 n \times k 的,计算 C_{ij} 时把 A 的第 i 行和 B 的第 j 列对应相乘再相加。
要注意数组的下标范围:A 要用 [n][m],B 要用 [m][k],结果用 [n][k],三者不能混。
参考代码
练习 2:斐波那契数列第 n 项
题目描述
求斐波那契数列第 n 项对 10^9 + 7 取模的结果。规定 F_1 = F_2 = 1。
输入格式
一个整数 n。
输出格式
输出一个整数,表示 F_n \bmod (10^9+7)。
数据范围
1 \le n \le 10^{18}。
输入输出样例
输入
10输出
55题目分析
n 到 10^{18},递推循环肯定跑不完,要用矩阵快速幂。
\begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-1} \begin{pmatrix} F_1 \\ F_0 \end{pmatrix}
把转移矩阵的 n-1 次幂用快速幂算出来,取结果矩阵的左上角元素即可。
参考代码
练习 3:解线性方程组
题目描述
给定一个 n 元线性方程组的增广矩阵,解出 n 个未知数。保证有唯一解。
输入格式
第一行一个整数 n;接下来 n 行,每行 n+1 个实数,表示增广矩阵。
输出格式
输出 n 行,每行一个实数,表示对应未知数的值,保留两位小数。
数据范围
1 \le n \le 100。
输入输出样例
输入
3
1 1 1 6
0 2 5 -4
2 5 -1 27输出
5.00
3.00
-2.00题目分析
高斯-约当消元的标准题。每一步选当前列绝对值最大的行做列主元,把主元化成 1,再消掉该列其余所有位置。消完以后最后一列就是答案。
判断「这一列全为 0」用 fabs(x) < EPS,不能写 x == 0。
参考代码
练习 4(进阶):定长路径计数
题目描述
给定一个有向图的邻接矩阵 A(a_{ij} = 1 表示 i 到 j 有一条边),求从顶点 1 到顶点 n、长度(边数)恰好为 k 的路径条数,对 10^9+7 取模。
输入格式
第一行两个整数 n、k;接下来 n 行,每行 n 个整数(0 或 1),表示邻接矩阵。
输出格式
输出一个整数,表示路径条数对 10^9+7 取模的结果。
数据范围
1 \le n \le 50,1 \le k \le 10^9。
输入输出样例
输入
3 3
0 1 1
1 0 1
1 1 0输出
3从 1 到 3、长度恰好为 3 的路径有 1→2→1→3、1→3→1→3、1→3→2→3,共 3 条。
题目分析
矩阵乘法还有一个很漂亮的性质:A^k 的第 i 行第 j 列,就是「从 i 到 j 长度为 k 的路径条数」。
道理在定义里:(A^k)_{ij} = \sum_t (A^{k-1})_{it} A_{tj},即「先走 k-1 步到 t,最后一步从 t 到 j」,把所有中间点 t 的情况加起来。
所以只要把邻接矩阵做 k 次幂就行,k 到 10^9 用矩阵快速幂,复杂度 O(n^3 \log k)。
参考代码
小结
矩阵在竞赛里的价值在于把递推变成幂运算:只要能写成 f(n) = c_1 f(n-1) + \cdots + c_k f(n-k),就能用 k \times k 的转移矩阵加快速幂把 O(n) 降到 O(k^3 \log n)。
- 向量有点积和叉积,点积判断垂直,叉积判断共线与方向。
- 矩阵乘法
C_{ij} = \sum_k A_{ik} B_{kj},满足结合律但不满足交换律。 - 单位矩阵是矩阵乘法里的「1」,也是快速幂的初始值。
- 线性递推写成矩阵乘法后可以用快速幂加速;
A^k还能数出长度固定的路径条数。 - 高斯消元解线性方程组,写的时候一定要选列主元。
学完这一章,下面这些事应该能独立完成:
- 写出矩阵乘法的三重循环,并说清维度对齐的条件。
- 说清矩阵乘法为什么能用快速幂(结合律),为什么不能随意交换顺序。
- 把斐波那契一类线性递推写成转移矩阵,并写出矩阵快速幂的代码。
- 写出带列主元的高斯消元,并说清为什么不能直接用第一个非零元素。
- 说清「
A^k的元素是定长路径条数」这个结论的道理。