企业官网建设流程全解析

带这期LCY算法进阶培训班之前，我把历年矩阵快速幂专题的课件重新翻了一遍。说实话，这个专题在校队训练计划里属于“看着简单，讲透很难”的类型：矩阵乘法人人都学过，快速幂也几乎是基础班标配，可把它们凑在一起后，很多同学会在转移矩阵上一卡就是一晚上。LCY培训班的本期主题定位很准，不贪多，只围绕线性递推和状态转移这两类模型，把矩阵快速幂拆成建模、构造、调参三部分来讲。本文就把这次专题训练里我觉得最值得记录的思路、模板和坑位都整理出来，适合刚学完快速幂、想在竞赛里稳定拿分的同学参考。如果你已经会写矩阵快速幂模板，重点看转移矩阵怎么构造，这部分才是拿分的关键。

1. 为什么矩阵快速幂会成为必学专题

1.1 这个专题总被放进进阶班的原因

校队训练里，矩阵快速幂一般不会在基础班讲。原因不是代码难写，而是前置知识凑齐需要时间：你至少得先懂快速幂，还得习惯矩阵乘法的“行乘列”视角，更重要的是，得能把一个递推式抽象成状态向量和转移矩阵。基础班很多同学还在用循环做斐波那契，当n到1e8就当场裂开，这时候讲矩阵快速幂，思维跨度太大。

但放到进阶班就非常合适。矩阵快速幂的知识点封闭，逻辑链短，两节课能把模板和典型题讲完，训练效果立竿见影。更重要的是，它能承接很多后续专题：概率DP里的马尔可夫转移、AC自动机上的计数DP、图上长度为k的路径统计，这些都要用到同一个套路。带训练这几年我发现，凡是这期专题认真跟下来的同学，后面学状态压缩DP和生成函数时明显轻松很多。所以LCY培训班把它放在进阶班第一周，是一个性价比很高的安排。

1.2 矩阵快速幂到底解决了什么问题

一句话概括：凡是能用“当前的若干个状态量线性组合出下一步状态”的问题，都可以尝试矩阵快速幂。最经典的场景是k阶线性递推，比如斐波那契。朴素循环算第n项是O(n)，n到1e18就完全不可行；矩阵快速幂把复杂度压到O(k^3 log n)，k是状态维度，通常只有3到10，log n大概是60，这个复杂度在竞赛题里可以轻松过。

除递推外，还有三类问题也常用它。第一是图上的路径计数，邻接矩阵的k次幂直接给出两点之间恰好走k步的方案数，这个性质在做计数题时几乎是秒杀。第二是概率期望问题，很多随机过程的“下一步概率只取决于当前分布”，本质上就是行向量乘以转移矩阵。第三是带有前缀和或多项式附加项的递推，把S(n)、n、n²这样的量也塞进状态向量里，就能统一处理。这几种场景在省选和区域赛里反复出现，所以专题训练从来不缺素材。

2. 核心原理与转移矩阵构造

2.1 快速幂的二进制思想怎么迁移到矩阵

普通快速幂求a^k，用到的核心观察是：幂次k可以拆成二进制，比如求2^100，只需要算2^64、2^32、2^4，再乘起来，而不需要连乘100次。每次把一个数平方，指数翻倍，相当于把问题规模对数缩减。你手头有1块钱，每轮允许翻倍，要凑出64块，并不需要翻倍64次，只需要6轮翻倍，这就是快速幂的生活化类比。

矩阵快速幂完全一样，只是把“一个数”换成了“一个方阵”。关键前提是矩阵乘法满足结合律，所以A^(a+b) = A^a × A^b成立。很多人担心矩阵乘法不满足交换律，其实这里用不到交换律，快速幂本身只依赖结合律。单位矩阵相当于数字里的1，任何矩阵乘单位矩阵都等于它自身，所以快速幂的初始结果矩阵设为E，而不是全零矩阵。这一点看起来基础，但真有人在这里翻车，后面排查表里还会提。

2.2 斐波那契转移矩阵的手推全过程

从最经典的递推说起。F(n) = F(n-1) + F(n-2)，已知F(1)=1，F(0)=0，求F(n)在模1e9+7下的值。

构造思路是：不要只看单个F(n)，把相邻两项打包成一个状态向量：

v(n) = [F(n), F(n-1)]^T

我们希望从v(n-1)推到v(n)，也就是：

[F(n), F(n-1)]^T = M × [F(n-1), F(n-2)]^T

矩阵M的每一行对应新状态的一个分量。第一行：F(n) = 1×F(n-1) + 1×F(n-2)，所以第一行是[1,1]；第二行：F(n-1) = 1×F(n-1) + 0×F(n-2)，所以第二行是[1,0]。于是：

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

写代码时套快速幂，答案是(M^(n-1) × v(1))的第一个分量，其中v(1) = [F(1), F(0)]^T = [1,0]^T。很多人算出来的F(n)总差一项，问题多半出在幂次多乘了一次或少乘了一次。我第一次带训时就强调一个验证方法：先用n=5手算M^4，再乘v(1)，得到的第一个值必须是5。如果第一个值是8，说明你多乘了一次；如果是3，说明少乘了一次。

2.3 n²这类多项式项怎么塞进矩阵

真正的难点来了。如果递推式里带着n²、n、常数，比如：

a(n) = 2×a(n-1) + 3×a(n-2) + n²

你会发现单独一个a(n-1)、a(n-2)不够了，n²不能写成a(n-1)的常系数组合。技巧在于：把n²也当作状态变量，用“下一步的n²可以由上一步的n²、n和1线性表示”来构造矩阵。因为从n-1走到n时，n² = (n-1)² + 2(n-1) + 1，所以只要把(n-1)²、n-1、1都放进向量里，就能精确表达。

定义旧状态v(n-1) = [a(n-1), a(n-2), (n-1)², n-1, 1]^T，新状态v(n) = [a(n), a(n-1), n², n, 1]^T。转移矩阵的每一行分别写：

• 第一行：a(n) = 2×a(n-1) + 3×a(n-2) + (n-1)² + 2×(n-1) + 1，所以是[2,3,1,2,1]
• 第二行：a(n-1)直接保留，所以是[1,0,0,0,0]
• 第三行：n² = (n-1)² + 2×(n-1) + 1，所以是[0,0,1,2,1]
• 第四行：n = (n-1) + 1，所以是[0,0,0,1,1]
• 第五行：1始终是1，所以是[0,0,0,0,1]

这样拼出来的5×5矩阵，配合初始向量，一次自乘就能算到很大步数。我自己的经验是：遇到带多项式附加项的问题，先列“从k-1到k每个分量怎么变”，再填矩阵行，比硬背模板靠谱得多。常数的本质是“步数无关的固定项”，所以单独占一个状态位；n的幂次需要几阶，就放几个连续幂次进去，直到它们能互相线性表示。

3. 模板代码和性能优化实录

3.1 一份可直接上手的C++竞赛模板

矩阵快速幂的模板代码很短，但细节决定成败。我在训练课上给过一份内部模板，核心如下：

#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007LL; struct Mat { static const int SZ = 5; int n; long long a[SZ][SZ]; Mat(int _n = 0, bool unit = false) : n(_n) { memset(a, 0, sizeof(a)); if (unit) { for (int i = 0; i < n; ++i) a[i][i] = 1; } } Mat operator*(const Mat& other) const { Mat res(n); for (int i = 0; i < n; ++i) { for (int k = 0; k < n; ++k) { if (a[i][k] == 0) continue; for (int j = 0; j < n; ++j) { res.a[i][j] = (res.a[i][j] + a[i][k] * other.a[k][j]) % MOD; } } } return res; } }; Mat qpow(Mat base, long long e) { Mat res(base.n, true); while (e > 0) { if (e & 1) res = res * base; base = base * base; e >>= 1; } return res; }

两个位置需要特别解释。第一，res(base.n, true)传的第二个参数是unit，表示初始化为单位矩阵，这直接对应“快速幂的结果初始为1”这个习惯。第二，乘法循环顺序我写的是i-k-j，而不是最直观的i-j-k，原因下一节细说。使用这个模板求斐波那契第n项时，只需要构造2×2的M和初始向量v，然后取qpow(M, n-1) × v的第一维。静态数组的好处是避免vector的动态堆分配，在反复乘法的场景下会稳定不少。

3.2 矩阵乘法的循环顺序与取模优化

矩阵乘法三重循环的顺序，看起来只是ijk的排列问题，实际会影响常数。我实测下来，i-k-j的顺序在绝大多数情况下比i-j-k快，尤其在矩阵乘法被快速幂反复调用时。原因是i-k-j的写法把a[i][k]固定在相对外层，可以在内层循环里连续使用，同时other.a[k][j]的访问更规整，缓存命中率也会好一些。我在代码里还加了一句if (a[i][k] == 0) continue，这个对稀疏矩阵很有效，比如邻接矩阵、转移矩阵中有大量0时，能省掉不少无意义计算；但如果矩阵是稠密的，加这个判断反而多花时间，要根据题目类型取舍。

取模也要注意。MOD是1e9+7时，两个long long相乘大约是1e18，在long long范围内不会溢出；但累加多轮后可能有风险，维度一大就要留神。最稳妥的做法是每轮相加后立即取模，不要等全部累加完再统一取模。如果模数接近1e18，甚至要用__int128过渡再转回long long。还有一个常用优化：当矩阵维度固定且很小，比如2×2或3×3，可以把矩阵乘法展开成具体表达式，省掉循环开销。这种写法很丑，但在反复调用时会明显提速。

3.3 用Python在本地验证建模是否正确

C++模板适合比赛，但调试时我更推荐先用Python验证思路，因为Python写起来快，而且不会因为指针和数组越界干扰判断。下面这个简易版本足够用了：

def mat_mul(A, B, mod): n = len(A) m = len(B) p = len(B[0]) C = [[0] * p for _ in range(n)] for i in range(n): for k in range(m): if A[i][k] == 0: continue for j in range(p): C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod return C def mat_pow(A, e, mod): n = len(A) R = [[1 if i == j else 0 for j in range(n)] for i in range(n)] while e: if e & 1: R = mat_mul(R, A, mod) A = mat_mul(A, A, mod) e >>= 1 return R

我在带训练时给同学定了一个死规矩：任何新题，先用Python验证转移矩阵在n=1到n=20的结果，再写C++交比赛。为什么是20？因为20以内的朴素递推可以手算或暴力循环验证，一旦前20项全对，矩阵建模基本就稳了。Python版本很慢，但验证期要的不是速度，是正确率；等验证完再用C++模板替换，实际多花的时间不超过五分钟。

4. 实战中踩过的坑与排查思路

4.1 常见矩阵快速幂错误速查表

矩阵快速幂的报错模式其实很集中，训练课上我列过一张内部速查表，这次整理出来：

这些坑每一个我都见过，其中最隐蔽的是状态向量方向的左右混淆。代码里矩阵数组a[i][j]表达第i行第j列，但公式里“左乘”还是“右乘”并不是写代码时能看出来的，必须在注释里固定一种写法：列向量统一写成v_new = M × v_old。如果一会儿写成行向量v_new = v_old × M，整个转移矩阵就要转置，很容易错乱。

4.2 典型案例复盘：图上恰好走k步的路径数

这次训练课上有一道经典题，很能说明矩阵快速幂的建模过程。题目大意是：给定一个n个点m条边的有向图，求从点s到点t恰好走k条边的方案数，k最大到1e18，结果取模。n通常不超过50，m也不算大。

做法是直接用邻接矩阵M，M[i][j]表示i到j的边数，有边记1，无记0。答案就是(M^k)[s][t]。为什么这么写？看k=2的情况，(M²)[s][t]等于对每个中间点mid求和：M[s][mid]×M[mid][t]，这正是从s经过任意一个中间点再到t的两步路径方案数。k=3时就再乘一次M，相当于继续枚举第三个中间点，每一步都由矩阵乘法的计数语义自动完成。用数学归纳法可以证明，k次乘法的结果就表示恰好k步的路径数。

需要注意两个细节。第一，k=0时，矩阵的0次幂是单位矩阵，所以从s到t恰好0步的方案数只有当s==t时为1，这正好对应“原地不动”的唯一路径。第二，如果图是无向的，邻接矩阵本身是对称的，但转移矩阵照样能用。这类题扩展也很多，比如路径长度不超过k时，可以加一个虚拟节点或把“停住”状态也建模进矩阵，不过那是后面进阶的内容了。

4.3 典型案例复盘：求前n项和的递推

另一道高频题是求斐波那契的前n项和S(n) = F(1)+F(2)+...+F(n)。最直接的方案是套恒等式S(n)=F(n+2)-1，只用一次矩阵快速幂算F(n+2)就完事。但训练课上我更推荐用增广状态的方法演示一遍，因为它能帮你理解“把目标量当作状态之一”的通用思路。

构造状态向量v(n) = [F(n), F(n-1), S(n)]^T，从v(n-1)推到v(n)：

• F(n) = F(n-1) + F(n-2)
• F(n-1) = F(n-1)
• S(n) = S(n-1) + F(n) = S(n-1) + F(n-1) + F(n-2)

所以转移矩阵M是：

[1, 1, 0] [1, 0, 0] [1, 1, 1]

初始向量v(1) = [1, 0, 1]^T，因为F(1)=1，F(0)=0，S(1)=1。验证一下：M² × v(1)可以得到[2,1,4]^T，即F(3)=2、F(2)=1、S(3)=4，手算完全一致。其实这道题用增广状态做没有恒等式快，但它展示了一种很值钱的思维：你需要的量没出现在递推式里，那就把它作为独立维度放进去。前缀和、区间和、累计次数这类问题，很多都能用同一招解决。

4.4 一个降低调试成本的独家小习惯

最后说一个我自己带训多年攒下的习惯：任何转移矩阵第一次写完，不要直接交评测，先做一个“小n验证”。具体做法是，用朴素写法跑出前10到20项，再用矩阵快速幂跑同样范围，逐项对拍。这一步能过滤掉绝大部分建模错误，包括状态向量方向、幂次差一、矩阵某行列漏写等常见问题。

我见过太多同学在矩阵快速幂上卡一整晚，最后发现只是某一行系数写反。原因是他们把调试重心放在快速幂函数上，而不是矩阵本身。实际上，快速幂的代码是成熟模板，不容易出问题；真正需要反复推理的是“这个递推式到底该怎么变成矩阵”。统一约定也很重要。我们内部的标准写法是：状态一律列向量，转移一律“新状态 = 矩阵 × 旧状态”，矩阵数组a[i][j]严格表示状态i如何由状态j贡献系数。团队协作时，这个约定能避免“我看你的代码像转置，你看我的代码像左乘”的混乱。

我个人带完这期训练班最大的感受是，矩阵快速幂是那种“建模对了，代码半小时就完事”的题。真正花时间的不是函数怎么写，而是递推式怎么塞进矩阵里。所以后来在训练里定了一条规矩：专题训练的前两题必须手推转移矩阵，写完先对拍，对拍通过再去想优化。这个小习惯帮我们减少了大量调整样例的时间。如果后续有时间，我可以把AC自动机上的矩阵DP和带环图上的计数这两类进阶题也写成单独复盘，它们其实是这个专题的自然延伸。