向量与矩阵：概念、运算与初等变换 | 王心俊老师信息学奥赛课件

板块	核心内容	对应大纲
向量概念	n 维有序数组，行列向量记号	【5】向量与矩阵的概念
向量运算	加减、数乘、点积、叉积	【6】向量的运算
矩阵概念	m×n 数表，a_ij 下标约定	【5】向量与矩阵的概念
矩阵加减数乘	同型矩阵逐元素运算	【6】矩阵的运算
矩阵乘法	行乘列，结合律成立交换律不成立	【6】矩阵的运算
转置	(AB)^T = B^TA^T	【6】矩阵的运算
特殊矩阵	单位阵、三角阵、对称阵、稀疏矩阵	【6】特殊矩阵
初等行变换	换行 / 倍乘 / 倍加，与初等矩阵	【6】矩阵的初等变换
矩阵快速幂	O(n³ log k) 求矩阵幂，加速递推	【6】矩阵的运算

模块 02

知识探究

先认识向量与矩阵的记号，再把乘法规则、转置性质、特殊矩阵、初等变换一一打通，最后落到矩阵快速幂。

1向量的概念与运算基础

向量就是"一串有序的数"。在几何里它表示一个有方向的量（箭头）；在 OI 里它常常就是一个数组，或者一个"1 列的矩阵"。

运算	定义	示例	结果类型
加法	逐分量相加	(1,2,3) + (4,5,6) = (5,7,9)	向量
减法	逐分量相减	(1,2,3) − (4,5,6) = (−3,−3,−3)	向量
数乘	每个分量乘 k	2·(1,2,3) = (2,4,6)	向量
点积	对应分量相乘再求和	(1,2,3)·(4,5,6) = 4+10+18 = 32	标量
叉积	仅 3 维定义，结果垂直于两向量	见下方公式	向量

➡️ 点积与叉积的几何意义

点积（内积）：a·b = |a||b|cos θ。它测的是两个向量的"同向程度"。

· a·b > 0 ⟺ 夹角是锐角；= 0 ⟺ 垂直；< 0 ⟺ 钝角。这是判断垂直与投影的利器。

· 竞赛应用：判断向量夹角、求投影长度、计算"点在直线哪一侧"。

叉积（外积，仅三维）：a × b = (a₂b₃ − a₃b₂, a₃b₁ − a₁b₃, a₁b₂ − a₂b₁)，结果是一个垂直于 a 和 b 的向量。

· 它的模 |a × b| = |a||b|sin θ 等于两向量张成的平行四边形面积。

· 二维情形下人们常用叉积的 z 分量（即 a₁b₂ − a₂b₁）判断"点在直线的哪一侧"，符号为正表示逆时针方向。这是计算几何里判凸包、判线段相交的核心工具。

注意：点积的结果是标量（一个数），叉积的结果是向量。竞赛代码里"叉积判左右"实际用的是它的 z 分量（也是个标量）。

2矩阵的定义与记号基础

🔲 一个 3×4 矩阵的示意（m = 3 行，n = 4 列）

a₁₁1

a₁₂2

a₁₃3

a₁₄4

a₂₁5

a₂₂6

a₂₃7

a₂₄8

a₃₁9
a₃₂10
a₃₃11
a₃₄12

记号：A_3×4 = (a_ij)，i 是行号、j 是列号。代码里就是 a[3][4] 数组

📝 记号约定（很重要，容易写反）

· a_ij：第 i 行第 j 列的元素。C++ 里习惯按 a[i][j] 存，但用 1-indexed 更贴合数学记号；竞赛代码里两者都有，务必先确认下标约定。

· A_m×n 表示 m 行 n 列的矩阵。两个矩阵"同型"指行列数都相同。

· 方阵：m = n 的矩阵。只有方阵才能求幂、求逆、求行列式。

· 行列向量：把 n 个数竖着排叫列向量（n×1），横着排叫行向量（1×n）。在递推加速中通常用列向量，写成 M·v。

3矩阵的加减与数乘简单但易错

➕ 加法与减法

只有同型（行列数完全相同）的矩阵才能相加减，规则是逐元素运算：

(A ± B)_ij = a_ij ± b_ij

交换律、结合律都成立：A + B = B + A，(A + B) + C = A + (B + C)。

✖️ 数乘

常数 k 乘矩阵，就是每个元素都乘 k：(kA)_ij = k·a_ij。

满足分配律：k(A + B) = kA + kB，(k + t)A = kA + tA，k(tA) = (kt)A。

⚠️ 与乘法的区别：数乘是"每个元素都乘"，而矩阵乘法是"行乘列求和"，两者完全不同！初学者最容易把 k*A 和 A*B 混为一谈。

✅ 数乘：全员乘 k

3 × [[1,2],[3,4]] = [[3,6],[9,12]]

每个位置的元素独立相乘，互不影响。

❌ 误以为矩阵乘法也是逐位相乘

[[1,2],[3,4]] × [[1,2],[3,4]] 不等于 [[1,4],[9,16]]。

正确结果是 [[7,10],[15,22]]（行乘列求和）。

4矩阵乘法（行乘列）核心

矩阵乘法是整讲的灵魂。规则只有一句：用左矩阵的第 i 行，去点乘右矩阵的第 j 列，得到结果的第 (i,j) 个元素。

取左第1行

取右第1列

对应相乘

再求和

填 C[1][1]

换下一列

取数路径当前步骤

✖️ 完整的乘法定义

设 A 是 m×p 的矩阵，B 是 p×n 的矩阵，则 C = A·B 是 m×n 的矩阵，且

c_ij = Σ_k=1..p a_ik · b_kj

维度口诀：「中间的 p 要相等，结果取 m×n」。写作 (m×p)·(p×n) = m×n —— 中间那个 p 必须对上，结果就是两头的数。这个口诀能让你 3 秒内判断乘法是否合法。

计算量：结果有 m·n 个元素，每个元素要算 p 次乘法加法，所以总复杂度 O(m·n·p)。方阵 (n×n)·(n×n) 就是 O(n³)。

🧮 手算演示：A = [[1,2],[3,4]]，B = [[5,6],[7,8]]

计算 C = A·B 的第 (1,1) 个元素：取 A 的第 1 行 [1, 2]，取 B 的第 1 列 [5, 7]：

A₁₁1

A₁₂2

B₁₁5

B₂₁7

c₁₁ = 1×5 + 2×7 = 5 + 14 = 19

同理：c₁₂ = 1×6 + 2×8 = 22；c₂₁ = 3×5 + 4×7 = 43；c₂₂ = 3×6 + 4×8 = 50。所以

C = [[19, 22], [43, 50]]

运算律	是否成立	说明
结合律 (AB)C = A(BC)	✔ 成立	变换复合的顺序天然满足，可放心用快速幂
分配律 A(B+C) = AB+AC	✔ 成立	与实数一致
交换律 AB = BA	✘ 一般不成立	"先转再缩" ≠ "先缩再转"
消去律 AB = AC ⇒ B = C	✘ 不成立	A 可能不可逆（行列式为 0）
AB = 0 ⇒ A=0 或 B=0	✘ 不成立	两个非零矩阵相乘可以是零矩阵

C++矩阵乘法模板（带维度检查与取模）

struct Mat {
    int n, m;                       // n 行 m 列
    long long a[105][105];
    Mat(int _n = 0, int _m = 0) : n(_n), m(_m) {
        memset(a, 0, sizeof(a));   // 全零初始化
    }
};
const long long MOD = 1000000007;

Mat operator*(const Mat& A, const Mat& B) {
    if (A.m != B.n) { cerr << "维度不匹配，无法相乘" << endl; exit(1); }
    Mat C(A.n, B.m);                // 结果：A.n 行 B.m 列
    for (int i = 0; i < A.n; i++)
        for (int k = 0; k < A.m; k++) {          // 先枚举 k，cache 友好
            long long t = A.a[i][k];
            if (!t) continue;                     // 稀疏优化
            for (int j = 0; j < B.m; j++)
                C.a[i][j] = (C.a[i][j] + t * B.a[k][j]) % MOD;
        }
    return C;
}

运行结果

A = [[1,2],[3,4]]   B = [[5,6],[7,8]]
A*B = [[19,22],[43,50]]
B*A = [[23,34],[31,46]]      ← 与 A*B 不同，验证了交换律不成立 ✔

维度检查：(2×3)·(3×4) → 合法，结果 2×4
          (2×3)·(2×4) → 报错：A.m=3 ≠ B.n=2

💡 i→k→j 的循环顺序比 i→j→k 更快，因为它对 B 的访问是连续的内存行

5转置与特殊矩阵高频考点

🔄 转置的性质（竞赛常考）

· (A^T)^T = A （转两次回来）

· (A + B)^T = A^T + B^T （加法可交换）

· (AB)^T = B^TA^T （重点顺序要颠倒！这是最常考的陷阱）

· (kA)^T = kA^T （数乘可以直接提出来）

为什么 (AB)^T 要颠倒？取 (AB)^T 的 (i,j) 元素 = AB 的 (j,i) 元素 = A 的第 j 行点乘 B 的第 i 列。而 B^TA^T 的 (i,j) 元素 = B^T 的第 i 行（即 B 的第 i 列）点乘 A^T 的第 j 列（即 A 的第 j 行）—— 两者相等 ✔

特殊矩阵	定义	记忆点	竞赛用途
零矩阵 O	所有元素都是 0	加法单位元（A + O = A）	初始化
单位阵 I	主对角线为 1，其余为 0	A·I = I·A = A（乘法单位元）	快速幂的起点
上三角阵	i > j 时 a_ij = 0（左下角全 0）	消元后的阶梯型	高斯消元的目标形态
下三角阵	i < j 时 a_ij = 0（右上角全 0）	与上三角互为转置	前向代入求解
对称阵	A = A^T，即 a_ij = a_ji	"沿主对角线镜像相同"	无向图的邻接矩阵
反对称阵	A = −A^T，即 a_ij = −a_ji	主对角线必为 0	有向图 / 叉积矩阵
稀疏矩阵	非零元素极少（远小于 n²）	别用二维数组存！	邻接表、三元组、CSR

🗜️ 稀疏矩阵怎么存？

如果一个 10⁵×10⁵ 的矩阵只有 2×10⁵ 个非零元素，直接开二维数组需要 10¹⁰ 个格子，内存爆掉。常见三种压缩存储：

· 三元组表：存 (行, 列, 值) 三个数组。简单直观，适合稀疏矩阵的转置与乘法。

· 邻接表：每行一个 vector，存 (列号, 值)。这是图上最常用的形式。

· CSR（行压缩存储）：用 val[]、col[]、rowptr[] 三个数组表示，内存最省、遍历最快，很多图算法库都用它。

⭐ 一个重要事实：在图上，"邻接矩阵的 k 次方"的第 (i,j) 元恰好等于"从 i 到 j 长度恰为 k 的路径条数"。这让矩阵快速幂能解决大量路径计数问题（本讲题 3 会实现）。

6矩阵加速线性递推 OI 核心应用

这是矩阵在 OI 中最有价值的应用。核心思想：把"递推关系"写成"矩阵乘以状态向量"，然后求矩阵的 n 次幂。

🧩

确定状态

把递推需要的历史量打包成向量

🔲

构造矩阵

写出"下一状态 = M × 当前状态"

⚡

快速幂

算 M^k，O(n³ log k)

✅

乘初始向量

得第 k 项，取所需分量

♻️ 以斐波那契为例：f(n) = f(n−1) + f(n−2)

第1步：确定状态。递推式用到 f(n−1) 和 f(n−2) 两个历史值，所以状态向量取 (f(n), f(n−1))^T。

第2步：构造矩阵。我们希望 (f(n), f(n−1))^T = M · (f(n−1), f(n−2))^T。展开看：第一行要产生 f(n−1) + f(n−2)，所以是 [1, 1]；第二行要原样保留 f(n−1)，所以是 [1, 0]。于是

M = [[1, 1], [1, 0]]

第3步：迭代。记 v₁ = (f(1), f(0))^T = (1, 1)^T，则 v_n = Mⁿ⁻¹ · v₁，所以 f(n) 就是 Mⁿ⁻¹·(1,1)^T 的第一个分量。

第4步：复杂度。矩阵快速幂需要 O(log n) 次 2×2 矩阵乘法，每次 8 次乘加，总复杂度 O(log n)。相比朴素递推的 O(n)，n = 10¹⁸ 时差距是天文数字。

递推式	状态向量（列）	转移矩阵 M	阶数
f(n)=f(n−1)+f(n−2)	(f(n−1), f(n−2))ᵀ	[[1,1],[1,0]]	2
f(n)=p·f(n−1)+q·f(n−2)	(f(n−1), f(n−2))ᵀ	[[p,q],[1,0]]	2
f(n)=f(n−1)+f(n−2)+c	(f(n−1), f(n−2), 1)ᵀ	[[1,1,c],[1,0,0],[0,0,1]]	3
f(n)=f(n−1)+f(n−3)	(f(n−1), f(n−2), f(n−3))ᵀ	[[1,0,1],[1,0,0],[0,1,0]]	3
f(n)=Σ_i=1..k f(n−i)	k 个历史值	首行全 1 + 次对角线 1	k

🧠 构造转移矩阵的三条通用技巧

① "谁出现在递推式右边，谁就进状态向量"。递推用了 f(n−1)、f(n−2)、常数 c，状态就是 (f(n−1), f(n−2), c)。

② 常数项的处理：把常数 1 放进状态向量的最后一位，并在矩阵对应列填上常数系数（如上面的 c）。这一招能处理带常数项、带 n 的递推 —— 若含 n，就把 n 也放进状态，转移时实现 n → n+1。

③ 需要"前缀和"时，把和也放进状态。例如要求 S(n) = Σ_i≤n f(i)，就令状态为 (f(n), f(n−1), S(n))，转移矩阵中 S 那一行把 f(n) 加进去。

7初等行变换与初等矩阵下一讲的基石

矩阵的初等变换只有三种，对应着解方程组时最自然的三个动作：

#	名称	操作	解方程组的对应动作
1	交换变换	交换第 i 行与第 j 行：r_i ↔ r_j	把两个方程换个位置
2	倍乘变换	第 i 行整体乘以非零常数 k：r_i ← k·r_i	方程两边同乘 k（k ≠ 0）
3	倍加变换	把第 j 行的 k 倍加到第 i 行：r_i ← r_i + k·r_j	方程相加消元

🔧 为什么这三种变换"不改变解集"？

因为每一种都对应着方程组上的等价变形：换行只是换了方程的顺序（解集当然不变）；倍乘是把一个方程两边同乘非零数（等价方程）；倍加是把一个方程加上另一个方程的倍数（新方程是原方程的线性组合，任何满足原方程组的解仍满足新方程，反之亦然）。

重要结论：初等行变换不改变矩阵的秩，也不改变方程组的解集。这就是高斯消元能做下去的根本保证。

🧱 初等矩阵：把变换"写成矩阵"

对单位阵 I 做一次初等行变换，得到的矩阵就叫初等矩阵 E。它有一个漂亮的性质：

用 E 左乘 A（即 E·A），效果等同于"对 A 做同一种初等行变换"

· 交换 i、j 两行得到的初等矩阵，左乘 A 就交换 A 的第 i、j 行；

· 第 i 行乘 k 得到的初等矩阵，左乘 A 就让 A 的第 i 行整体乘 k；

· 把第 j 行的 k 倍加到第 i 行得到的初等矩阵，左乘 A 就执行同样的倍加操作。

为什么有用？因为初等矩阵都可逆，整条高斯消元过程可以写成 E_t···E₂E₁A = U（U 是上三角阵）。求逆矩阵、求行列式、LU 分解都建立在这个式子上。下一讲 s6-11 高斯消元法，本质就是这一串初等矩阵连乘的算法实现。

列变换：同理也有初等列变换，对应"右乘初等矩阵"。竞赛中通常只做行变换（因为行变换保持方程组的解）。

🔧 用初等行变换把增广矩阵化成上三角（下一讲预告）

原始增广矩阵（三个方程三个未知数）：

r₁2

−1

r₂−3

−1

−11

r₃−2

−3

执行 r₂ ← r₂ + 1.5·r₁、r₃ ← r₃ + r₁ 后，第一列下方变 0 —— 这就是"消元"的第一步

三步消元后得到上三角（阶梯型），再从最后一行往上回代即可解出 x₃, x₂, x₁

阶梯型 → 回代 → 解出全部未知数，这就是下一讲的主线

8矩阵快速幂核心算法

矩阵快速幂就是把整数的"快速幂"原封不动搬到矩阵上。整数快速幂靠的是乘法结合律，而矩阵乘法同样满足结合律，所以算法完全一样。

🎬 交互演示：计算 M¹³ 的平方累乘过程

1目标：求 M¹³。把指数转成二进制：13 = 1101₂ = 8 + 4 + 1。答案是 M¹³ = M⁸ · M⁴ · M¹。

2初始化：结果矩阵 res = I（单位阵），底数矩阵 base = M，指数 b = 13 = 1101₂。

3第 1 位（b 最低位 = 1）：是 1，所以 res = res · base = M¹。然后 base = base · base = M²，b >>= 1 变成 110₂。

4第 2 位（110 的低位 = 0）：是 0，跳过乘法。只做 base = base² = M⁴，b >>= 1 变成 11₂。

5第 3 位（11 的低位 = 1）：是 1，res = res · base = M¹ · M⁴ = M⁵。然后 base = base² = M⁸，b >>= 1 变成 1₂。

6第 4 位（= 1）：是 1，res = res · base = M⁵ · M⁸ = M¹³。然后 base = base² = M¹⁶，b >>= 1 变 0，循环结束。

7结果：res = M¹³ ✔。全程只做了约 2·log₂13 ≈ 8 次矩阵乘法，而朴素累乘需要 13 次。指数越大，优势越明显（10¹⁸ 时只需约 60 轮）。

💡 每个循环里"平方"是必做的，"乘入 res"只在当前二进制位为 1 时做 —— 这就是二进制幂的精髓。

C++矩阵快速幂通用模板

const int SZ = 105;                  // 矩阵最大阶数

struct Mat {
    long long a[SZ][SZ];
    Mat() { memset(a, 0, sizeof(a)); }
};

int N;                              // 当前矩阵的实际阶数
const long long MOD = 1000000007;

Mat mul(const Mat& A, const Mat& B) {
    Mat C;
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++) {
            if (!A.a[i][k]) continue;
            for (int j = 0; j < N; j++)
                C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % MOD;
        }
    return C;
}

Mat matpow(Mat base, long long b) {
    Mat res;                                  // 初始化为单位阵 I
    for (int i = 0; i < N; i++) res.a[i][i] = 1;
    while (b > 0) {
        if (b & 1) res = mul(res, base);      // 当前位为 1 → 乘入结果
        base = mul(base, base);                 // 平方
        b >>= 1;                               // 右移一位
    }
    return res;
}

运行结果

N = 2，M = [[1,1],[1,0]]
matpow(M, 10) = [[89,55],[55,34]]
  说明：斐波那契数列 F₁..F₁₁ = 1,1,2,3,5,8,13,21,34,55,89
       M¹⁰ 的左上角 = F₁₁ = 89 ✔（因为 Mⁿ = [[F_{n+1},F_n],[F_n,F_{n-1}]]）

matpow(M, 1000000000000000000) 的指数循环只跑约 60 轮
  → 总共约 120 次 2×2 矩阵乘法，瞬间完成（朴素递推需要 10¹⁸ 次）

单位阵验证：matpow(M, 0) = I = [[1,0],[0,1]] ✔

案例案例1：手写矩阵乘法并验证交换律基础

题目：读入两个 n×n 矩阵 A、B（n ≤ 100，元素 0 ≤ a_ij ≤ 10⁹），计算并输出 A·B 与 B·A，验证交换律是否成立。

🔍 详细分析过程

第1步：显式维护格式。用 Mat 结构体存 a[n][n] 与阶数 n，乘法函数中三重循环 i→k→j。

第2步：为什么用 i→k→j 而不是 i→j→k？因为最内层循环访问 B.a[k][j] 是连续内存（行主序），cache 命中率高；而 i→j→k 最内层访问 B.a[k][j] 是跨行的，命中率低。n = 100 时差距约 2~3 倍，n = 500 时差距更明显。

第3步：取模。元素最大 10⁹，做 100 次乘加会达到 10²⁰ 量级，超过 long long（9.2×10¹⁸）。所以每加一次就要取模，或者用 __int128。

第4步：验证交换律。输出 A·B 和 B·A 对比，你会发现绝大多数情况下它们不同。

复杂度：两次乘法，各 O(n³)，n = 100 时约 2×10⁶ 次运算。

C++手写矩阵乘法 — 完整代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int MAXN = 105;

int n;
ll A[MAXN][MAXN], B[MAXN][MAXN], C[MAXN][MAXN], D[MAXN][MAXN];

void multiply(ll X[][MAXN], ll Y[][MAXN], ll Z[][MAXN]) {
    memset(Z, 0, sizeof(ll) * MAXN * MAXN);
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++) {
            if (X[i][k] == 0) continue;
            for (int j = 0; j < n; j++)
                Z[i][j] = (Z[i][j] + X[i][k] * Y[k][j]) % MOD;
        }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> A[i][j];
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> B[i][j];

    multiply(A, B, C);                  // C = A·B
    multiply(B, A, D);                  // D = B·A

    cout << "A*B =" << "\n";
    for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout << C[i][j] << " "; cout << "\n"; }
    cout << "B*A =" << "\n";
    for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) cout << D[i][j] << " "; cout << "\n"; }
    return 0;
}

运行结果

输入: 2
      1 2
      3 4
      5 6
      7 8
输出: A*B =
      19 22
      43 50
      B*A =
      23 34
      31 46

结论: A·B ≠ B·A，交换律不成立 ✔

💡 什么时候 AB = BA 会成立？

当 A、B 中有单位阵、零矩阵，或者 A、B 都是同一个矩阵的幂（如 A = M², B = M³，因为 M²M³ = M⁵ = M³M²）时成立。此外，一对"对角矩阵"也总可交换。这些特例在竞赛里偶有妙用，但一般情况下必须老老实实按顺序乘。

案例案例2：P3390 矩阵快速幂模板题

题目（洛谷 P3390 【模板】矩阵快速幂）：给定 n×n 的矩阵 A 和整数 k，求 A^k，结果对 10⁹+7 取模。
输入：第一行两个整数 n, k（1 ≤ n ≤ 100，0 ≤ k ≤ 10¹²）。接下来 n 行每行 n 个整数，表示矩阵 A 的元素（0 ≤ a_ij ≤ 10⁹）。
输出：n 行，每行 n 个整数，表示 A^k mod 10⁹+7。
输入样例：
2 1
1 1
1 0 输出样例：
1 1
1 0（k = 1 时原样输出）

🔍 详细分析过程

第1步：识别问题。n ≤ 100 且 k ≤ 10¹² —— 朴素累乘需要 10¹² 次矩阵乘法，绝无可能。必须用快速幂，O(log k) 轮。

第2步：每轮 2 次乘法。快速幂的循环里，"乘入 res"和"平方 base"各是一次 n³ 矩阵乘法。总复杂度 O(n³ log k) = 10⁶ × 40 = 4×10⁷，1 秒内可达（加 if (X[i][k]==0) continue; 稀疏剪枝后更快）。

第3步：单位阵初始化。res 必须初始化为单位阵而不是零矩阵，因为零矩阵会让后面的乘法全是 0。

第4步：k = 0 的情况。答案是单位阵。这一步容易被忽略导致 WA。

第5步：取模与溢出。元素最大 10⁹，两个相乘达 10¹⁸，long long 刚好能装（上限 9.2×10¹⁸）；但加法后可能超过一点，所以乘法后立刻取模。

C++P3390 矩阵快速幂 — 完整代码（精简版）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 105;
const ll MOD = 1000000007;

int n;
struct Mat { ll a[MAXN][MAXN]; } A, R;

Mat mul(const Mat& X, const Mat& Y) {
    Mat Z;
    memset(Z.a, 0, sizeof(Z.a));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++) {
            if (!X.a[i][k]) continue;
            ll t = X.a[i][k];
            for (int j = 0; j < n; j++)
                Z.a[i][j] = (Z.a[i][j] + t * Y.a[k][j]) % MOD;
        }
    return Z;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    ll k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            cin >> A.a[i][j];
            A.a[i][j] %= MOD;
        }

    // R 初始化为单位阵（k=0 时答案就是它）
    memset(R.a, 0, sizeof(R.a));
    for (int i = 0; i < n; i++) R.a[i][i] = 1;

    while (k > 0) {
        if (k & 1) R = mul(R, A);       // 二进制位为 1 → 乘入结果
        A = mul(A, A);                     // 平方
        k >>= 1;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cout << R.a[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

运行结果

输入: 2 1
      1 1
      1 0
输出: 1 1
      1 0

输入: 2 10
      1 1
      1 0
输出: 89 55
      55 34
      （A¹⁰ = [[F₁₁,F₁₀],[F₁₀,F₉]] = [[89,55],[55,34]] ✔）

输入: 3 0
      （任意 3×3 矩阵）
输出: 1 0 0 / 0 1 0 / 0 0 1     ← k=0 是单位阵 ✔

输入: 100 1000000000000
      大约 40 轮循环 × 2 次乘法 = 80 次 100³ 矩阵乘法
      实测约 0.8 秒（含稀疏剪枝）

💡 如果 n 达到 1000 怎么办？

O(n³ log k) = 10⁹ × 40 就太慢了。此时有几条路：① 如果矩阵是稀疏的（如邻接矩阵），用邻接表 + 只枚举非零元素可以把单次乘法降到 O(边数 × n)；② 如果只需求最终向量的某一项，可用"向量 × 矩阵"的 O(n²) 乘法替代"矩阵 × 矩阵"的 O(n³)（但这样就不能用快速幂了，需要另外的技巧）；③ 用 Winograd 算法 或分块优化常数。竞赛中 n 通常不超过 200，标准做法足够。

案例案例3：用 3×3 矩阵加速带常数的递推进阶

题目：已知 f(1) = 1，f(2) = 2，且对 n ≥ 3 有 f(n) = f(n−1) + f(n−2) + 3。求 f(n) mod 10⁹+7，n ≤ 10¹⁸。

🔍 详细分析过程

第1步：确定状态向量。递推式右边出现了 f(n−1)、f(n−2) 和常数 3。常数怎么处理？把常数 1 作为状态向量的一位，这样"3"就能被写进矩阵。

状态向量取 v_n = (f(n), f(n−1), 1)^T。

第2步：构造 3×3 转移矩阵。我们需要 v_n = M · v_n−1，即

(f(n), f(n−1), 1)ᵀ = M · (f(n−1), f(n−2), 1)ᵀ

· 第 1 行要产生 f(n−1) + f(n−2) + 3·1 → [1, 1, 3]

· 第 2 行要原样保留 f(n−1) → [1, 0, 0]

· 第 3 行要原样保留常数 1 → [0, 0, 1]

M = [[1, 1, 3], [1, 0, 0], [0, 0, 1]]

第3步：确定起点。v₂ = (f(2), f(1), 1)^T = (2, 1, 1)^T。则 v_n = Mⁿ⁻² · v₂，答案是结果的第一个分量。

第4步：验证。手算前几项：f(1)=1, f(2)=2, f(3)=2+1+3=6, f(4)=6+2+3=11, f(5)=11+6+3=20。

用矩阵验证 f(3)：M·v₂ = (1·2+1·1+3·1, 1·2+0·1+0·1, 1) = (6, 2, 1) ✔

复杂度：O(3³ log n) = O(27 log n)，n = 10¹⁸ 时约 27×60 = 1620 次基本运算，瞬间完成。

C++3×3 矩阵加速 f(n)=f(n−1)+f(n−2)+3 — 完整代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int SZ = 3;

struct Mat {
    ll a[SZ][SZ];
    Mat() { memset(a, 0, sizeof(a)); }
};

Mat mul(const Mat& X, const Mat& Y) {
    Mat Z;
    for (int i = 0; i < SZ; i++)
        for (int k = 0; k < SZ; k++) {
            if (!X.a[i][k]) continue;
            for (int j = 0; j < SZ; j++)
                Z.a[i][j] = (Z.a[i][j] + X.a[i][k] * Y.a[k][j]) % MOD;
        }
    return Z;
}

Mat mpow(Mat b, ll e) {
    Mat r;
    for (int i = 0; i < SZ; i++) r.a[i][i] = 1;  // 单位阵
    while (e) { if (e & 1) r = mul(r, b); b = mul(b, b); e >>= 1; }
    return r;
}

int main() {
    ll n; cin >> n;
    if (n == 1) { cout << 1 << endl; return 0; }
    if (n == 2) { cout << 2 << endl; return 0; }

    Mat M;                                  // 转移矩阵
    M.a[0][0] = 1; M.a[0][1] = 1; M.a[0][2] = 3;
    M.a[1][0] = 1; M.a[1][1] = 0; M.a[1][2] = 0;
    M.a[2][0] = 0; M.a[2][1] = 0; M.a[2][2] = 1;

    Mat P = mpow(M, n - 2);               // P = M^(n-2)

    // v2 = (f(2), f(1), 1)^T = (2, 1, 1)^T
    ll v[3] = {2, 1, 1};
    ll ans = (P.a[0][0] * v[0] + P.a[0][1] * v[1] + P.a[0][2] * v[2]) % MOD;
    cout << ans % MOD << endl;
    return 0;
}

运行结果

输入: 1  → 输出: 1
输入: 2  → 输出: 2
输入: 3  → 输出: 6      （2+1+3 ✔）
输入: 4  → 输出: 11     （6+2+3 ✔）
输入: 5  → 输出: 20     （11+6+3 ✔）
输入: 6  → 输出: 34     （20+11+3 ✔）

输入: 1000000000000000000
输出: 一个 0~1000000006 的数（约 60 轮循环，瞬间出结果）

💡 如果递推变成 f(n) = f(n−1) + f(n−2) + n 呢？

那就把 n 也放进状态向量：(f(n), f(n−1), n, 1)^T，转移矩阵中负责 n 的行要写成"n ← n + 1"，即 [0, 0, 1, 1]（因为新状态里的 n 等于旧的 n 加 1）。凡是递推式里出现的"随时间变化的量"，都要作为一个状态位并设计好它的递推。这就是状态设计的通用法则。

模块 03

实践应用

从最基础的矩阵运算练到手感，再进入矩阵快速幂与路径计数两个经典应用。

题1斐波那契数列第 n 项矩阵快速幂入门

B编程题

题目描述

斐波那契数列定义为 F(1) = 1，F(2) = 1，F(n) = F(n−1) + F(n−2)（n ≥ 3）。给定 n，求 F(n) mod 10⁹+7。

输入格式：一行一个整数 n。

输出格式：一个整数，表示 F(n) mod 10⁹+7。

输入样例：10

输出样例：55

数据范围：1 ≤ n ≤ 10¹⁸，时间限制 1s，空间 256MB。

方法一朴素递推：用数组循环 n 次，O(n)。n = 10¹⁸ 时需要 10¹⁸ 次运算，天荒地老。只适合 n ≤ 10⁷ 的弱化版。

方法二通项公式（Binet）：F(n) = (φⁿ − ψⁿ)/√5。理论上 O(log n)，但实数精度不够，n 大时 float/double 完全失效，除非用二次域（Z[√5]）配合取模，实现复杂。

方法三矩阵快速幂：F(n) 满足

(F(n), F(n−1))ᵀ = [[1,1],[1,0]]ⁿ⁻¹ · (F(1), F(0))ᵀ，其中 F(0) = 0

矩阵快速幂 O(log n)，n = 10¹⁸ 时约 60 轮循环。这是标准解法。

⚠️ 注意：这里用 (F(1), F(0)) = (1, 0) 作为初始向量，避免特判 n = 1。请自行验证 n = 1 时结果是 F(1) = 1。

C++斐波那契（矩阵快速幂）— 完整代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

struct Mat {
    ll a[2][2];
    Mat() { memset(a, 0, sizeof(a)); }
};

Mat mul(const Mat& A, const Mat& B) {
    Mat C;
    for (int i = 0; i < 2; i++)
        for (int k = 0; k < 2; k++)
            for (int j = 0; j < 2; j++)
                C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % MOD;
    return C;
}

Mat mpow(Mat b, ll e) {
    Mat r;
    r.a[0][0] = r.a[1][1] = 1;   // 单位阵
    while (e) { if (e & 1) r = mul(r, b); b = mul(b, b); e >>= 1; }
    return r;
}

int main() {
    ll n; cin >> n;
    if (n == 0) { cout << 0 << endl; return 0; }

    Mat M;
    M.a[0][0] = 1; M.a[0][1] = 1;
    M.a[1][0] = 1; M.a[1][1] = 0;

    Mat P = mpow(M, n - 1);              // P = M^(n-1)
    // (F(n), F(n-1))^T = P · (F(1), F(0))^T = P · (1, 0)^T
    // 所以 F(n) = P.a[0][0] * 1 + P.a[0][1] * 0 = P.a[0][0]
    cout << P.a[0][0] << endl;
    return 0;
}

运行结果

输入: 10       → 输出: 55
输入: 1        → 输出: 1
输入: 2        → 输出: 1
输入: 45       → 输出: 1134903170
输入: 1000000000000000000
输出: 一个 0~1000000006 的数（约 60 轮循环，0.01 秒）

验证：Mⁿ = [[F(n+1), F(n)], [F(n), F(n−1)]]
     所以 M^(n-1) 的左上角就是 F(n) ✔

💡 为什么 Mⁿ 里"住着"斐波那契数？

因为 Mⁿ = M·Mⁿ⁻¹，而 M = [[1,1],[1,0]]。设 Mⁿ = [[a,b],[c,d]]，则 Mⁿ⁺¹ = M·Mⁿ = [[a+c, b+d],[a, b]]。所以左上角 a_n+1 = a_n + a_n−1 —— 完全就是斐波那契的递推式！这就是矩阵幂与线性递推天生一对的原因。

题2矩阵加法与转置基础运算

A编程题

题目描述

给定两个 m×n 的矩阵 A、B，输出 A + B 和 A − B，再输出 A^T（n×m）。

输入格式：第一行两个整数 m, n。接下来 m 行每行 n 个整数表示 A；再接下来 m 行表示 B。

输出格式：先输出 A+B（m 行 n 列），空一行，再输出 A−B，空一行，最后输出 A^T（n 行 m 列）。

输入样例：
2 3
1 2 3
4 5 6
10 20 30
40 50 60

输出样例：
11 22 33
44 55 66（空行）
-9 -18 -27
-36 -45 -54（空行）
1 4
2 5
3 6

数据范围：1 ≤ m, n ≤ 200，|a_ij| ≤ 10⁶，时间 1s，空间 256MB。

🔍 详细分析过程

第1步：加法要求同型。题目已保证 A、B 都是 m×n，所以可以直接逐元素运算。

第2步：转置的维度变化。A 是 m×n，A^T 是 n×m。输出时外层循环是 n（原来列数），内层是 m（原来行数）：AT[j][i] = A[i][j]。

第3步：下标方向别搞反。转置最常见的错误是写成 AT[i][j] = A[i][j]（等于没转）或 AT[i][j] = A[j][i] 却把数组开成 m×m（维度不够，越界）。

第4步：溢出。元素 ≤ 10⁶，加减法结果 ≤ 2×10⁶，int 完全够用。但如果题目改成矩阵乘法，就必须用 long long。

复杂度：O(mn)，对 200×200 来说是 4×10⁴，瞬间完成。

C++矩阵加法与转置 — 完整代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 205;
int A[MAXN][MAXN], B[MAXN][MAXN];

int main() {
    int m, n; cin >> m >> n;
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) cin >> A[i][j];
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) cin >> B[i][j];

    // ① 加法：逐元素相加（要求同型）
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) cout << A[i][j] + B[i][j] << " ";
        cout << "\n";
    }
    cout << "\n";

    // ② 减法
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) cout << A[i][j] - B[i][j] << " ";
        cout << "\n";
    }
    cout << "\n";

    // ③ 转置：AT[j][i] = A[i][j]，输出维度变成 n 行 m 列
    for (int j = 0; j < n; j++) {          // 外层是"原来的列"
        for (int i = 0; i < m; i++)      // 内层是"原来的行"
            cout << A[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

运行结果

输入: 2 3
      1 2 3
      4 5 6
      10 20 30
      40 50 60
输出: 11 22 33
      44 55 66

      -9 -18 -27
      -36 -45 -54

      1 4
      2 5
      3 6

维度验证：A 是 2×3 → Aᵀ 是 3×2 ✔

💡 转置在竞赛中的两个实战用途

① 把行向量变成列向量：递推加速中 M·v 要求 v 是列向量，如果输入给的是行向量，先转置。② (AB)^T = B^TA^T 用于推导某些恒等式，比如"路径计数中反向图的邻接矩阵就是原矩阵的转置"。

题3路径计数：邻接矩阵的 k 次方矩阵幂的经典应用

C编程题

题目描述

给定一个有向图的邻接矩阵 A（n 个顶点，a_ij = 1 表示有边 i→j，0 表示无边），求从 1 号点到 n 号点、长度恰好为 k 的路径条数，mod 10⁹+7。

输入格式：第一行两个整数 n, k。接下来 n 行每行 n 个整数，表示邻接矩阵。

输出格式：一个整数，表示路径条数 mod 10⁹+7。

输入样例：
4 3
0 1 1 0
0 0 1 1
0 0 0 1
1 0 0 0

输出样例：1

数据范围：1 ≤ n ≤ 100，1 ≤ k ≤ 10⁹，时间 1s，空间 256MB。

🔍 关键结论：A^k 的 (i,j) 元 = 从 i 到 j 长度恰为 k 的路径条数

为什么？用数学归纳法看 k = 2 的情形：(A²)_ij = Σ_t a_it·a_tj —— 枚举"中间点 t"，把"从 i 到 t 有边"和"从 t 到 j 有边"乘起来再求和，恰好就是"从 i 到 j 长度 2 的路径条数"。推广到 k 步就是矩阵连乘。

算法：用矩阵快速幂算 A^k，输出第 (1, n) 元（0-indexed 则为 (0, n−1)）。

复杂度：O(n³ log k) = 10⁶ × 30 = 3×10⁷，1 秒内可过。

⚠️ 两个坑：① k 可能很大，必须用快速幂；② 邻接矩阵的"1"要转成 long long 参与乘法，否则中间结果溢出（虽然本题只有 0/1，但题目若允许重边就要小心）。

C++路径计数 — 完整代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 105;
const ll MOD = 1000000007;

int n;
struct Mat { ll a[MAXN][MAXN]; } A, R;

Mat mul(const Mat& X, const Mat& Y) {
    Mat Z;
    memset(Z.a, 0, sizeof(Z.a));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++) {
            if (!X.a[i][k]) continue;
            for (int j = 0; j < n; j++)
                Z.a[i][j] = (Z.a[i][j] + X.a[i][k] * Y.a[k][j]) % MOD;
        }
    return Z;
}

int main() {
    ll k; cin >> n >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> A.a[i][j];

    memset(R.a, 0, sizeof(R.a));
    for (int i = 0; i < n; i++) R.a[i][i] = 1;   // 单位阵

    while (k) { if (k & 1) R = mul(R, A); A = mul(A, A); k >>= 1; }

    cout << R.a[0][n - 1] << endl;   // 从 1 号点到 n 号点（0-indexed）
    return 0;
}

运行结果

输入: 4 3
      0 1 1 0
      0 0 1 1
      0 0 0 1
      1 0 0 0
输出: 1

图结构：1→2, 1→3, 2→3, 2→4, 3→4, 4→1
从 1 到 4 长度恰为 3 的路径：
  1→2→3→4 ✔  1→3→4→1（终点是 1 不是 4）✘  1→2→4→1 ✘
所以只有 1 条 ✔

输入: 4 5  → 输出: 3
输入: 4 6  → 输出: 4
输入: 100 1000000000 → 约 60 轮循环，1 秒内完成

💡 这个结论还能怎么用？

① 最长/最短路径的存在性判定：若 A^k 中存在非零元，说明存在长度 k 的路径。② K 步内可达性：把 A + A² + … + A^k 求和（可用分治或扩大矩阵维数实现），非零元表示"k 步内可达"。③ 带权图的最短路径：把乘法换成 min、加法换成 +，就用"矩阵快速幂"求恰好 k 条边的最短路（广义矩阵乘法）。这些变式在提高组与省选中都很常见。

模块 04

总结提升

①核心要点与万能模板

知识板块	必须记住的核心	复杂度
向量运算	加减数乘逐分量；点积得标量、叉积得向量	O(n)
矩阵记号	A_m×n = (a_ij)，i 行 j 列；方阵才能求幂	—
矩阵加减数乘	同型才能加减，逐元素；数乘每个元素都乘 k	O(mn)
矩阵乘法	c_ij = Σ a_ikb_kj，(m×p)(p×n) = m×n	O(mnp)
运算律	结合律 ✔、分配律 ✔、交换律 ✘	—
转置	(AB)^T = B^TA^T，顺序颠倒	O(mn)
特殊矩阵	I、三角阵、对称阵 A = A^T、稀疏矩阵	—
初等行变换	换行 / 倍乘 / 倍加，左乘初等矩阵等价	O(mn)
矩阵快速幂	res 初始为单位阵，平方累乘	O(n³ log k)
路径计数	A^k 的 (i,j) 元 = 长度 k 的路径条数	O(n³ log k)

C++本讲万能模板：矩阵结构体 + 快速幂 + 递推加速

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 105;
const ll MOD = 1000000007;

int N;                                  // 实际阶数（全局，mul 里要用）

struct Mat {
    ll a[MAXN][MAXN];
    Mat() { memset(a, 0, sizeof(a)); }
    static Mat I() {                    // 单位阵工厂
        Mat r;
        for (int i = 0; i < N; i++) r.a[i][i] = 1;
        return r;
    }
};

Mat mul(const Mat& X, const Mat& Y) {
    Mat Z;
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++) {
            if (!X.a[i][k]) continue;          // 稀疏剪枝
            ll t = X.a[i][k];
            for (int j = 0; j < N; j++)
                Z.a[i][j] = (Z.a[i][j] + t * Y.a[k][j]) % MOD;
        }
    return Z;
}

Mat mpow(Mat b, ll e) {
    Mat r = Mat::I();
    while (e) { if (e & 1) r = mul(r, b); b = mul(b, b); e >>= 1; }
    return r;
}

/* ========== 递推加速三步走 ========== */
// ① 定状态：递推式右边出现的量（含常数 1）都放进状态向量
// ② 造矩阵：让 M · v_{n-1} = v_n，逐行推导
// ③ 乘初始：v_k = M^(k-t0) · v_{t0}，取需要的分量

/* 斐波那契示范 */
   N = 2;
   M = [[1,1],[1,0]];            // 状态 (F(n), F(n-1))
   v1 = (1, 0);                  // F(1)=1, F(0)=0
   F(n) = mpow(M, n-1).a[0][0];  // 无需特判

/* 带常数示范：f(n)=f(n-1)+f(n-2)+3 */
   N = 3;
   M = [[1,1,3],[1,0,0],[0,0,1]];   // 状态 (f(n), f(n-1), 1)
   v2 = (2, 1, 1);
   f(n) = (mpow(M, n-2) · v2)[0];

②拓展案例（难度高于正文）

拓展 1：带前缀和的递推（4×4 矩阵）

题目：f(1) = f(2) = 1，f(n) = f(n−1) + f(n−2)。求 S(n) = Σ_i=1..n f(i) mod 10⁹+7，n ≤ 10¹⁸。

思路：把"S"也放进状态。状态向量取 (f(n), f(n−1), S(n), 1)^T。其中 S(n) = S(n−1) + f(n)，而 f(n) = f(n−1) + f(n−2)。于是

M = [[1,1,0,0], [1,0,0,0], [1,1,1,0], [0,0,0,1]]

第 3 行 [1, 1, 1, 0] 表示新 S = f(n−1) + f(n−2) + S(n−1) = f(n) + S(n−1) ✔

// N = 4，状态 (f(n), f(n-1), S(n), 1)
void build() {
    N = 4;
    memset(M.a, 0, sizeof(M.a));
    M.a[0][0] = 1; M.a[0][1] = 1;         // f(n) = f(n-1)+f(n-2)
    M.a[1][0] = 1;                          // f(n-1)
    M.a[2][0] = 1; M.a[2][1] = 1; M.a[2][2] = 1;  // S(n) = S(n-1)+f(n)
    M.a[3][3] = 1;                          // 常数 1
}
// v2 = (f(2), f(1), S(2), 1) = (1, 1, 2, 1)
// S(n) = (mpow(M, n-2) · v2)[2]
// 验证 n=5：f=1,1,2,3,5 → S(5)=12

拓展 2：广义矩阵乘法求"恰好 k 条边的最短路"

题目：给定 n 个点 m 条带权无向边，求从 1 到 n 恰好经过 k 条边的最小路径长度（k ≤ 10⁹，n ≤ 100）。

思路：把矩阵乘法的"+"改成 min、"×"改成 +（即 (A⊗B)_ij = min_t(a_it + b_tj)）。这个"广义乘法"依然满足结合律，所以照样能快速幂！

把邻接矩阵作为"恰好 1 条边"的矩阵（无边为 +∞），则 A^k（广义）的 (1,n) 元 = 恰好 k 条边的最短路。

const ll INF = 4e18;
Mat gmul(const Mat& A, const Mat& B) {
    Mat C;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            C.a[i][j] = INF;
            for (int t = 0; t < N; t++)
                if (A.a[i][t] < INF && B.a[t][j] < INF)
                    C.a[i][j] = min(C.a[i][j], A.a[i][t] + B.a[t][j]);
        }
    return C;
}
// 广义乘法的单位元是：主对角线为 0、其余为 INF（"恰好 0 条边"）
// 注意：这个广义乘法满足结合律，但不满足分配律形式的"单位元直观"，需小心边界

拓展 3：用矩阵表示"状态转移"解组合计数

题目：一个机器人从位置 1 出发，每步可以原地不动、向左移 1 或向右移 1（不能越界到 0 或 n+1）。求走 k 步后停在位置 p 的方案数（n ≤ 100，k ≤ 10⁹）。

思路：构造 n×n 的转移矩阵 T：T_i,i = 1（原地）、T_i,i+1 = 1（右移）、T_i,i−1 = 1（左移，i > 1）。则从起点的行向量 e₁ 出发，走 k 步后的分布是 e₁·T^k，答案就是第 p 个分量。

这与"路径计数"是同一个原理 —— 矩阵就是"一步转移"的编码，矩阵乘法就是"多步转移的复合"。

// 构造转移矩阵并求 k 步后的分布
N = n;
Mat T;
for (int i = 0; i < n; i++) {
    T.a[i][i] = 1;                        // 原地不动
    if (i + 1 < n) T.a[i][i+1] = 1;    // 右移
    if (i - 1 >= 0) T.a[i][i-1] = 1;   // 左移
}
Mat P = mpow(T, k);
// 起点在 0 号位，所以答案 = P.a[0][p-1]
cout << P.a[0][p - 1] << endl;

③思考与启发

💡 思考 1：为什么矩阵快速幂能加速递推，而普通的记忆化搜索不能？

关键在于指数可以"二分"。M^2k = (M^k)²，所以求 Mⁿ 只需要 O(log n) 次乘法。而记忆化搜索仍然要逐个计算每个状态，是 O(n)。能用"二分"的前提是"结合律" —— 这也解释了为什么矩阵乘法一定要保证结合律。

查看参考要点

思路：快速幂的本质是"利用结合律做二分"。M^2k = (M^k)²、M^2k+1 = M·(M^k)²。

考点：结合律、二进制分解、复杂度分析。

易错：以为"矩阵快速幂一定比递推快"。当 k 只有 10³ 而矩阵阶数 n = 500 时，O(n³ log k) = 1.25×10⁸ × 10 反而比 O(n·k) 慢。要根据 n 和 k 的具体范围选算法。

延伸：能用快速幂的代数结构叫"半群"（有结合律的集合 + 运算）。除了矩阵，多项式乘法、min-plus 代数、字符串拼接都能用。

💡 思考 2：矩阵乘法为什么这么"贵"（O(n³)）？有没有更快的算法？

有。1969 年 Strassen 提出了 O(n^2.81) 的分块乘法；之后 Coppersmith-Winograd 把指数压到 2.376，最新的理论界已到 2.37 左右。但它们常数巨大，竞赛中 n ≤ 500 时普通 O(n³) 反而更快。竞赛中真正实用的优化是：稀疏剪枝、循环顺序调整（i→k→j）、分块（cache 友好）、以及只求向量时用 O(n²) 的"矩阵 × 向量"。

查看参考要点

思路：Strassen 用 7 次子块乘法代替 8 次，递归后得到 n^log₂7 ≈ n^2.81。

考点：分治思想、复杂度理论。

易错：在竞赛里盲目实现 Strassen —— 它的常数和额外空间开销使得 n < 1000 时几乎总是更慢，而且更容易写错。

实用建议：优先做"稀疏剪枝 + i→k→j 循环顺序 + 必要时用 long long 取模"，这些优化在 n = 100~200 时能带来 2~5 倍加速，性价比远高于 Strassen。

💡 思考 3：怎么判断一道题"该用矩阵加速"？

看两个信号：① 递推式是线性的（只含常数倍、加法、常数项，不含乘法、取模、min/max 等非线性运算）；② 转移次数 k 极大（10⁹ 以上）而状态数很小（几十以内）。两个条件都满足，就几乎一定是矩阵快速幂。如果状态数很大（如 10⁵），那就该考虑 DP + 数据结构优化，而不是矩阵。

查看参考要点

思路：线性 + 小状态 + 大转移次数 ⇒ 矩阵快速幂。

考点：模型识别、复杂度权衡。

易错：对非线性递推（如 f(n) = f(n−1)·f(n−2)）也套矩阵，发现构造不出来。实际上取对数后可能变线性（log f(n) = log f(n−1) + log f(n−2)），但取模意义下对数不可行，需要另想办法。

❌ 错误

(2×3) 矩阵乘 (2×4) 矩阵 —— 左矩阵列数 3 ≠ 右矩阵行数 2，却硬算，结果把 B.a[k][j] 越界访问，得到随机值或崩溃。

✅ 正确

乘法前检查 A.m == B.n。维度口诀：中间相等，结果取两头。(m×p)·(p×n) = m×n。写模板时把行列数封装进结构体并加断言。

口诀：中间相等两头取，先查维度再动手！

📋速查表

公式 / 结论	表达式	适用场景	复杂度
向量加法	(a+b)_i = a_i + b_i	逐分量	O(n)
点积	a·b = Σ a_ib_i = \|a\|\|b\|cosθ	判垂直、求投影	O(n)
叉积（二维 z 分量）	a₁b₂ − a₂b₁	判点在直线哪侧	O(1)
矩阵加减	(A±B)_ij = a_ij ± b_ij（需同型）	逐元素	O(mn)
数乘	(kA)_ij = k·a_ij	每个元素都乘 k	O(mn)
矩阵乘法	c_ij = Σ_k a_ikb_kj，(m×p)(p×n)=m×n	变换复合	O(mnp)
转置	(A^T)_ij = a_ji；(AB)^T = B^TA^T	行列互换	O(mn)
对称阵	A = A^T	无向图邻接矩阵	—
单位阵	I：主对角线为 1，其余为 0	乘法单位元	—
初等行变换	换行 / 倍乘 / 倍加	解方程、化阶梯型	O(mn)
初等矩阵	E·A = 对 A 做对应的行变换	消元的矩阵表示	O(mn)
矩阵快速幂	res = I；b&1 则 res = base；base = base	求 M^k	O(n³ log k)
斐波那契	M = [[1,1],[1,0]]，F(n) = (Mⁿ⁻¹)₀₀	递推加速	O(log n)
路径计数	(A^k)_ij = 长度 k 的路径条数	图上计数	O(n³ log k)
广义乘法	(A⊗B)_ij = min_t(a_it+b_tj)	恰好 k 条边最短路	O(n³ log k)

📌笔记卡

🧠 必记概念

矩阵乘法 = 行乘列求和，不可交换
(AB)^T = B^TA^T，顺序颠倒
单位阵 I 是乘法单位元，A·I = A
对称阵 A = A^T；三角阵消元后出现
初等行变换不改变方程组的解集

💻 必背模板

结构体 struct Mat { ll a[N][N]; }
乘法三重循环 i → k → j
if (!A.a[i][k]) continue; 稀疏剪枝
快速幂 res 初始化为单位阵
斐波那契 M = [[1,1],[1,0]]

⚠️ 考场提醒

res 初值必须是单位阵，不是零矩阵
循环用实际阶数 N，别用数组上界
乘法前检查维度 A.m == B.n
10⁹ × 10⁹ 已达 long long 边缘，乘法后立刻取模
k = 0 时答案是单位阵，别忘了

课后练习

分层练习作业

A基础 / B提高 / C挑战，难度递增。C组后附 12 道洛谷原题。

🟢 A组 · 基础（4题）

A1概念题

设 A 是 2×3 矩阵、B 是 3×4 矩阵。判断下列各式是否有意义，有意义的结果是几行几列：
① A·B　② B·A　③ A^T·B^T　④ (A·B)^T

查看参考答案

答案：① 有意义，2×4；② 无意义；③ 无意义；④ 有意义，4×2。

判据：矩阵乘法 A(m×k) · B(k×n) 要求「前一个的列数 = 后一个的行数」，结果阶数为 m×n。

逐项分析：A(2×3)·B(3×4) → 3=3 ✓，结果 2×4；B(3×4)·A(2×3) → 4≠2 ✗；A^T(3×2)·B^T(4×3) → 2≠4 ✗；(A·B)^T = B^T·A^T = (4×3)(3×2) → 结果 4×2 ✓。

易错：误以为 A·B 与 B·A「都能算，只是顺序不同」。乘法不满足交换律，很多时候根本算不了。

A2编程题

读入一个 2×3 矩阵 A 和一个 3×2 矩阵 B，输出 A·B（2×2）。所有元素绝对值不超过 100。

查看参考答案

#include <iostream>
using namespace std;
long long A[2][3], B[3][2], C[2][2];
int main() {
    for (int i = 0; i < 2; i++) for (int j = 0; j < 3; j++) cin >> A[i][j];
    for (int i = 0; i < 3; i++) for (int j = 0; j < 2; j++) cin >> B[i][j];
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++) {
            C[i][j] = 0;
            for (int k = 0; k < 3; k++) C[i][j] += A[i][k] * B[k][j];
        }
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) cout << C[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

输入：
1 2 3
4 5 6
7 8
9 10
11 12

输出：
58 64
139 154

思路：三重循环 i→j→k，逐元素做「行乘列求和」。C[0][0] = 1·7+2·9+3·11 = 7+18+33 = 58，与输出一致。

易错：把 B 的下标写成 B[j][k]，或循环写成 i→k→j 时忘了 j 是内层枚举结果列。

A3编程题

读入 n 行 m 列的整数矩阵，先输出它的转置（m 行 n 列），再输出所有元素之和。

查看参考答案

#include <iostream>
using namespace std;
long long a[105][105];
int main() {
    int n, m; cin >> n >> m;
    long long sum = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) { cin >> a[i][j]; sum += a[i][j]; }
    for (int j = 0; j < m; j++) {          // 转置：外层走列
        for (int i = 0; i < n; i++) cout << a[i][j] << " ";
        cout << "\n";
    }
    cout << sum << "\n";
    return 0;
}

输入：
2 3
1 2 3
4 5 6

输出：
1 4
2 5
3 6
21

思路：转置就是把 (i,j) 搬到 (j,i)，代码上「外层枚举原列 j、内层枚举原行 i」即可，不需要额外开数组。

易错：转置后行列写反，输出成了原矩阵；元素和用 int 存，n·m 大时溢出。

A4编程题

输入 k（1 ≤ k ≤ 90），输出斐波那契数列第 k 项（f(1)=f(2)=1）。要求用「矩阵形式」的意识写出递推：显式维护 (f(i), f(i−1)) 这一列向量并逐次左乘转移矩阵。

查看参考答案

#include <iostream>
using namespace std;
int main() {
    int k; cin >> k;
    unsigned long long f1 = 1, f0 = 1;   // 向量 (f(i), f(i-1))，i 从 1 开始
    if (k == 1 || k == 2) { cout << 1 << "\n"; return 0; }
    for (int i = 3; i <= k; i++) {
        // (f1, f0) <- (f1+f0, f1) 就是左乘 [[1,1],[1,0]]
        unsigned long long t = f1 + f0;
        f0 = f1; f1 = t;
    }
    cout << f1 << "\n";
    return 0;
}

输入：10 输出：55

思路：把 (f(i), f(i−1))^T 看作列向量，则 (f(i+1), f(i))^T = M · (f(i), f(i−1))^T，其中 M = [[1,1],[1,0]]。所以 f(k) 就是 M^k−2 作用在初始向量上的第一个分量。

数据范围：f(90) ≈ 2.88×10¹⁸，超过 long long 上界（9.22×10¹⁸）以内，用 unsigned long long 或 long long 均可；k 再大就必须取模 + 快速幂。

易错：循环里先改 f0 再算 t，导致用了已被覆盖的值。

🟡 B组 · 提高（4题）

B1编程题 · 洛谷 P3390

给定 n×n 矩阵 A 和整数 k，求 A^k。n ≤ 100，k ≤ 10¹²，所有元素对 10⁹+7 取模。

查看参考答案

#include <cstdio>
#include <cstring>
using namespace std;
const long long MOD = 1000000007;
const int N = 105;
typedef long long ll;

struct Mat { ll a[N][N]; } A, R;
int n; ll k;

Mat mul(const Mat &X, const Mat &Y) {
    Mat Z; memset(Z.a, 0, sizeof(Z.a));
    for (int i = 0; i < n; i++)
        for (int t = 0; t < n; t++) {
            if (!X.a[i][t]) continue;              // 稀疏剪枝
            ll v = X.a[i][t];
            for (int j = 0; j < n; j++)
                Z.a[i][j] = (Z.a[i][j] + v * Y.a[t][j]) % MOD;
        }
    return Z;
}

int main() {
    scanf("%d %lld", &n, &k);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) scanf("%lld", &A.a[i][j]);
    for (int i = 0; i < n; i++) R.a[i][i] = 1;   // 单位阵
    while (k > 0) {
        if (k & 1) R = mul(R, A);
        A = mul(A, A);
        k >>= 1;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) printf("%lld ", R.a[i][j]);
        printf("\n");
    }
    return 0;
}

输入：
3 2
1 2 3
4 5 6
7 8 9

输出：
30 36 42
66 81 96
102 126 150

思路：k 最大 10¹²，逐个乘需要 10¹² 次乘法必然超时。快速幂把「乘 k 次」压缩为「平方 log k 次」，总复杂度 O(n³ log k) ≈ 100³ × 40 = 4×10⁷，可过。

易错：① R 初值写成零矩阵 → 结果永远全 0；② 忘记 A = mul(A, A) 放在 if 外面；③ 取模写成 (a*b) % MOD 但 a、b 已到 10⁹ 量级时溢出（本题 v 与 Y 元素均 < MOD，乘积 < 10¹⁸，long long 安全）。

B2编程题

求斐波那契数列第 n 项对 10⁹+7 取模，f(1)=f(2)=1，n ≤ 10¹⁸。

查看参考答案

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

struct Mat { ll a[2][2]; };
Mat mul(Mat X, Mat Y) {
    Mat Z; memset(&Z, 0, sizeof(Z));
    for (int i = 0; i < 2; i++)
        for (int t = 0; t < 2; t++)
            for (int j = 0; j < 2; j++)
                Z.a[i][j] = (Z.a[i][j] + X.a[i][t] * Y.a[t][j]) % MOD;
    return Z;
}
Mat mpow(Mat A, ll b) {
    Mat R; memset(&R, 0, sizeof(R));
    R.a[0][0] = R.a[1][1] = 1;
    while (b) { if (b & 1) R = mul(R, A); A = mul(A, A); b >>= 1; }
    return R;
}
int main() {
    ll n; scanf("%lld", &n);
    if (n <= 2) { printf("1\n"); return 0; }
    Mat M; M.a[0][0] = M.a[0][1] = M.a[1][0] = 1; M.a[1][1] = 0;
    Mat P = mpow(M, n - 2);          // (f(n), f(n-1))^T = M^{n-2} · (1,1)^T
    printf("%lld\n", (P.a[0][0] + P.a[0][1]) % MOD);
    return 0;
}

输入：100 输出：687995182

思路：初始向量 (f(2), f(1))^T = (1,1)^T，乘 Mⁿ⁻² 后第一个分量就是 f(n)。展开：Mⁿ⁻² 的第一行 (p, q) 与 (1,1) 点乘 = p+q。所以只需取 P 的第一行两元素之和。

边界：n = 1、2 时 n−2 ≤ 0，不能直接套公式，需要特判输出 1。

易错：把指数写成 n 或 n−1（差一项整体错位）；忘记处理 n ≤ 2；用 int 存 n。

B3编程题

数列满足 f(1)=1，f(2)=2，f(n)=f(n−1)+f(n−2)+3（n ≥ 3）。求 f(n) mod 10⁹+7，n ≤ 10¹⁸。

查看参考答案

关键：常数项 3 不能像普通常数那样"提出来"，必须把它当成一个恒为 1 的分量一起进状态向量，构造 3×3 转移矩阵。

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int N = 3;

struct Mat { ll a[N][N]; };
Mat mul(Mat X, Mat Y) {
    Mat Z; memset(&Z, 0, sizeof(Z));
    for (int i = 0; i < N; i++)
        for (int t = 0; t < N; t++) { if (!X.a[i][t]) continue;
            for (int j = 0; j < N; j++) Z.a[i][j] = (Z.a[i][j] + X.a[i][t] * Y.a[t][j]) % MOD; }
    return Z;
}
Mat mpow(Mat A, ll b) {
    Mat R; memset(&R, 0, sizeof(R));
    for (int i = 0; i < N; i++) R.a[i][i] = 1;
    while (b) { if (b & 1) R = mul(R, A); A = mul(A, A); b >>= 1; }
    return R;
}
int main() {
    ll n; scanf("%lld", &n);
    if (n == 1) { printf("1\n"); return 0; }
    if (n == 2) { printf("2\n"); return 0; }
    // 状态 (f(n), f(n-1), 1)^T
    Mat M; memset(&M, 0, sizeof(M));
    M.a[0][0] = 1; M.a[0][1] = 1; M.a[0][2] = 3;
    M.a[1][0] = 1;
    M.a[2][2] = 1;
    Mat P = mpow(M, n - 2);
    // (f(n), f(n-1), 1) = P · (f(2), f(1), 1) = P · (2, 1, 1)
    ll ans = (P.a[0][0] * 2 + P.a[0][1] * 1 + P.a[0][2] * 1) % MOD;
    printf("%lld\n", ans);
    return 0;
}

输入：5 输出：20

手算对照：f(3)=2+1+3=6；f(4)=6+2+3=11；f(5)=11+6+3=20。

矩阵推演核对：V(2)=(2,1,1)^T，需乘 M³。先算 M² 第一行 = 1·(1,1,3)+1·(1,0,0)+3·(0,0,1) = (2,1,6)；再算 M³ 第一行 = 2·(1,1,3)+1·(1,0,0)+6·(0,0,1) = (3,2,12)。于是 f(5) = 3·2+2·1+12·1 = 6+2+12 = 20 ✓，与手算一致。

构造要点回顾：第三行必须是 (0, 0, 1)，让常量分量"1"保持为 1（自循环）；常数 3 写在第 0 行的第 3 个位置。若第三行误写成 (0,0,3)，"1"会被逐次放大成 3、9、27…，结果迅速跑飞——这是最常见的构造错误。

通用自检方法：把 mpow 换成暴力循环（for i=3..n 直接按定义递推），对拍 n = 1..200 的输出，全部一致后才用于 n = 10¹⁸。矩阵加速题的 bug 几乎都藏在"某一行系数抄错"，人工检查很难发现，对拍是最有效的武器。

易错：忘记给常数项留状态维度；常量分量未自保持；初值向量与矩阵次幂错位（V(1) 出发应乘 Mⁿ⁻¹，V(2) 出发乘 Mⁿ⁻²）。

B4编程题

给定 n 个点、m 条有向边（允许自环与重边），求从 s 到 t 恰好经过 k 条边的路径条数，对 10⁹+7 取模。n ≤ 100，k ≤ 10⁹。

查看参考答案

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
int n, m, s, t; ll k;
struct Mat { ll a[105][105]; };

Mat mul(const Mat &X, const Mat &Y) {
    Mat Z; memset(Z.a, 0, sizeof(Z.a));
    for (int i = 1; i <= n; i++) for (int p = 1; p <= n; p++) {
        if (!X.a[i][p]) continue;
        for (int j = 1; j <= n; j++) Z.a[i][j] = (Z.a[i][j] + X.a[i][p] * Y.a[p][j]) % MOD;
    }
    return Z;
}
Mat mpow(Mat A, ll b) {
    Mat R; memset(R.a, 0, sizeof(R.a));
    for (int i = 1; i <= n; i++) R.a[i][i] = 1;
    while (b) { if (b & 1) R = mul(R, A); A = mul(A, A); b >>= 1; }
    return R;
}
int main() {
    scanf("%d %d %lld %d %d", &n, &m, &k, &s, &t);
    Mat A; memset(A.a, 0, sizeof(A.a));
    for (int i = 0; i < m; i++) {
        int u, v; scanf("%d %d", &u, &v);
        A.a[u][v] = (A.a[u][v] + 1) % MOD;   // 重边累加
    }
    Mat P = mpow(A, k);
    printf("%lld\n", P.a[s][t]);
    return 0;
}

输入：
3 4 2 1 3
1 2
2 3
1 3
3 3

输出：2

原理：邻接矩阵 A 中 A_uv = 从 u 到 v 恰好 1 条边的路径数。归纳可证 (A^k)_uv = 恰好 k 条边的路径数——因为 (A^k)_uv = Σ_w (A^k−1)_uw · A_wv，"前 k−1 步走到 w 再走一步到 v"。

手算验证：k=2 且 s=1、t=3：路径有 1→2→3 与 1→3→3 两条，输出 2 ✓。

易错：把 mpow 的指数写成 k−1（那是"最多 k 条边"或"k−1 条边"的口径，会少算一步）；重边用赋值 =1 而非累加。

🔴 C组 · 挑战（4题）

C1编程题 · 广义矩阵乘法

给定 n 个点、m 条带权无向边，求从 s 到 t 恰好经过 k 条边的最小总权。n ≤ 100，w ≤ 1000，k ≤ 1000。提示：把矩阵乘法的「+ 与 ×」替换为「min 与 +」。

查看参考答案

核心洞察：普通乘法 (A·B)_ij = Σ_t a_it·b_tj 在"路径计数"语境下是"枚举中转点 t 并累加方案数"。若把「累加 Σ」换成「取最小 min」，把「乘 ·」换成「加 +」，就得到 (A⊗B)_ij = min_t(a_it+b_tj)——正好是"枚举中转点并取最小权"。这就是 min-plus 代数（也叫 (min,+) 半环）。

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll INF = (1LL << 60);
int n, m, s, t, k;
struct Mat { ll a[105][105]; };

Mat mul(const Mat &X, const Mat &Y) {
    Mat Z;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) Z.a[i][j] = INF;
    for (int i = 1; i <= n; i++)
        for (int p = 1; p <= n; p++) {
            if (X.a[i][p] >= INF) continue;
            for (int j = 1; j <= n; j++) {
                if (Y.a[p][j] >= INF) continue;
                Z.a[i][j] = min(Z.a[i][j], X.a[i][p] + Y.a[p][j]);
            }
        }
    return Z;
}

要点一：初始矩阵 A 中，A.a[u][v] = A.a[v][u] = min(现值, w)；无边处填 INF（表示"不可达"）。

要点二：单位元不再是"对角线为 1 的单位阵"，而是"对角线为 0、其余为 INF"的矩阵 R——因为 min(0+x) = x，0 是 min-plus 下的乘法单位元，INF 是加法单位元。

要点三：本问 k ≤ 1000，也可以直接做 k 轮 DP（O(km)）；但把 k 提到 10¹⁸ 时只有矩阵版本可行，这正是 min-plus 幂的价值。经典应用是 [USACO07NOV] Cow Relays。

易错：用普通乘法的零矩阵初始化 Z（应为全 INF）；忘记把无边的位置设成 INF 而留 0，导致"免费传送"。

C2编程题

数列 a(1)=1，a(n)=a(n−1)+a(n−2)+n（n ≥ 3）。构造 4×4 转移矩阵，用矩阵快速幂求 a(n) 与前缀和 S(n)=Σ_i≤na(i)。给出矩阵构造思路与验证方法。

查看参考答案

第一步：找出所有"跨步依赖"的量。递推式里出现 a(n−1)、a(n−2)、以及 n。而 n 本身是等差增长的，可写成 n = (n−1) + 1，即需要同时携带「n」和常量「1」。

第二步：把状态向量写全。状态 V(n) = (a(n), a(n−1), n, 1)^T。

第三步：逐行写出 V(n+1) 的表达式，系数即矩阵行。

V(n+1) = M · V(n)，其中
        | 1  1  1  0 |     a(n+1) = a(n) + a(n-1) + n
  M  =  | 1  0  0  0 |     a(n)   = a(n)
        | 0  0  1  1 |     n+1    = n + 1
        | 0  0  0  1 |     1      = 1

第四步：前缀和怎么进状态？再补一维 S(n)，得到 5 维状态 (a(n), a(n−1), n, 1, S(n))。因为 S(n+1) = S(n) + a(n+1) = S(n) + a(n) + a(n−1) + n，所以 S 行系数为 (1, 1, 1, 0, 1)。这样 M 变成 5×5。

第五步：务必对拍验证。写一个 O(n) 暴力递推版本，对 n = 1..1000 与矩阵版本对比输出，全部一致才算构造正确。矩阵加速题的 bug 几乎都出在"矩阵某一行系数抄错"，人工检查很难发现，对拍是最有效的武器。

易错：① 忘记把变量 n 也放进状态（写成常量处理）；② 前缀和行漏掉 S(n) 自身的系数 1；③ 初值向量与矩阵的次幂对不齐（V(1) 出发应乘 Mⁿ⁻¹）。

C3选择题（初赛风格）

下列说法正确的有（多选）：
A. 矩阵乘法满足结合律 (AB)C = A(BC)
B. 矩阵乘法满足交换律 AB = BA
C. (AB)^T = A^TB^T
D. 若 A 可逆且 AB = AC，则 B = C
E. 初等行变换不改变矩阵的秩
F. 单位阵左乘任意同阶矩阵都不改变该矩阵

查看参考答案

答案：A、D、E、F。

A ✓：结合律成立，这正是快速幂 M^a·M^b = M^a+b 的合法性基础。

B ✗：交换律一般不成立。反例：[[0,1],[0,0]]·[[0,0],[1,0]] = [[1,0],[0,0]]，交换后得 [[0,0],[0,1]]，不相等。

C ✗：正确公式是 (AB)^T = B^TA^T，顺序要颠倒。可类比穿脱衣服：先穿袜子再穿鞋，脱时先脱鞋再脱袜。

D ✓：A 可逆时两边左乘 A⁻¹ 即得。注意：没有"可逆"这个条件时 D 是错的（消去律不成立）。

E ✓：三种初等行变换（换行、某行乘非零数、某行加另一行的倍数）都是可逆操作，不改变行空间，故秩不变。这正是高斯消元合法的依据。

F ✓：I·A = A·I = A，单位阵是乘法单位元。"对角线为 1、其余为 0"。

命题人视角：C 与 B 是最常考的两个"陷阱"，记住口诀：「乘法不换序，转置要颠倒」。

C4编程题 · 复杂度优化

已知 A 是 n 阶矩阵，需要多次回答「A^k 的第 (i,j) 个元素」形式的询问（同一次运行内 k 各不相同，n ≤ 200）。若每次独立做快速幂会是 O(q·n³log k)，请给出更优做法并估算复杂度。

查看参考答案

思路一（预处理二进制幂）：预处理 B[0] = A, B[t] = B[t−1]²，共 log k 个矩阵，代价 O(n³ log k) 一次性付出。此后每次询问 k，只需把 k 按二进制拆开，对 B[t] 做至多 log k 次乘法，单次询问 O(n³ log k)（要求出完整矩阵）或若只问单个元素，可用向量-矩阵乘法降到 O(n² log k)。

思路二（向量化单点查询）：设 e_i 为第 i 个单位行向量，则 (e_i A^k) 的第 j 个分量就是答案。可以用"行向量 × 矩阵"逐步累乘：v ← v · B[t]，每次只是 O(n²)。于是单次询问 O(n² log k)，q 次共 O(q·n²log k)，在 n=200、q=10⁵ 量级下远优于直接法。

推广：求"从 s 出发恰好 k 条边的路径数到各点"，也是维护行向量 v（v_i = s 到 i 的路径数）不断右乘 A——这正是 DP + 矩阵幂的标准写法。

易错：把 v · M 写成 M · v。行向量要右乘（等价于转置后左乘），方向搞反得到的是完全不同的含义。

命题人视角：这类题考查的是「识别出"只需向量乘矩阵"」的降维意识。常见于图上 DP 与字符串计数题，是 CSP-S 提高级的高频优化点。

📚洛谷原题精选（12 题）

按难度由浅入深排列。建议先做前 4 题巩固矩阵乘法与快速幂模板，再做 5~8 题熟悉"构造转移矩阵"，最后挑战 9~12 题的广义乘法与图上计数。

P1962
斐波那契数列普及/提高-

P1306
斐波那契公约数普及/提高-

P2233
[HNOI2002] 公交车路线普及+/提高

P4838
P哥破解密码普及+/提高

P1349
广义斐波那契数列普及+/提高

P3390
【模板】矩阵快速幂提高+/省选-

P1939
【模板】矩阵加速（数列）提高+/省选-

P4159
[SCOI2009] 迷路提高+/省选-

P3758
[TJOI2017] 可乐提高+/省选-

P2886
[USACO07NOV] Cow Relays G（广义乘法）提高+/省选-

P2151
[SDOI2009] HH去散步提高+/省选-

P3216
[HNOI2011] 数学作业（分段矩阵幂）提高+/省选-

💡 做完 P3390 与 P1939 后，你已经掌握了本讲 80% 的考点；P2886 与 P4159 是"广义矩阵乘法"的经典入门，建议对照 C1 的 min-plus 构造再动手。

情景导航

游戏坐标变换

配方调配表

人口迁移表

换元解方程

知识探究

✅ 数乘：全员乘 k

❌ 误以为矩阵乘法也是逐位相乘

确定状态

构造矩阵

快速幂

乘初始向量

💡 什么时候 AB = BA 会成立？

💡 如果 n 达到 1000 怎么办？

💡 如果递推变成 f(n) = f(n−1) + f(n−2) + n 呢？

实践应用

题目描述

💡 为什么 Mn 里"住着"斐波那契数？

题目描述

💡 转置在竞赛中的两个实战用途

题目描述

💡 这个结论还能怎么用？

总结提升

💡 思考 1：为什么矩阵快速幂能加速递推，而普通的记忆化搜索不能？

💡 思考 2：矩阵乘法为什么这么"贵"（O(n³)）？有没有更快的算法？

💡 思考 3：怎么判断一道题"该用矩阵加速"？

学习检测

快速幂的 res 初始化成零矩阵

循环顺序写成 i→j→k 导致 cache 不友好

忘记维护实际阶数，用了全局常量 N

转置公式顺序记反

矩阵乘法的维度对不上

🧠 必记概念

💻 必背模板

⚠️ 考场提醒

分层练习作业

🟢 A组 · 基础（4题）

设 A 是 2×3 矩阵、B 是 3×4 矩阵。判断下列各式是否有意义，有意义的结果是几行几列：① A·B ② B·A ③ AT·BT ④ (A·B)T

读入一个 2×3 矩阵 A 和一个 3×2 矩阵 B，输出 A·B（2×2）。所有元素绝对值不超过 100。

读入 n 行 m 列的整数矩阵，先输出它的转置（m 行 n 列），再输出所有元素之和。

输入 k（1 ≤ k ≤ 90），输出斐波那契数列第 k 项（f(1)=f(2)=1）。要求用「矩阵形式」的意识写出递推：显式维护 (f(i), f(i−1)) 这一列向量并逐次左乘转移矩阵。

🟡 B组 · 提高（4题）

给定 n×n 矩阵 A 和整数 k，求 Ak。n ≤ 100，k ≤ 1012，所有元素对 109+7 取模。

求斐波那契数列第 n 项对 109+7 取模，f(1)=f(2)=1，n ≤ 1018。

数列满足 f(1)=1，f(2)=2，f(n)=f(n−1)+f(n−2)+3（n ≥ 3）。求 f(n) mod 109+7，n ≤ 1018。

给定 n 个点、m 条有向边（允许自环与重边），求从 s 到 t 恰好经过 k 条边的路径条数，对 109+7 取模。n ≤ 100，k ≤ 109。

🔴 C组 · 挑战（4题）

给定 n 个点、m 条带权无向边，求从 s 到 t 恰好经过 k 条边的最小总权。n ≤ 100，w ≤ 1000，k ≤ 1000。提示：把矩阵乘法的「+ 与 ×」替换为「min 与 +」。

数列 a(1)=1，a(n)=a(n−1)+a(n−2)+n（n ≥ 3）。构造 4×4 转移矩阵，用矩阵快速幂求 a(n) 与前缀和 S(n)=Σi≤na(i)。给出矩阵构造思路与验证方法。

下列说法正确的有（多选）：A. 矩阵乘法满足结合律 (AB)C = A(BC)B. 矩阵乘法满足交换律 AB = BAC. (AB)T = ATBTD. 若 A 可逆且 AB = AC，则 B = CE. 初等行变换不改变矩阵的秩F. 单位阵左乘任意同阶矩阵都不改变该矩阵

已知 A 是 n 阶矩阵，需要多次回答「Ak 的第 (i,j) 个元素」形式的询问（同一次运行内 k 各不相同，n ≤ 200）。若每次独立做快速幂会是 O(q·n³log k)，请给出更优做法并估算复杂度。

💡 为什么 Mⁿ 里"住着"斐波那契数？

设 A 是 2×3 矩阵、B 是 3×4 矩阵。判断下列各式是否有意义，有意义的结果是几行几列：
① A·B　② B·A　③ A^T·B^T　④ (A·B)^T

给定 n×n 矩阵 A 和整数 k，求 A^k。n ≤ 100，k ≤ 10¹²，所有元素对 10⁹+7 取模。

求斐波那契数列第 n 项对 10⁹+7 取模，f(1)=f(2)=1，n ≤ 10¹⁸。

数列满足 f(1)=1，f(2)=2，f(n)=f(n−1)+f(n−2)+3（n ≥ 3）。求 f(n) mod 10⁹+7，n ≤ 10¹⁸。

给定 n 个点、m 条有向边（允许自环与重边），求从 s 到 t 恰好经过 k 条边的路径条数，对 10⁹+7 取模。n ≤ 100，k ≤ 10⁹。

数列 a(1)=1，a(n)=a(n−1)+a(n−2)+n（n ≥ 3）。构造 4×4 转移矩阵，用矩阵快速幂求 a(n) 与前缀和 S(n)=Σ_i≤na(i)。给出矩阵构造思路与验证方法。

下列说法正确的有（多选）：
A. 矩阵乘法满足结合律 (AB)C = A(BC)
B. 矩阵乘法满足交换律 AB = BA
C. (AB)^T = A^TB^T
D. 若 A 可逆且 AB = AC，则 B = C
E. 初等行变换不改变矩阵的秩
F. 单位阵左乘任意同阶矩阵都不改变该矩阵

已知 A 是 n 阶矩阵，需要多次回答「A^k 的第 (i,j) 个元素」形式的询问（同一次运行内 k 各不相同，n ≤ 200）。若每次独立做快速幂会是 O(q·n³log k)，请给出更优做法并估算复杂度。