斐波那契数列矩阵快速幂：从线性递推到O(log n)模板

1. 从“每日一题”说起这道题的坑到底藏在哪斐波那契数列这道题几乎每个刷过算法题的人都见过。递推式 F(n) F(n-1) F(n-2)前两项 F(0)0、F(1)1让你求第 n 项。看起来是入门题但每日一题里出现它往往不是让你写个 for 循环就完事——真正卡人的地方在于 n 的取值范围。当题目把 n 顶到 10^18 这个量级任何 O(n) 的写法都会直接超时你必须换一套工具也就是矩阵乘法加快速幂。这篇东西就是围绕这一套打法展开的从为什么必须上矩阵到转移矩阵怎么推出来再到一份能直接复制进评测系统的模板最后把我自己在调试这类题时踩过的坑、对拍的方法、常数优化的细节都摊开讲清楚。适合谁看如果你刚学完矩阵乘法但还不知道怎么往题目上套这篇能帮你把“原理”和“代码”之间的那段空白补上如果你已经会写模板但老是 WA答案错误第四、五章的排查顺序表应该能省你不少时间就算你只是想找一份稳定的、不依赖第三方库的实现第三章的两版代码C 和 Python也是拿来就能用的。我下面的讲法尽量不用教科书的腔调更多是“我当时是这么想、这么写、这么调出来的”这种复盘式叙述中间会夹着不少实测数据和参数选择的理由。1.1 朴素递推的天花板在哪先算一笔账把“为什么不能直接递推”这件事量化一下。现代评测机大概每秒能跑 10^8 次简单加法运算这是个比较保守的经验值实际有波动但量级差不多。如果 n 10^18你从 F(2) 一路加过去需要 10^18 次迭代除一下就是 10^10 秒换算成年大约是 317 年。这还没算每次迭代的取模开销和数组访问开销。所以只要题目把 n 写到 10^18递推就彻底没戏这不是“慢一点”的问题是“完全不可能跑完”的问题。再往下想一层递推慢的本质是什么是它把每一步都当成独立的一步从 n-1 推到 n再从 n 推到 n1每一步只利用了前一步的结果没有“跳”的能力。而斐波那契的递推是一个线性递推线性递推有个非常好的性质——它可以被写成矩阵形式而矩阵乘法满足结合律这就给了我们“把很多步合并成一步”的空间。快速幂的思路就是利用结合律把 n 次乘法压缩成 log n 次。还有一个容易被忽略的点有些题目的 n 不大但询问次数极多。比如 10^5 组询问每组 n 到 10^6。这种情况下单次 O(n) 递推也是要挂的但你可以预处理到 10^6然后 O(1) 回答。所以判断用哪种方案得先看清题目给的是“单次大 n”还是“多次中等 n”这两种情形的应对策略不一样。矩阵快速幂解决的是前者预处理打表解决的是后者别搞混。1.2 三种常见思路的横向对比我把这道题常见的三条路线列个表方便你判断自己该走哪条。这个对比不是背下来的是我在实际做题中反复权衡后整理的经验值尤其是常数项那一列很多人只看渐进度就选错了方案。方案时间复杂度空间复杂度适用 n 范围主要风险线性递推O(n)O(1)n ≤ 10^7n 大了直接超时预处理打表O(N) 预处理 O(1) 查询O(N)多组询问N ≤ 10^7内存吃紧N 受限于空间矩阵快速幂O(log n)O(1)n 可达 10^18边界、取模、初始化容易错通项公式浮点O(1) 理论上O(1)n ≤ 70 左右浮点精度崩得快不可用最后一行特别说明一下。斐波那契有通项公式用黄金分割比那一套看着很美理论上 O(1)。但实测下来 n 到 70 左右双精度浮点就已经开始丢精度了算出来的整数部分会对不上。有人试图用高精度浮点或者对数十次方来救工程上非常麻烦性价比极低。我在早期试过一次n90 的时候结果差了 1之后就不再考虑这条路了。真正稳的、能覆盖大 n 的就是矩阵快速幂。还有一条路是对数时间的递推用 F(2k) 和 F(2k1) 的恒等式做倍增复杂度也是 O(log n)常数比矩阵还小一些但可读性和可扩展性差遇到变形题比如带常数项、带前缀和就得重新推公式。矩阵的好处是套路化——换个递推式改一下矩阵元素就行思路完全不用重新想。1.3 为什么最后还是落在矩阵乘法上原因有三条逐条讲。第一是通用性任何形如 F(n) a·F(n-1) b·F(n-2) c 的线性递推都能塞进矩阵框架里甚至带常数项、带多项式项的也能扩展。你只要会构造转移矩阵一大类题就都有了统一解法不用每道题重新推一遍数学。第二是可验证性矩阵快速幂的正确性容易用小数据暴力验证写个对拍脚本n 从 0 跑到 1000两种写法比一比不一样立刻就能定位。相比之下通项公式那种方案你连“哪一步开始错的”都很难查。第三是工程上的稳矩阵大小固定斐波那契就是 2×2乘法次数固定约 2·log₂n 次没有任何随数据变化的隐藏开销。n 10^18 的时候log₂(10^18) ≈ 60总共大约 120 次 2×2 矩阵乘法每次 8 次乘加加起来不到 1000 次运算对评测机来说是呼吸之间的功夫。这个时间完全可以预测不会出现“大数据过了小数据反而挂”的诡异情况。2. 矩阵乘法为什么能算斐波那契2.1 把递推式改写成状态向量关键的思维转换在于不要盯着“一个数”看要盯着“一组数”看。斐波那契在算第 n 项的时候其实只依赖前两项所以“此刻的状态”就是一对数 (F(n), F(n-1))。把这一对数打包成一个列向量那么从 (F(n-1), F(n-2)) 推到 (F(n), F(n-1))就是一次固定的线性变换。这个变换与 n 无关是恒定的这就是能写成矩阵的前提。具体写出来[ F(n) ] [ 1 1 ] [ F(n-1) ] [ F(n-1) ] [ 1 0 ] · [ F(n-2) ]验证一下第一行1·F(n-1) 1·F(n-2) F(n-1) F(n-2) F(n)正好是递推式。第二行1·F(n-1) 0·F(n-2) F(n-1)也对。所以中间那个 2×2 矩阵就是转移矩阵我后面统一叫它 M。这里有个细节值得说为什么转移矩阵要写成 2×2而不是 1×2 或者别的形状因为你要求的是 F(n)它依赖两项状态向量的维度就必须是 2矩阵就得是 2×2。如果递推式依赖三项比如 F(n) a·F(n-1) b·F(n-2) c·F(n-3)那状态向量就是三维矩阵是 3×3。维度永远等于依赖的项数这是个可以直接套的规律不用每次都重新想。2.2 转移矩阵的构造与下标对齐矩阵的构造本身不难难的是下标对齐。这一步错了代码跑出来的结果会整体偏移一位很容易蒙对几个测试点。我的做法是从基准状态开始推。设基准是 (F(1), F(0)) (1, 0)也就是状态向量 S₁。那么 S₂ M·S₁S₃ M²·S₁依此类推S_n M^(n-1) · S₁写成坐标形式F(n) 就是向量 M^(n-1)·S₁ 的第一个分量。而 S₁ (1, 0)ᵀ所以 M^(n-1) 乘以 (1,0)ᵀ 得到的就是 M^(n-1) 的第一列取第一个元素正好是 M^(n-1) 的 (0,0) 位置。结论很干净当 n ≥ 1 时F(n) (M^(n-1))[0][0]。这个式子的好处是不需要额外构造向量做乘法直接读矩阵的一个元素就行代码能少一行出错的概率也低。我用小数据验一遍确认不会偏移n1M⁰ 是单位矩阵[0][0]1F(1)1对。n2M¹[0][0]1F(2)1对。n3M² [[2,1],[1,1]][0][0]2F(3)2对。n4M³ [[3,2],[2,1]][0][0]3对。四个点都对上了这个式子可以放心用。顺便提另一种等价写法如果你把 F(0)、F(1) 作为基准也可以写成 F(n) (M^n)[0][1]同样正确。但这种写法在 n0 时要特殊处理容易忘。我倾向用 n-1 那种虽然多一个特判 n0但整体更清晰。2.3 快速幂把线性次迭代压成对数次矩阵的幂靠的是结合律。M^a · M^b M^(ab)所以 M^8 ((M²)²)²只需要 3 次乘法而不是 7 次。这就是快速幂的全部思想没有任何玄机。具体做法是二进制拆分。把指数 n 写成二进制从低位往高位扫维护两个量base 表示“当前二进制位对应的幂次”res 表示“已经累积的答案”。res 单位矩阵 base M while n 0: if n 1: res res * base base base * base n 1举 n 13 的例子13 1101₂。循环过程是这样的轮次n 的二进制n 1res 变化base 变化111011I → M¹M → M²21100不变M² → M⁴3111M¹ → M⁵M⁴ → M⁸411M⁵ → M¹³M⁸ → M¹⁶最后 res M¹³正确。整个过程 4 轮做了大约 6 次矩阵乘法而暴力要 13 次。n 越大差距越明显n 10^18 时约 60 轮120 次左右乘法暴力是 10^18 次量级上的差距不需要再解释了。这里有两个地方特别容易翻车我单独拎出来。一是 res 的初值必须是单位矩阵不能是零矩阵也不能是 M 本身。单位矩阵在矩阵乘法里相当于数字 1乘任何矩阵都不变这是唯一正确的初值。二是 base 要被反复平方所以传参的时候得按值传或者先复制一份别在主函数里把原始矩阵给覆盖了后面还要用。3. 手把手实现一版能过题的矩阵快速幂3.1 C 版本结构体封装与完整实现先给能直接编译提交的版本。我习惯用结构体包一层好处是后面换成 3×3 的时候只要改数组维度循环边界跟着改常量就行逻辑不用重写。取模的那个常量我这里按常见的 10^97 写实际做题时按题目要求改。#include bits/stdc.h using namespace std; typedef long long ll; const ll MOD 1000000007LL; struct Mat { ll a[2][2]; Mat() { memset(a, 0, sizeof(a)); } // 关键默认清零 }; Mat mul(const Mat x, const Mat y) { Mat z; for (int i 0; i 2; i) { for (int k 0; k 2; k) { if (x.a[i][k] 0) continue; // 稀疏优化 for (int j 0; j 2; j) { z.a[i][j] (z.a[i][j] x.a[i][k] * y.a[k][j]) % MOD; } } } return z; } Mat qpow(Mat base, ll e) { Mat res; res.a[0][0] res.a[1][1] 1; // 单位矩阵 while (e 0) { if (e 1) res mul(res, base); base mul(base, base); e 1; } return res; } ll fib(ll n) { if (n 0) return 0; if (n 2) return 1 % MOD; Mat M; M.a[0][0] 1; M.a[0][1] 1; M.a[1][0] 1; M.a[1][1] 0; Mat P qpow(M, n - 1); return P.a[0][0] % MOD; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n; while (cin n) { cout fib(n) \n; } return 0; }几个地方说明一下。构造函数里那句memset是必须的我见过太多人卡在这里——局部变量不初始化里面是随机垃圾值结果完全不可预测有时候小数据能过大数据挂有时候反过来排查起来极其痛苦。宁可在结构体里多做一次清零也不要赌运气。mul里的循环顺序用的是 i-k-j 而不是教科书上常见的 i-j-k。这个顺序在 2×2 的规模下影响不大但换成大矩阵时差别就很明显了因为 i-k-j 对 z 的访问是连续的缓存友好。同一个习惯我一直保持下来改规模的时候不用重写。if (x.a[i][k] 0) continue;这行是稀疏优化。2×2 的矩阵里 0 不少单位矩阵、M 本身都有一个 0跳过能省一点。规模小的时候是锦上添花但写习惯了不亏。qpow的第一个参数是按值传的因为函数内部会修改它。如果你写成引用主函数里的 M 就被平方好几次了后面再用就全乱。这个坑我踩过调了半小时才反应过来。3.2 Python 版本与无模大数场景Python 的版本更适合用在“结果不取模”或者“n 不算特别大但要精确值”的场合。Python 的整数是任意精度的所以你不需要管溢出代价是数字位数多了之后乘法会变慢——斐波那契第 10^6 项大约有 20 万位十进制数字那时候乘法开销就不能忽略了。MOD 10 ** 9 7 def mat_mul(x, y, modNone): a, b x[0][0], x[0][1] c, d x[1][0], x[1][1] e, f y[0][0], y[0][1] g, h y[1][0], y[1][1] m mod if mod else (lambda v: v) return [ [m(a * e b * g), m(a * f b * h)], [m(c * e d * g), m(c * f d * h)], ] def fib(n, modMOD): if n 0: return 0 if n 2: return 1 % mod res [[1, 0], [0, 1]] base [[1, 1], [1, 0]] e n - 1 while e: if e 1: res mat_mul(res, base, lambda v: v % mod) base mat_mul(base, base, lambda v: v % mod) e 1 return res[0][0] % mod print(fib(10)) # 55 print(fib(50)) # 12586269025 print(fib(10**18)) # 走模运算瞬间出结果mat_mul里我把 2×2 展开成 8 个标量运算没有用嵌套循环。原因是 Python 的循环开销远大于表达式求值展开之后速度提升相当明显我实测过大约快 2.5 倍。看起来不优雅但 Python 里为了性能这种展开是常规操作。m那个参数设计成可传可不传是为了同一个函数兼顾“取模”和“不取模”两种需求。写成lambda v: v稍微绕你也可以直接在调用处传None然后判断看个人习惯。这里没有用pow之类的高级特性是为了让逻辑对新手透明。如果题目要求精确值不取模把modNone传进去就行Python 会自动处理大整数。但注意n 到 10^6 以上的时候会明显变慢那时候不如理解成“这题本来就不该用 Python 硬扛大数”更实际。3.3 用暴力对拍验证正确性模板写完不能直接交得先跟自己确认它是对的。我的固定动作是写个小对拍用递推做标准答案跟矩阵版本逐项比。def fib_brute(n): a, b 0, 1 for _ in range(n): a, b b, a b return a bad [] for i in range(0, 200): if fib(i) ! fib_brute(i) % MOD: bad.append(i) print(mismatch:, bad if bad else none)跑一遍输出none就说明前 200 项全对。这一步花不到三十秒但能把下标偏移、单位矩阵初值、边界特判这三类错误一次性全部筛掉。很多人跳过这步直接交结果 WA 了之后回头找反而更费时间。我的态度很明确模板是一次性投入对拍是廉价保险没有理由不做。C 那边同理把暴力版本写进main里加个#ifdef DEBUG包裹提交前把宏去掉就行不影响最终代码的整洁。4. 核心参数与边界处理4.1 取模和溢出什么时候该上 __int128取模这件事看着简单实则是最容易让代码“本地能跑、提交就挂”的环节之一。核心问题是乘法溢出。假设模数是 M矩阵元素都是小于 M 的两个元素相乘最大是 (M-1)²。当 M 10^9 时(10^9)² 10^18而long long的上限约 9.22×10^18还留了将近一个数量级的余量安全。但如果题目把模数改成 10^18 这种量级呢(10^18)² 10^36long long直接溢出结果完全不可信。这种时候有两个选择一是用__int128GCC 系编译器支持蓝桥杯的 C 环境一般没问题二是用龟速乘把乘法拆成加法O(log) 复杂度的乘法。前者简单后者可移植。我一般优先用__int128因为代码改动最小typedef __int128 i128; ll mul_mod(ll a, ll b, ll m) { return (ll)((i128)a * b % m); }还有一个隐蔽的坑负数取模。C 里-1 % 1000000007结果是 -1不是 1000000006。如果你的中间结果可能为负比如做减法、或者从别的题改过来的代码记得统一处理成(x % MOD MOD) % MOD。斐波那契这题本身全是加法不会出负但你要是在它基础上改造成带减法的递推就得留意。第三个坑是取模的位置。有人为了“减少取模次数提升性能”把取模挪到循环外面结果中间累加爆炸。我的原则是每次加法之后立刻取模不要攒。2×2 的规模下取模开销可以忽略为省这点时间冒溢出的风险完全不值。4.2 下标和 n 的取值边界斐波那契的边界值是最经典的陷阱区。题目里 n 的定义有时候从 0 开始有时候从 1 开始有时候干脆写“第 n 项”让你猜。你得看样例别凭感觉。我总结的对应关系是这样的n 的取值F(n) 的值代码是否要特判n 00要直接返回 0n 11建议特判避免走幂运算n 21可选n-11 时也能算对n ≥ 3正常走矩阵不需要对应的处理if (n 0) return 0; if (n 2) return 1 % MOD;1 % MOD这个写法看似多余其实有意义。如果模数是 1虽然斐波那契题里极少见1 % 1 0才是正确答案直接return 1就错了。这种防御性写法成本几乎为零我一般都会加上。还有一个场景f(0) 特判和qpow(M, n-1)的配合。如果 n 是long long且可能为 0n-1会变成 -1然后qpow里的while (e 0)直接不进循环返回单位矩阵[0][0] 1但你期望是 0。这就是为什么 n0 必须单独拦截不能靠快速幂自己兜底。4.3 多组测试与模板复用每日一题的输入格式经常是“第一行 T后面 T 行每行一个 n”。这种多组输入下有两个常见失误。第一个是忘记重置。如果你把矩阵定义成全局变量然后反复修改第二组数据就会继承第一组的残留状态。解决办法很简单——所有矩阵都在函数内部定义靠构造函数清零不搞全局。我上面给的模板就是这个思路fib函数每次调用都重新构造 M 和 P互不影响。第二个是读入超时。T 到 10^5 级别的时候cin不加优化会明显拖慢。那两行ios::sync_with_stdio(false); cin.tie(nullptr);是标配写上就是了没有副作用。如果题目允许甚至可以把幂运算抽成一个通用的模板函数换成任意递推式只改矩阵元素的赋值。我自己的代码库里就留了这么一个template int N struct Matrix { ll a[N][N]; Matrix() { memset(a, 0, sizeof(a)); } static Matrix identity() { Matrix r; for (int i 0; i N; i) r.a[i][i] 1; return r; } };模板参数 N 决定了维度2×2、3×3 都能直接用加个mul和qpow就齐活。写熟了之后遇到线性递推的题基本就是“填矩阵、调模板、跑对拍”三步。5. 常见问题与排查实录5.1 答案错了一半按这个顺序查调试这类代码最忌讳漫无目的地改。我给自己定了一个固定的检查顺序从最可能出错的地方往下走通常前三步就能定位问题。第一步检查下标偏移。拿 n3 和 n4 手动算一遍看代码输出是不是 2 和 3。如果输出是 1 和 2说明整体少算了一项多半是qpow的指数写成了 n 而不是 n-1或者基准状态的假设错了。这一步能解决大概四成的错误。第二步检查单位矩阵。在qpow里把res打印出来确认对角线是 1、其余是 0。我见过有人写res.a[0][1] res.a[1][0] 1把单位矩阵和转移矩阵搞混了结果小数据碰巧过、大数据全崩。第三步检查清零。在mul函数开头打印 z 的初始值如果出现随机大数说明构造函数没生效或者你压根没写。这类错误在 C 里特别常见尤其是把Mat z;声明成局部变量又忘了初始化的时候。第四步检查溢出。把MOD临时改成一个小值比如 100000再跑一遍。如果结果变了说明原本的计算路径里存在溢出。这一步的思路是“缩小规模观察异常”很有效。第五步才是检查矩阵元素填错、循环边界写错这类笔误。放到最后不是因为它们少见而是因为前三步的排查成本更低、命中率更高。5.2 常见问题速查表把上面这些整理成一张表出问题的时候直接对号入座。这张表是我自己攒的覆盖了我遇到的九成以上情况。现象最可能的原因快速验证方法修复全部输出 0忘记初始化 res 为单位矩阵打印 res对角线置 1输出比正确值小一档下标偏移多算或少算一项手算 n3、n4调整指数为 n-1小数据对、大数据错乘法溢出把 MOD 改小重跑换 long long / __int128输出负数取模前有减法打印中间值(x%MODMOD)%MOD多组数据第二组开始错全局变量未重置单独跑第二组改为局部变量n0 时输出 1缺少边界特判直接输入 0加 n0 分支结果随机跳动局部矩阵未清零打印 z 初值加 memset编译报错找不到 __int128编译器不支持—改用龟速乘再补一条表格里放不下的如果你试图对指数取模来“加速”那是错的。有人看到模数 10^97 就想着用费马小定理把 n 降到 (MOD-1) 的范围但费马小定理针对的是整数底数矩阵在模意义下一般并不满足 A^(p-1) ≡ I。这个操作会导致结果完全错误而且错得很隐蔽——小 n 的时候看不出来大 n 直接崩。指数该多大就多大靠快速幂的对数复杂度去扛别动歪脑筋。5.3 常数优化能省的地方和省不了的地方2×2 矩阵快速幂本身已经够快了n 10^18 也就百来次乘法优化空间其实很小。但如果你在写更复杂的版本比如 3×3、4×4或者嵌套在别的算法里这些技巧就有意义了。第一减少取模。当模数小于 2^31 时两个元素相乘的结果在long long里能存下好几轮累加可以攒几次再加一起取模。但 2×2 的场景下收益微乎其微我一般不折腾避免引入溢出风险。第二手动展开循环。把i-k-j三重循环展开成 8 条赋值语句能省掉循环变量开销。实测在 10^6 次调用的量级上大约快 30%但普通题目根本用不到这么多次属于过度优化。第三循环顺序用 i-k-j。这个前面提过原理是让内层循环访问连续内存。2×2 时无所谓换成 50×50 的时候差距能到两三倍。第四别用vectorvectorll。嵌套 vector 的每次访问都要两次指针跳转比原生二维数组慢一个量级。固定维度的题老老实实用ll a[2][2]。反过来有些“优化”是没必要的比如为了省一次矩阵乘法而特殊处理 n 的奇偶其实快速幂的if (e 1)已经天然处理了比如用位运算替代取模仅当模数是 2 的幂时可行斐波那契题里模数几乎不会是 2 的幂用不上。6. 从这一道题延伸出去的几个方向6.1 前缀和、广义递推与三阶矩阵原题只要求第 n 项但变体题经常加码。最常见的是求前 n 项和 S(n) F(1) F(2) ... F(n)。有个漂亮的性质可以直接用S(n) F(n2) - 1。所以只要把矩阵快速幂多算一项就完事代码几乎是原封不动ll fib_sum(ll n, ll MOD) { // S(n) F(n2) - 1 ll v (fib(n 2) - 1) % MOD; return (v MOD) % MOD; }注意那个MOD减法之后必须拉回非负区间这是最典型的负数取模场景。我在前面强调过这里正好用上。另一个思路是不用恒等式直接把前缀和塞进状态向量构造 3×3 矩阵[ F(n) ] [ 1 1 0 ] [ F(n-1) ] [ F(n-1) ] [ 1 0 0 ] · [ F(n-2) ] [ S(n) ] [ 1 1 1 ] [ S(n-1) ]第三行展开1·F(n-1) 1·F(n-2) 1·S(n-1) F(n) S(n-1) S(n)对上了。这种写法的好处是不依赖恒等式遇到“前缀和再套前缀和”这种变态需求也能一层层加维度往上堆。代价是每次乘法从 8 次乘加变成 27 次n 大的时候常数明显变大所以能用恒等式就别用 3×3。再往远一点形如 F(n) a·F(n-1) b·F(n-2) 的广义递推转移矩阵就是 [[a, b], [1, 0]]。带常数项 c 的比如 F(n) F(n-1) F(n-2) c就升到 3×3[ F(n) ] [ 1 1 1 ] [ F(n-1) ] [ F(n-1) ] [ 1 0 0 ] · [ F(n-2) ] [ c ] [ 0 0 1 ] [ c ]第三行恒等于 c就是用来“保持”这个常数项的。这个套路可以一直往上加带 n 的一次项、二次项都能塞进去维度跟着涨思路完全不变。6.2 还有哪些题能用这套打法矩阵快速幂不只服务斐波那契。凡是“状态转移是线性的、转移规则与步数无关”的题都能套。我整理几类常见的。第一类是路径计数。给定一个有向图问从 A 走到 B 恰好 k 步有多少条路径。把邻接矩阵当成转移矩阵求它的 k 次幂结果矩阵的 (A,B) 元素就是答案。原理是矩阵乘法的定义恰好对应“枚举中间点”这个对应关系非常漂亮。k 到 10^18 的时候只有快速幂能救。第二类是线性递推加速 DP。有些 DP 题的转移方程是线性的、只依赖前几项状态数不多但步数极多。这时候把状态打包成向量转移写成矩阵步数就变成了指数同样是 O(log n)。第三类是图上带权路径。求恰好 k 步的最短路径用广义矩阵乘法把乘换成加、把加换成取 min同样能快速幂。这个属于进阶用法需要额外注意单位元的定义加法单位元是 0min 的单位元是无穷大容易在初始化上翻车。第四类是字符串匹配的自动机加速。把状态机写成转移矩阵问走 n 步后落在各状态的方案数。这类题看起来跟斐波那契没关系但内核一模一样。我不建议一上来就去啃这些变体。先把斐波那契这一道彻底吃透——能手推转移矩阵、能默写快速幂、能自己写出对拍、能一眼看出边界——再去扩展。基础不牢的时候去碰 3×3、4×4只会把错误放大调起来更痛苦。最后分享一个我自己一直在用的小习惯每写完一个矩阵快速幂的模板我都会在代码顶部加一行注释写清楚“状态向量的定义”和“转移矩阵的含义”。隔两周再回来看没有这行注释我大概率要重新推一遍矩阵反而更慢。模板这种东西写一次要用很多次多花三十秒写注释后面能省无数次推导。