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 推到 n+1，每一步只利用了前一步的结果，没有“跳”的能力。而斐波那契的递推是一个线性递推，线性递推有个非常好的性质——它可以被写成矩阵形式，而矩阵乘法满足结合律，这就给了我们“把很多步合并成一步”的空间。快速幂的思路就是利用结合律，把 n 次乘法压缩成 log n 次。

还有一个容易被忽略的点：有些题目的 n 不大，但询问次数极多。比如 10^5 组询问，每组 n 到 10^6。这种情况下单次 O(n) 递推也是要挂的，但你可以预处理到 10^6，然后 O(1) 回答。所以判断用哪种方案，得先看清题目给的是“单次大 n”还是“多次中等 n”，这两种情形的应对策略不一样。矩阵快速幂解决的是前者，预处理打表解决的是后者，别搞混。

1.2 三种常见思路的横向对比

我把这道题常见的三条路线列个表，方便你判断自己该走哪条。这个对比不是背下来的，是我在实际做题中反复权衡后整理的经验值，尤其是常数项那一列，很多人只看渐进度就选错了方案。

最后一行特别说明一下。斐波那契有通项公式，用黄金分割比那一套，看着很美，理论上 O(1)。但实测下来 n 到 70 左右，双精度浮点就已经开始丢精度了，算出来的整数部分会对不上。有人试图用高精度浮点或者对数十次方来救，工程上非常麻烦，性价比极低。我在早期试过一次，n=90 的时候结果差了 1，之后就不再考虑这条路了。真正稳的、能覆盖大 n 的，就是矩阵快速幂。

还有一条路是对数时间的递推（用 F(2k) 和 F(2k+1) 的恒等式做倍增），复杂度也是 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]。这个式子的好处是不需要额外构造向量做乘法，直接读矩阵的一个元素就行，代码能少一行，出错的概率也低。

我用小数据验一遍，确认不会偏移：n=1，M⁰ 是单位矩阵，[0][0]=1，F(1)=1，对。n=2，M¹[0][0]=1，F(2)=1，对。n=3，M² = [[2,1],[1,1]]，[0][0]=2，F(3)=2，对。n=4，M³ = [[3,2],[2,1]]，[0][0]=3，对。四个点都对上了，这个式子可以放心用。

顺便提另一种等价写法：如果你把 F(0)、F(1) 作为基准，也可以写成 F(n) = (M^n)[0][1]，同样正确。但这种写法在 n=0 时要特殊处理，容易忘。我倾向用 n-1 那种，虽然多一个特判 n=0，但整体更清晰。

2.3 快速幂：把线性次迭代压成对数次

矩阵的幂，靠的是结合律。M^a · M^b = M^(a+b)，所以 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₂。循环过程是这样的：

最后 res = M¹³，正确。整个过程 4 轮，做了大约 6 次矩阵乘法，而暴力要 13 次。n 越大差距越明显，n = 10^18 时约 60 轮，120 次左右乘法，暴力是 10^18 次，量级上的差距不需要再解释了。

这里有两个地方特别容易翻车，我单独拎出来。一是 res 的初值必须是单位矩阵，不能是零矩阵，也不能是 M 本身。单位矩阵在矩阵乘法里相当于数字 1，乘任何矩阵都不变，这是唯一正确的初值。二是 base 要被反复平方，所以传参的时候得按值传或者先复制一份，别在主函数里把原始矩阵给覆盖了，后面还要用。

3. 手把手实现一版能过题的矩阵快速幂

3.1 C++ 版本：结构体封装与完整实现

先给能直接编译提交的版本。我习惯用结构体包一层，好处是后面换成 3×3 的时候只要改数组维度，循环边界跟着改常量就行，逻辑不用重写。取模的那个常量我这里按常见的 10^9+7 写，实际做题时按题目要求改。

#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, mod=None): 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, mod=MOD): 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之类的高级特性，是为了让逻辑对新手透明。

如果题目要求精确值（不取模），把mod=None传进去就行，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^36，long long直接溢出，结果完全不可信。这种时候有两个选择：一是用__int128（GCC 系编译器支持，蓝桥杯的 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 项”让你猜。你得看样例，别凭感觉。

我总结的对应关系是这样的：

对应的处理：

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且可能为 0，n-1会变成 -1，然后qpow里的while (e > 0)直接不进循环，返回单位矩阵，[0][0] = 1，但你期望是 0。这就是为什么 n=0 必须单独拦截，不能靠快速幂自己兜底。

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 答案错了一半？按这个顺序查

调试这类代码，最忌讳漫无目的地改。我给自己定了一个固定的检查顺序，从最可能出错的地方往下走，通常前三步就能定位问题。

第一步，检查下标偏移。拿 n=3 和 n=4 手动算一遍，看代码输出是不是 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 常见问题速查表

把上面这些整理成一张表，出问题的时候直接对号入座。这张表是我自己攒的，覆盖了我遇到的九成以上情况。

再补一条表格里放不下的：如果你试图对指数取模来“加速”，那是错的。有人看到模数 10^9+7 就想着用费马小定理把 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 的时候差距能到两三倍。

第四，别用vector<vector<ll>>。嵌套 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(n+2) - 1。所以只要把矩阵快速幂多算一项就完事，代码几乎是原封不动：

ll fib_sum(ll n, ll MOD) { // S(n) = F(n+2) - 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），同样能快速幂。这个属于进阶用法，需要额外注意单位元的定义（加法单位元是 0，min 的单位元是无穷大），容易在初始化上翻车。

第四类是字符串匹配的自动机加速。把状态机写成转移矩阵，问走 n 步后落在各状态的方案数。这类题看起来跟斐波那契没关系，但内核一模一样。

我不建议一上来就去啃这些变体。先把斐波那契这一道彻底吃透——能手推转移矩阵、能默写快速幂、能自己写出对拍、能一眼看出边界——再去扩展。基础不牢的时候去碰 3×3、4×4，只会把错误放大，调起来更痛苦。

最后分享一个我自己一直在用的小习惯：每写完一个矩阵快速幂的模板，我都会在代码顶部加一行注释，写清楚“状态向量的定义”和“转移矩阵的含义”。隔两周再回来看，没有这行注释，我大概率要重新推一遍矩阵，反而更慢。模板这种东西，写一次要用很多次，多花三十秒写注释，后面能省无数次推导。