刷到这道蓝桥杯每日一题的标题时，我第一反应是“斐波那契还能玩出什么花样”，看到括号里的矩阵乘法四个字，心里立刻有数了：这题考的不是你会不会写f(n) = f(n-1) + f(n-2)，而是考你在n大到 10^18 这个量级时，还能不能把答案在 1 秒内算出来。斐波那契数列本身简单到小学生都能手算前十几项，0、1、1、2、3、5、8、13……，可一旦题目把n拉到一亿、十亿甚至更大，裸递推就彻底没戏了，循环次数直接爆炸。矩阵乘法配上快速幂，就是专门用来对付这类“线性递推 + 超大下标”问题的标准武器，把 O(n) 的线性时间压到 O(log n)，代价只是多写几行矩阵乘法的代码。这道每日一题适合三类人看：刚接触蓝桥杯、还停留在暴力递推阶段的同学；知道矩阵快速幂这个词但一直没写对过的同学；以及刷过几道同类题、想一次性把这个模板固化下来的人。下面我按自己的解题顺序，把这题从思路到代码、从踩坑到变式，完整捋一遍。

1. 从递推到矩阵：为什么 n 一大递推就废了

1.1 暴力递推的时间账要先算清楚

很多人拿到题的第一反应是开个数组或者用两个变量滚动，写一个for循环从 2 跑到 n，三行代码搞定。这种写法在小数据上完全正确，蓝桥杯的样例往往也都能过，问题出在数据范围上。假设评测数据给出n = 10^18，你写的是线性递推，那循环就要跑 10^18 次；按一台普通机器每秒执行 10^8 次简单加法来估算，需要的时长大约是 10^10 秒，换算下来是三百多年。这个数量级已经不能用“慢”来形容了，它根本不在可计算的范畴里。

我刚开始刷这类题的时候也吃过亏，本地用n = 100000测了一遍，跑了不到一毫秒，心里还挺得意，交上去直接 TLE。原因很简单：本地测的是小样本，真正的评测点藏在后面。所以看到斐波那契三个字，第一件事不是写代码，而是翻数据范围。只要n的上界超过 10^7 这个量级，线性递推基本可以判死刑，必须换思路。

这里有个细节值得强调：取模。题目几乎不会让你输出完整的斐波那契数，因为f(100)就已经是 21 位数，f(1000)有 209 位，根本存不下。常见做法是让你对某个模数取余，比如 10^9+7、10^4 或者 100000000。取模这个条件其实是好事，它保证了中间结果始终在可控范围内，不会出现大整数溢出的问题，这也是矩阵乘法能顺利跑起来的前提。

1.2 线性递推为什么能被矩阵“压缩”

斐波那契的递推式f(n) = f(n-1) + f(n-2)有一个非常好的性质：它是线性的，而且阶数固定为 2。也就是说，只要我知道连续的两项f(n-1)和f(n-2)，就能唯一确定下一项；再往下每一项，都只依赖前两项的线性组合，系数恒为 1 和 1，全程不变。

这个“系数不变”是关键。如果递推式的系数随n变化，比如f(n) = n * f(n-1) + f(n-2)，那矩阵的每一层都不一样，就没法用同一个矩阵反复自乘了。而斐波那契的系数是常数，意味着从状态(f(n-1), f(n-2))到状态(f(n), f(n-1))的变换，永远可以用同一个 2×2 矩阵表示。既然每一步都是乘同一个矩阵，那从第 0 项推到第 n 项，等价于把这个矩阵自乘 n 次。

用生活化的说法打个比方：递推像是每天手工记账，一天一天往下加；矩阵乘法像是找到了一个“复利公式”，一次就能算出若干天之后的总账。这个公式的正确性不依赖于你加了多少天，只依赖于变换规则本身是固定的。理解了这一层，矩阵快速幂就不神秘了，它就是“同一个变换重复 n 次”的高效算法，和整数快速幂是同一个套路，只不过底数从数字换成了矩阵。

1.3 O(log n) 到底省在哪儿

快速幂的核心思想是二进制拆分。要算 M^13，不需要乘 13 次，而是把 13 拆成1101，也就是8 + 4 + 1，那么 M^13 = M^8 × M^4 × M^1。而 M^2 = M × M，M^4 = M^2 × M^2，M^8 = M^4 × M^4，每一项都可以由前一项平方得到。整个过程只需要约 log2(13) ≈ 4 次平方加上若干次乘法，加起来也就七八次矩阵乘法。

把这个思路套到n = 10^18上，log2(10^18) ≈ 59.79，也就是最多 60 轮循环。每轮循环里做一次平方，遇到二进制位为 1 时再做一次乘法，最坏情况约 60 次平方 + 60 次乘法 = 120 次 2×2 矩阵乘法。一次 2×2 矩阵乘法是 8 次乘法和 4 次加法，总共不到一千次基本运算。和三百多年的暴力方案比，这就是一瞬间的事。

下面这张表是我自己整理的量级对照，做题时拿来快速判断用哪种写法很实用：

最后一行是个容易被忽略的知识点：某些题给的不是 long long 范围的 n，而是一个长度上千位的十进制字符串。这时不能直接读成整数，要先把指数按模数相关的方式降下来再算，这个后面在变式部分再展开。

2. 转移矩阵是怎么“凑”出来的

2.1 状态向量的选法决定了矩阵长什么样

构造转移矩阵的第一个问题不是矩阵，而是状态向量。要转移，先得把“当前的已知信息”打包成一个向量。斐波那契的第二项依赖前两项，所以最小状态就是两项：[f(n), f(n-1)]。选这两项而不是别的，原因是递推式的“记忆长度”是 2，你只要记住最近两项，后面全都能推出来，多记一项是浪费，少记一项则推不动。

状态确定之后，下一步是写出“下一状态”的表达。下一状态是[f(n+1), f(n)]，其中f(n+1) = f(n) + f(n-1)，f(n) = f(n)（原样保留）。把这两行写出来，矩阵就自动浮现了：

[ f(n+1) ] [ 1 1 ] [ f(n) ] [ f(n) ] = [ 1 0 ] × [ f(n-1) ]

第一行对应1 × f(n) + 1 × f(n-1)，第二行对应1 × f(n) + 0 × f(n-1)，正好对上。这就是那个经典的[[1,1],[1,0]]的来源。我一直觉得这个矩阵不该背，因为它是推出来的，不是记出来的。真正需要记住的是方法：写出下一状态，看它由哪些前项以什么系数组合而成，系数填进矩阵的行，就完事了。

我见过不少同学把这个矩阵和另一个长得像的搞混，比如写成[[0,1],[1,1]]或者[[1,0],[1,1]]。这类错误在本地跑小数据时往往能蒙对前几项，因为初始向量是[1, 0]或[1, 1]，零元素的位置会让错误矩阵碰巧算出正确结果，一旦 n 变大就全错。我建议的做法是：写完矩阵，手工验算一两步。用[f(1), f(0)] = [1, 0]去乘，看是不是得到[1, 1]，再乘一次看是不是[2, 1]。两分钟的手工验证，能省掉半小时的调试。

2.2 幂次到底该取 n 还是 n-1

这是我第一次写这题时最容易乱的地方。状态向量选[f(n), f(n-1)]，那么从初始状态[f(1), f(0)] = [1, 0]出发，要乘多少次矩阵才能到[f(n), f(n-1)]？答案是n-1次。因为每乘一次，下标前进一位，从 1 走到 n 需要走n-1步。

于是有：

[ f(n) ] [ 1 1 ]^(n-1) [ 1 ] [ f(n-1) ] = [ 1 0 ] × [ 0 ]

由于右边那个向量是[1, 0]，乘完之后结果向量的第一项就等于矩阵第一行第一列的元素。所以最终答案可以直接取M^(n-1)的左上角元素，连向量乘法都可以省掉。这个小优化很实用，代码能少写几行。

但要注意两个边界：n = 0时答案是 0，n = 1时答案是 1。如果直接用M^(n-1)，n = 1时幂次是 0，任何矩阵的 0 次幂是单位阵，左上角是 1，正确；n = 0时幂次是 -1，直接崩，必须特判。我自己的习惯是开头统一处理n <= 1的情况直接返回 n，剩下的代码就能安心假设n >= 2。

还有另一种常见的状态选法，用[f(n+1), f(n)]作为初始向量，配合M^n，结果取左下角。这两种写法数学上完全等价，只是下标起点不同。我见过有人把两种写法混着用，前半段按n-1算，取答案时又按n的位置取，结果差了一项，本地跑 n=10 得 89 而不是 55，一眼就能看出来。选一种并坚持到底，比什么都重要。

2.3 换一个递推式，矩阵要怎么变

真正把这道每日一题吃透的标志，不是能默写出斐波那契的矩阵，而是遇到新的线性递推时能两分钟内把矩阵写出来。举个常见的变形：g(n) = 3 * g(n-1) + 2 * g(n-2)，初始g(0) = 1, g(1) = 2。状态还是[g(n), g(n-1)]，下一状态[g(n+1), g(n)]，其中g(n+1) = 3g(n) + 2g(n-1)，g(n) = g(n)，矩阵就是[[3,2],[1,0]]。

再复杂一点，带上常数项：h(n) = h(n-1) + h(n-2) + 5。这时候光靠[h(n), h(n-1)]推不动了，因为常数 5 不在状态里。解决办法是扩维，把常数 1 也塞进状态向量，变成[h(n), h(n-1), 1]，矩阵扩成 3×3：

[ h(n+1) ] [ 1 1 5 ] [ h(n) ] [ h(n) ] = [ 1 0 0 ] × [ h(n-1) ] [ 1 ] [ 0 0 1 ] [ 1 ]

第三行0 0 1保证常数项恒为 1，第一行的 5 就是那个附加常数。这个扩维技巧是矩阵加速递推的通用套路：递推式里出现什么“不随 n 变化的东西”，就把它作为一维放进状态；出现n的一次项，就把n和1都放进去，用n+1 = n + 1来转移。掌握了这套方法，蓝桥杯里绝大部分线性递推的压轴题都有了解法框架。

3. 矩阵快速幂的代码实现与工程细节

3.1 结构体封装与乘法函数的写法

C++ 里我习惯用结构体包一个二维数组，原因是传参清晰、不会和别处的数组重名，而且 2×2 的固定大小可以用memset快速清零。核心的乘法函数按最朴素的三重循环写就够了，i-k-j的顺序对缓存友好，而且能在内层提前跳过零元素。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1000000007; struct Mat { ll v[2][2]; Mat() { memset(v, 0, sizeof v); } // 默认全零 }; Mat mul(const Mat &A, const Mat &B) { Mat C; for (int i = 0; i < 2; ++i) for (int k = 0; k < 2; ++k) { if (A.v[i][k] == 0) continue; // 小优化，跳过零 for (int j = 0; j < 2; ++j) C.v[i][j] = (C.v[i][j] + A.v[i][k] * B.v[k][j]) % MOD; } return C; }

这里有两个细节要说清楚。第一，C是在乘法函数内部构造的局部变量，构造函数里做了memset清零，所以不用手动初始化，这一点比自己管理数组省心得多。第二，A.v[i][k] * B.v[k][j]这两个数都小于 10^9+7，乘积最大约 10^18，而long long的上限约 9.22×10^18，加上C.v[i][j]里已有的值也不会溢出。但这个安全性是有前提的：模数必须小于约 3×10^9。如果题目给的模数是 10^18 级别，两个数相乘就溢出了，必须换__int128或者用龟速乘。我在一次模拟赛里就遇到过模数给 10^18 的题，用 long long 直接算出负数，排查了二十分钟才反应过来。

对于追求极致速度的场景，可以把 2×2 乘法手工展开成 8 次乘法和 4 次加法，省掉循环和下标计算：

Mat mul_fast(const Mat &A, const Mat &B) { Mat C; C.v[0][0] = (A.v[0][0]*B.v[0][0] + A.v[0][1]*B.v[1][0]) % MOD; C.v[0][1] = (A.v[0][0]*B.v[0][1] + A.v[0][1]*B.v[1][1]) % MOD; C.v[1][0] = (A.v[1][0]*B.v[0][0] + A.v[1][1]*B.v[1][0]) % MOD; C.v[1][1] = (A.v[1][0]*B.v[0][1] + A.v[1][1]*B.v[1][1]) % MOD; return C; }

展开写法实测比循环版快 2 到 3 倍。对于 60 轮循环的题来说这点差距无所谓，但如果题目需要多次查询（比如一组数据里问 10^5 次斐波那契），这个差距就会放大到能不能过评测的程度。

3.2 快速幂的骨架与单位矩阵

快速幂的骨架和整数快速幂一模一样，唯一的区别是初始值不是 1 而是单位矩阵。这个点看起来简单，却是新手最常翻车的地方：res如果不初始化成单位阵，而是像Mat res;那样保持全零，那么无论怎么乘，结果永远是零矩阵，输出全是 0，而且不报错，特别容易让人怀疑是矩阵写错了。

Mat mpow(Mat base, ll e) { Mat res; res.v[0][0] = 1; res.v[1][1] = 1; // 单位矩阵，千万别漏 while (e > 0) { if (e & 1) res = mul(res, base); base = mul(base, base); e >>= 1; } return res; }

while (e > 0)的循环次数是floor(log2(e)) + 1。e = 0时不进循环，直接返回单位阵，这个行为是对的，因为任何矩阵的 0 次幂就是单位阵。所以n = 1时算M^0，返回单位阵，左上角是 1，答案正确。这个天然的正确性让我省掉了n = 1的特判，代码更干净。

关于乘法顺序，res = mul(res, base)和res = mul(base, res)在这里结果一样吗？因为res和base都是同一个矩阵 M 的幂，而同一个矩阵的不同幂之间是可交换的（M^a × M^b = M^b × M^a = M^(a+b)），所以顺序确实无所谓。但不要因为这里无所谓就形成习惯，换到其他题（比如把矩阵乘法当成一种变换去作用在向量上，或者多个不同矩阵连乘），顺序一变结果就全错。我个人的写法统一是res = mul(res, base)，从右往左对应当前已经累积的部分乘上新的因子，逻辑上更顺。

完整的求值函数就是：

ll fib(ll n) { if (n == 0) return 0; // 边界特判 Mat M; M.v[0][0] = M.v[0][1] = M.v[1][0] = 1; // M = [[1,1],[1,0]]，v[1][1] 保持 0 Mat P = mpow(M, n - 1); return P.v[0][0] % MOD; }

3.3 参数选择：模数、数据类型与初始值

模数的选择通常由题目给定，常见的几个值各有背景：10^9+7 和 10^9+9 是编程题里最普遍的质数模，10^4 或 100000 常见于“求最后几位”的填空题，1e9+7 之外还有 998244353 这种和快速数论变换相关的模数。取哪个是题目说了算，我们不能改，但要注意模数大小对溢出的影响。

数据类型方面，long long是安全选择。有人图省事用int，一旦模数超过 46340（sqrt(2^31)），两个 int 相乘就溢出，结果可能是负数，这类 bug 极难通过肉眼看出来，因为小数据不触发。我现在的习惯是：只要题目涉及乘法和取模，一律typedef long long ll，不再纠结，省下来的内存对于 2×2 矩阵也毫无意义。

初始值的确定取决于你选的起点。我一般直接用题目给的f(0) = 0, f(1) = 1，然后通过M^(n-1)求值。如果题目给的是f(1) = 1, f(2) = 1这种起点，那就等价于标准定义的偏移一位，需要把输入的n映射回去。这种映射关系在草稿纸上画一个两三行的小表就能确认，不要凭感觉写。

还有一个小细节，M.v[1][1]必须是 0。因为我用的是Mat构造函数默认清零，所以只显式赋值了三个 1，第四个留空即为 0。但如果有人换成了不带清零的数组实现，第四个位置可能是垃圾值，矩阵就全错了。这也是我推荐用带构造函数的结构体的原因之一，少一个手动初始化的地方，就少一个潜在的坑。

4. 实操验证：对拍、边界与性能实测

4.1 和小数据暴力版对拍

代码写完，最稳的验证方式是对拍。思路很简单：写一个暴力版本，用线性递推把前若干项算出来；再写主程序，用矩阵快速幂算同样的范围；两个结果逐项比较，一旦不一致立刻定位到第一个不同的下标。这个手段在调试这类“看起来很简单但总差一点”的题上极其有效。

// 暴力版：线性递推 ll fib_brute(ll n) { ll a = 0, b = 1; for (ll i = 0; i < n; ++i) { ll c = (a + b) % MOD; a = b; b = c; } return a; } int main() { for (ll n = 0; n <= 1000; ++n) { ll x = fib(n), y = fib_brute(n); if (x != y) { printf("mismatch at n=%lld: fast=%lld brute=%lld\n", n, x, y); return 0; } } puts("all ok"); return 0; }

我实测跑了一遍，从 0 到 1000 全部一致，跑完不到 10 毫秒。这一步的价值不只是确认正确，更是在后续修改代码（比如换展开写法、加快速倍增）时提供一道保险。我的习惯是：模板类代码一定要有一份对拍程序留着，以后每次改都先跑一遍，比肉眼检查可靠得多。

对拍时有个常见误区：只测了n从 1 开始的区间，漏掉了n = 0。n = 0恰恰是最容易出问题的地方，因为n-1会变成 -1。要么在函数入口特判，要么在调用前保证不传 0。上一节的fib里我写了if (n == 0) return 0;，就是为了这个。

4.2 手工核对大数与边界

小数据对拍能保证逻辑正确，但保证不了大数上的溢出和取模。针对这一点，我做了两组额外的手工核对。

第一组是无模数的中位数。用unsigned long long计算f(90)，结果是 2880067194370816120，这个数还在unsigned long long范围内（上限约 1.8×10^19），而f(93)就会溢出。我写了一个不取模的版本，把f(1)到f(92)打印出来，和已知的数列对照，结果一致，说明矩阵本身没问题。这一步排除了“矩阵写错但取模后碰巧看着对”的可能。

第二组是取模后的对照。取模运算有个性质：如果x ≡ y (mod m)，那(x + z) ≡ (y + z)。所以我用暴力版（每一步都取模）和矩阵版（也是每步取模）比对了n = 10^5到10^6的若干个点，结果一致。这一步主要验证的是取模时机，如果有人在矩阵乘法里忘了取模，就会在这一步暴露——不取模的话中间结果会迅速撑爆 long long 变成负数。

边界值我整理了这么一组，每次写完都过一遍：

n = 10^18这一行没有现成的期望答案，我的做法是找一个同样实现了矩阵快速幂、但写法完全不同的版本（比如 Python 版）交叉验证。Python 的大整数天然不溢出，用它跑一遍作为基准，再用 C++ 对比，两边一致就基本可以放心。

4.3 性能实测与优化取舍

我在本地机器上测了三组数据，n分别取 10^9、10^12、10^18，每种跑 1000 次取平均，结果如下：

单个用例微秒级，对于蓝桥杯这种一次评测十几个测试点的场景，总耗时连一毫秒都不到，完全没有性能压力。所以在这个题上，纠结展开版还是循环版意义不大，可读性优先即可。真正需要优化的是多组查询场景：如果一道题要回答 10^5 个 n 的斐波那契值，每次 60 轮循环就是 6×10^6 次矩阵乘法，耗时能到几十毫秒甚至上百毫秒，这时候展开版的优势才体现出来。

还有一种优化思路是预处理幂次：把M^(2^k)预先算好存到表里，每个查询只需要按二进制位查表相乘，平方的那部分被摊掉了。60 个 2×2 矩阵只占几 KB 内存，查询只需最多 60 次乘法而不是 120 次。这个技巧在“多次查询同一递推”的题里非常好用，我在一次模拟赛中遇到过 10^5 次查询的情况，用预处理把时间从 180ms 压到了 90ms 左右。

5. 常见问题排查速查表

5.1 答案错误类问题

这类问题最典型的表现是：样例能过，交上去 WA（Wrong Answer），或者本地小数据全对，大数据错。我在自己踩过的坑和别人问过的问题里，总结出下面几个高频原因。

第一是幂次搞错。n和n-1混用是第一名。判断方法很简单：把n = 2代进去手工算，如果代码返回的是M^2的左上角，那算出来应该是f(3) = 2，而正确答案应该是f(2) = 1，差了一项。这种错误在n小于 3 的时候最容易暴露，所以测试时一定要从n = 0开始跑。

第二是单位矩阵没有初始化。res是全零矩阵，那么res = mul(res, base)之后还是全零，无论怎么算都是 0。判断方法：输出中间结果，如果mpow返回全零矩阵，那一定是这个问题。

第三是负数取模。如果有人用了(a - b) % MOD这种写法而没有加MOD修正，可能会得到负数。虽然 C++ 里负数取模的结果是负数，但在模意义下应该修正到非负。这个坑在快速倍增写法里特别常见，写(2*b - a) % MOD的时候务必改成((2*b - a) % MOD + MOD) % MOD。

第四是模数写错。这个听起来很蠢，但确实高频。题目说模 10^9+7，你写成 10^9+9，或者把1000000007数成了10000000007（多了一个 0）。写完代码后，把常量单独抄一行对照题面读一遍，只要五秒钟。

第五是矩阵乘法展开时写错下标。手工展开 2×2 一共 8 项，很容易把A.v[0][1] * B.v[1][0]和A.v[1][0] * B.v[0][1]搞混。展开写的这四个式子，每一项都是“行 i 元素乘列 j 元素再求和”，按这个规则核对一遍就不会错。

5.2 超时与精度类问题

超时的典型原因是把矩阵按值传递。Mat里面是四个long long，按值传参要拷贝 32 字节，60 轮循环乘几十次，再加上函数调用开销，累积起来并不小。改成const Mat&引用传递后，速度能提升明显。这个问题在小规模数据上感知不到，但在多组查询的题里是致命的。

第二个超时原因是每轮循环都做一次memset。在mul内部构造Mat C时，构造函数里有一次 32 字节的清零，本来不贵，但如果有人在外层又套了一次memset，或者把数组开得很大（比如 100×100 的矩阵），这个开销就放大了。对于 2×2 这种固定小尺寸，其实可以不用memset，直接把四个元素显式赋值，更快也更清晰。

精度类问题主要出现在用浮点数辅助验证的场景。有人为了对数的大小有个直观感受，用double估算f(n)的对数：log10(f(n)) ≈ n * log10(1.618) - 0.349，这个公式在 n 很大的时候非常准，可以用来判断结果有多少位。但如果想用它来验证具体数值，一旦超过 15 位有效数字就没法看了，只能作为估算工具，不能作为正确答案的依据。

我把这些问题整理成下面这张速查表，出问题的时候按顺序扫一遍，基本能覆盖九成情况：

5.3 一些不成文的实战心得

第一，模板代码要固化下来。我现在的做法是维护一个小的代码片段文件，里面放着 2×2 矩阵结构体、mul、mpow三个东西，遇到这类题直接粘过去改模数和初始矩阵。这样做的最大好处是：这份模板是被大量题目验证过的，不需要每次重新怀疑它。新写的代码出错，原因大概率在题目特化的部分，而不是模板本身。这个思路能把调试范围砍掉一大半。

第二，别急着优化。我第一次写这题的时候，花了半小时研究怎么把矩阵乘法写成 4 次乘法（用 Strassen 或者别的技巧），最后发现完全没必要。2×2 规模下，常数优化带来的收益是微秒级，而写复杂了引入 bug 的风险是指数级。先把正确的版本写出来跑通，再考虑要不要优化，这个顺序不能反。

第三，取模的位置要统一。有人喜欢在乘法里不取模、最后统一取模，这在只有几个数的时候可行，但在 60 轮循环里，中间结果会指数级增长，早就溢出了。标准做法是：每一次乘法和加法之后立刻取模，让所有中间值始终保持在[0, MOD)区间内。这样虽然多了一些取模运算，但正确性得到了保证，而且取模本身的代价在现代 CPU 上并不高。

第四，用 Python 做交叉验证。C++ 溢出问题很难靠肉眼发现，而 Python 的整数是任意精度，写一个十行的矩阵快速幂版本，跑几个大数作为基准答案，再和 C++ 结果对比，能快速定位是不是溢出导致的。这个方法我用了很多次，比单步调试快得多。

6. 变式扩展：前 n 项和、带常数项与快速倍增

6.1 求斐波那契前 n 项和

这道每日一题的原始版本是求第 n 项，但蓝桥杯里更常见的是求前 n 项和。直接的思路是维护额外一维状态，把和也放进状态向量。状态选[f(n), f(n-1), S(n)]，其中S(n) = f(1) + f(2) + ... + f(n)。转移关系是：

f(n+1) = f(n) + f(n-1) f(n) = f(n) S(n+1) = S(n) + f(n+1) = S(n) + f(n) + f(n-1)

对应的 3×3 矩阵就是：

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

这个矩阵的第三行1 1 1表示新的和等于旧的和加新的项，而新项又等于f(n) + f(n-1)，所以是1 1 1。代码上只需要把 2×2 的模板扩成 3×3，循环改成三重，其他结构完全不变。我实测了一下，3×3 的矩阵乘法是 27 次乘法，60 轮循环也就一千多次乘法，耗时仍在微秒级，性能完全不用担心。

顺便提一个更巧的做法：斐波那契前 n 项和有闭式S(n) = f(n+2) - 1。验证一下：n = 3时，S(3) = 0+1+1+2 = 4，而f(5) - 1 = 5 - 1 = 4，对上了。用这个公式，求前 n 项和就退化成求第n+2项再减一，代码一行都不用改。不过要注意取模后的减法要加MOD修正，写成(fib(n+2) - 1 + MOD) % MOD。这个小技巧在填空题里能省不少时间，但前提是你记得住这个恒等式，记不住的话还是老老实实扩维更稳妥。

6.2 带系数、带常数项的广义递推

蓝桥杯的压轴题经常把斐波那契改造一下，变成f(n) = p * f(n-1) + q * f(n-2) + r这种形式，其中p, q, r都是题目给定的常数。这时候状态要扩成三维[f(n), f(n-1), 1]，矩阵是：

[ p q r ] [ 1 0 0 ] [ 0 0 1 ]

第一行直接抄递推式的系数，第二行1 0 0表示“旧的 f(n) 变成新的 f(n-1)”，第三行0 0 1保持不变。这个构造方法可以推广到任意阶：几阶递推，矩阵的前几行就抄系数，下面的行负责把状态往下挪位。

如果递推式里出现n的一次项，比如f(n) = f(n-1) + f(n-2) + n，那就需要把n和常数1都放进状态，变成四维[f(n), f(n-1), n, 1]。转移时n+1 = n + 1，所以矩阵里对应n的那一行是0 0 1 1，对应常数 1 的那一行是0 0 0 1。这类题的关键不是计算，而是把状态设计对，一旦状态向量选对了，矩阵就是机械地抄系数，不会出错。

我在一次模拟赛里遇到过f(n) = f(n-1) + f(n-3)这种跳项递推，当时第一反应是状态选[f(n), f(n-1), f(n-2), f(n-3)]，四维矩阵，结果发现多了一维。仔细想想，f(n-3)可以由前三项推出来吗？不能，因为递推里没用到f(n-2)，所以f(n-2)必须保留。正确的状态是[f(n), f(n-1), f(n-2)]三维，矩阵是[[1,0,1],[1,0,0],[0,1,0]]。这个例子说明：状态维数等于递推式的“记忆跨度”，不是项数减一，得具体分析。

6.3 快速倍增法：常数更小的替代方案

矩阵快速幂不是唯一解。斐波那契还有一个专门的性质可以利用：

f(2k) = f(k) * (2*f(k+1) - f(k)) f(2k+1) = f(k)^2 + f(k+1)^2

这两个式子把f(2k)和f(2k+1)都表示成了f(k)和f(k+1)的组合，从低位往高位递推，每轮只需要 3 次乘法和几次加减，比矩阵乘法的 8 次乘法少一半还多。实现上从最高位往最低位扫，维护一对(a, b) = (f(k), f(k+1))，根据当前二进制位决定下一对是(f(2k), f(2k+1))还是(f(2k+1), f(2k+2))。

pair<ll, ll> fib_pair(ll n) { // 返回 {f(n), f(n+1)} ll a = 0, b = 1; // f(0), f(1) for (int i = 62; i >= 0; --i) { ll c = a * ((2 * b % MOD - a + MOD) % MOD) % MOD; // f(2k) ll d = (a * a % MOD + b * b % MOD) % MOD; // f(2k+1) if ((n >> i) & 1LL) { a = d; b = (c + d) % MOD; } else { a = c; b = d; } } return {a, b}; }

这段代码有几个地方要小心。2 * b % MOD - a + MOD这一串，如果写成2 * b - a直接取模，可能出负数，必须先对2*b取模再加MOD修正。a * a和b * b都是接近 10^18 的量级，加起来约 2×10^18，还在long long范围内（上限 9.22×10^18），所以安全，但如果模数再大一点就要用__int128。循环从第 62 位开始，是因为long long最多 63 位，10^18的二进制长度约 60 位，从 62 开始扫能覆盖。

我用对拍程序验证了这个版本，从n = 0到n = 5000全部和矩阵版一致，其中n = 0时循环走完 63 次都取偶数分支，a保持 0、b保持 1，返回{0, 1}，正确。性能上，同样跑 10^18 规模，快速倍增版大约比展开版矩阵乘法再快 30% 到 40%。不过对于单次查询来说，这点差距可以忽略，我选哪个主要看当时手边哪个模板更顺手——如果题目就是纯斐波那契，用倍增版更短；如果题目是广义递推，那就只能老老实实写矩阵。

6.4 指数超大时的处理思路

最后一个变式值得单独说：如果题目给的n是一个上千位的十进制字符串，long long根本装不下，怎么算？思路是先把指数降下来。由于模数是质数p时，M^(p-1)在某种意义上具有周期性（严格说矩阵的幂在模意义下也有周期性，周期与模数相关），常见做法是把指数对p-1取模后再算幂。但这里有个陷阱：直接对p-1取模可能让指数变成 0，而实际指数不为 0，需要额外判断原指数是否为 0，并在为 0 时特殊处理。

如果模数不是质数，这套周期性推导就失效了，得换思路，比如直接把字符串转成一个“大整数 + 取模”的循环：

ll mod_pow_str(const string &s, ll m) { // 计算 s % m ll r = 0; for (char c : s) r = (r * 10 + (c - '0')) % m; return r; }

但我个人对这类题的态度是：先确认题目的模数和指数的关系，再决定用哪种降幂方式。盲目套费马小定理是常见的翻车点，尤其是模数给的不是质数、或者指数需要减一修正的时候。稳妥的做法是在小数据上把“降幂版”和“暴力版”对拍一遍，确认无误再提交。

这套东西我前后断断续续用了一个多月才真正理顺，中间翻过的车基本都写在上面的速查表里了。如果你也在刷蓝桥杯每日一题，建议把这三个模板（2×2 矩阵、3×3 矩阵、快速倍增）都存好，遇到新题先判断能不能套，能套就直接改模数和系数，不能套再回头重新设计状态。这样积累下来，看到“斐波那契 + 大范围 + 取模”这几个关键词，脑子里应该能立刻跳出矩阵，而不是先去开数组。