斐波那契数列这道题几乎每个打过算法竞赛的人都写过但真正在赛场上把它写对、写稳、写进时间限制里的人并不多。我在带新人刷每日一题的时候发现一个特别有意思的现象大家看到“斐波那契”四个字第一反应都是“这题我会”然后随手写个递归提交看到超时了才回头翻题解翻到“矩阵快速幂”五个字又愣住了。这篇就把斐波那契数列的矩阵快速幂求法从头到尾拆一遍从递推式怎么翻译成矩阵、指数该取 n 还是 n-1、取模为什么会炸 long long一直到赛场上真正会吃掉你罚时的几个边界条件。适合刚接触快速幂的新手也适合那些“知道大概思路但每次写都要现场推一遍”的老选手当模板库用。1. 为什么这道“每日一题”值得单独拎出来讲斐波那契这个题表面上看是把递推式换个写法实际上它是一整类问题的入口。你今天把它吃透了明天遇到“爬楼梯升级版”“统计合法字符串数量”“图上路径计数”脑子里会直接跳出“线性递推 矩阵加速”这个模板而不是从头想动态规划。这是我认为它值得单开一篇的根本原因。1.1 三种写法的失效边界在哪里先摆一个最容易被忽略的事实斐波那契的三种常见写法适用的规模是完全不同的。很多人写题的时候从来不看数据范围凭手感选写法结果就是要么写复杂了浪费时间要么写简单了直接超时。我把三种写法的失效边界整理成了下面这张表数据是我自己在本地实测的机器配置不同会有浮动但数量级是可靠的。写法时间复杂度n10^6n10^9n10^18朴素递归f(n)f(n-1)f(n-2)O(φ^n)φ≈1.618早已爆栈不可行不可行递推 / 记忆化O(n)约 10ms约 1~5s超时风险高不可行矩阵快速幂O(log n)约 1μs约 1μs约 1μs朴素递归的问题不在于它慢而在于它慢得离谱。调用次数大约是2*f(n1)-1n45 的时候 fib(45)1134903170也就是说光函数调用就有二十多亿次。我见过有人在赛场上写了个递归加个#pragma想硬扛结果连样例都没跑完就放弃了。记忆化递推或者直接滚动变量递推是 O(n) 的n 在 10^7 以内基本没问题一秒钟能跑完。但很多题目给的 n 是 10^9 甚至 10^18这时候 O(n) 就成了笑话——你就算给每秒十亿次运算的理想机器10^18 次也需要三十多年。所以看到 n 的量级到了 10^9脑子里那根弦就必须立刻绷起来这是要上快速幂了。1.2 矩阵快速幂把 O(n) 压到 O(log n) 的底层逻辑快速幂能成立靠的是两个前提缺一不可。第一个前提是结合律。矩阵乘法满足结合律也就是(A*B)*C A*(B*C)所以A^n可以任意拆分重组。如果运算不满足结合律快速幂这套东西根本无从谈起。这一点很多人写代码的时候从来没想过但它恰恰是整件事的地基。第二个前提是递推关系是线性的。斐波那契的f(n) f(n-1) f(n-2)里面两个旧值都只乘了常数系数 1没有出现f(n-1)*f(n-2)这种乘积项也没有出现n这种随位置变化的系数。只要是这种“当前项等于前面若干项的常数线性组合”的形式就一定能写成矩阵乘向量的形式。举个生活化的类比你有一个箱子里面装着最近两项的值每推进一步箱子里整体“翻新”一次。翻新这个动作是固定的、不随步骤变化的所以翻新十次等于“翻新操作”的十次方而十次方可以用二进制拆成几次平方来解决。具体到数量级n10^18 时log2(10^18) ≈ 59.8也就是说最多只需要做 60 次矩阵乘法每次 2×2 矩阵相乘是 8 次乘加。总共不到 500 次基本运算任何语言在任何评测机上都是瞬时的。这就是为什么矩阵快速幂在 n 极大的时候反而比暴力递推快得多的原因——它根本不去逐项计算而是直接跳到答案。还有一条路很多人不知道分治公式f(2k) f(k)*(2*f(k1) - f(k))和f(2k1) f(k)^2 f(k1)^2同样是 O(log n) 的。它和矩阵快速幂本质上是等价的只是写法不同。赛场上我一般还是用矩阵因为模板固定、不容易推错分治公式那两个式子记岔一个符号就全盘崩。2. 把递推式翻译成矩阵待定系数法的完整推导这一节是整篇的核心。我见过太多人矩阵是背下来的问他为什么是[[1,1],[1,0]]就答不上来。背模板在平时做题没问题但题目稍微一变——比如让你求前 n 项和或者递推式变成f(n)f(n-1)f(n-2)1——背下来的模板立刻失效。所以推导过程必须自己走一遍。2.1 从两项递推到 2×2 转移矩阵的构造我们的目标是找一个矩阵 M使得把[f(n-1), f(n-2)]这个列向量左乘 M 之后得到[f(n), f(n-1)]。如果能找到那问题就变成了对 M 反复做乘法也就是求 M 的幂。设 M 是 2×2 的元素用待定系数表示M [ a b ] [ c d ]那么[ a b ] * [ f(n-1) ] [ a*f(n-1) b*f(n-2) ] [ c d ] [ f(n-2) ] [ c*f(n-1) d*f(n-2) ]我们要求第一行等于f(n) 1*f(n-1) 1*f(n-2)第二行等于f(n-1) 1*f(n-1) 0*f(n-2)。逐项对比就能直接读出系数a1b1c1d0。所以 M [[1,1],[1,0]]。这个推导过程其实一分钟都用不到但它给了你一个通用的方法待定系数 逐项对比。以后遇到三阶递推你就设一个 3×3 矩阵九个未知数按同样的方式列方程解出来。遇到带常数项的就把向量维度加一常数项当成“永远等于 1 的那个分量”带上。把递推关系写成矩阵形式之后通项公式就出来了[ f(n) ] M^(n-1) * [ f(1) ] M^(n-1) * [ 1 ] [ f(n-1) ] [ f(0) ] [ 0 ]因为[1,0]^T乘以任何矩阵结果就是该矩阵的第一列。所以f(n)正好等于M^(n-1)的左上角元素。这是一个非常有用的简写后面写代码可以直接用。顺便说一个更漂亮的性质。如果直接算M^n会得到M^n [ f(n1) f(n) ] [ f(n) f(n-1) ]这个结论可以用数学归纳法证明也可以直接手算前几项验证。M^1 [[1,1],[1,0]]右上角是 1 f(1)M^2 [[2,1],[1,1]]右上角是 1 f(2)M^3 [[3,2],[2,1]]右上角是 2 f(3)。完全吻合。这个性质的实战价值在于算 M^n 取右上角n0 也能正确处理M^0 是单位阵右上角是 0 f(0)。而算M^(n-1)取左上角n0 的时候指数变成 -1直接出问题。这个差别在后面的边界章节还会展开讲。2.2 指数取 n 还是 n-1一个必须现场确认的错位陷阱这是我见过的最高频的错误没有之一。而且它很恶心——n 比较小的时候你验证样例是过的因为某些位置的值恰好撞上了。陷阱长这样你推导出f(n)是M^(n-1)的左上角结果写代码的时候顺手写了M^n却还是取左上角。这时候你算出来的是f(n1)整体往后错了一位。样例如果给的是n5, 答案是 5你算出来是 8一眼就能发现。但如果题目要的是模 1000000007 之后的结果或者样例恰好是个特殊值你可能根本没意识到错位。我建议的做法是写完之后固定用 n1 到 n6 手算六个值验证一遍。这几个值分别是 1, 1, 2, 3, 5, 8其中 1 出现了两次特别容易暴露错位问题——如果错位了一位n1 和 n2 的答案就会互换但由于它们恰好都是 1你反而看不出来得靠 n3 和 n4 才能区分。为了彻底避免这个问题我个人的习惯是统一用 M^n 取右上角这一种形式并且在纸上写下M^n[0][1] f(n)这个不变式。理由有三个第一n0 天然合法不需要特判第二指数就是 n不需要在代码里写n-1这种容易手滑的东西第三右上角这个位置在M^n里恰好对应 f(n)语义上是“转移 n 次得到第 n 项”直觉上更顺。如果你习惯用M^(n-1)取左上角那也没问题但一定要在代码里显式处理 n0 或者 n1 的情况别让它去算负指数。2.3 两种等价矩阵形式的取舍除了主对角线那一种构造斐波那契还有另一种常见的矩阵形式[ f(n) ] [ 1 1 ] * [ f(n-1) ] [ f(n-1) ] [ 1 0 ] [ f(n-2) ]和[ f(n1) ] [ 1 1 ] * [ f(n) ] [ f(n) ] [ 1 0 ] [ f(n-1) ]这两个其实就是同一个矩阵只是起点的脚标不同。第一种以[f(1), f(0)]为起点第二种以[f(0), f(-1)]为起点通常我们让 f(-1)1 来保证递推一致。实际写代码的时候没人会真的去处理负下标所以第一种更实用。还有一种“上下颠倒”的写法把矩阵写成[[0,1],[1,1]]这时候f(n)就落在左下角或者右下角。这种写法完全等价纯粹是个人偏好。我在比赛里判断一个选手基本功扎不扎实有个很朴素的方法看他能不能在三分钟内把矩阵快速幂的模板默写出来并且说清楚每个下标对应什么。能说清楚的人基本上不会再犯错位这种低级错误。3. 快速幂的三层拆解二进制、乘法、取模矩阵快速幂这个词拆开就是三个部分快速幂二进制拆分、矩阵乘法核心运算、取模数值控制。三个部分任何一环出问题代码就跑不对。这一节挨个拆。3.1 二进制拆分为什么能做到 log 级别快速幂的核心思想用一句话说就是a^13 a^8 * a^4 * a^1。因为 13 的二进制是 1101从低位到高位对应 1、4、8 三个权重恰好都是 2 的幂。为什么这样做能快因为a^1 → a^2 → a^4 → a^8每次只需要在上一项的基础上做一次平方a^2 a*aa^4 (a^2)^2a^8 (a^4)^2。求一个 2^k 次幂只需要 k 次平方而不是 2^k 次乘法。对于 n10^18k 大约 60六十次平方就够了相比逐次乘法的天文数字差距是指数级的。代码骨架是这样的Mat qpow(Mat base, long long n) { Mat res; // 单位矩阵 I res.a[0][0] res.a[1][1] 1; while (n 0) { if (n 1) res mul(res, base); // 当前二进制位是 1累乘 base mul(base, base); // 底数平方次次翻倍 n 1; // 右移看下一位 } return res; }这里的res为什么要初始化成单位矩阵因为矩阵乘法的“单位元”就是单位矩阵 I就像加法里的 0、乘法里的 1。如果初始化成全 0 矩阵那res mul(res, base)永远得到全 0答案直接错误。这个错我见过至少七八次都是手写模板的时候顺手memset(a, 0, sizeof(a))把整个结构体清零了。还有一个细节是base mul(base, base)必须无条件执行不能放在if里面。很多人写快速幂的时候把平方操作也塞进if(n 1)里逻辑就错了——因为无论当前位是 0 还是 1底数都要翻倍准备给下一位用。3.2 二阶矩阵乘法的循环顺序与常数优化2×2 矩阵乘法只有 8 次乘法和 4 次加法性能上其实怎么写都行。但在模板题里养成好习惯遇到 k100 甚至 k200 的大矩阵比如某些图论题的状态转移循环顺序的差别就非常明显了。最朴素的写法是 i-j-k 三层循环for (int i 0; i 2; i) for (int j 0; j 2; j) for (int k 0; k 2; k) r.a[i][j] (r.a[i][j] x.a[i][k] * y.a[k][j]) % MOD;这种写法的问题是内层循环 k 变化时y.a[k][j]的访问是跳跃的跨行缓存不友好而且每次都要读一次r.a[i][j]再做取模取模是除法指令开销不小。改良后的写法是 i-k-jfor (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) r.a[i][j] (r.a[i][j] x.a[i][k] * y.a[k][j]) % MOD; }这种顺序下y.a[k][j]的访问是连续的同一行r.a[i][j]也是连续的缓存命中率高得多。而且x.a[i][k]在内层循环里是常量编译器能把它提到寄存器里少一次内存读取。if (x.a[i][k] 0) continue这个判断在稀疏矩阵很多零元素的时候收益极大稠密矩阵也就是多一次分支预测代价可以忽略。在 k2 的情况下这些优化的收益是纳秒级的但如果是多组查询、需要做上万次矩阵乘法累积起来就能拉开差距。我个人的态度是模板代码反正写一次用一年为什么不写成最优的那一版。3.3 模数不同溢出策略就得换这是最容易被忽视、也是最容易 WA 掉的地方。C 里long long的上限是9.22*10^18。如果模数是常见的1000000007约 10^9两个小于模数的数相乘最大约10^18在long long的安全范围内直接乘没问题。这也是为什么 10^97 成为了竞赛里最受欢迎模数的原因之一——它正好卡在 long long 溢出的边界之内。但如果题目给的模数是10^18级别的呢两个数相乘最大10^36直接溢出成负数或者垃圾值。这时候有两条路第一条路是用__int128GCC 支持蓝桥杯常用的编译器应该都有。把乘法转成 128 位中间变量再取模r.a[i][j] (r.a[i][j] (__int128)x.a[i][k] * y.a[k][j]) % MOD;第二条路是“龟速乘”也就是把乘法改成加法循环用a*2 aa的方式累加每次加完立刻取模。复杂度从 O(1) 变成 O(log)但避免了溢出的问题。long long mul_mod(long long a, long long b, long long mod) { long long r 0; a % mod; while (b 0) { if (b 1) r (r a) % mod; a (a a) % mod; b 1; } return r; }还有一种情况是模数是负数或者题目要求处理负数结果。C 里负数取模结果是负的比如-5 % 3 -2而数学上我们要的是 1。处理办法是(x % MOD MOD) % MOD。在矩阵快速幂里如果初始值有负数比如某些变形题给 f(0) 一个负数初值这个处理就必须要加否则会输出奇怪的结果。我习惯在main函数把所有输入先规整到[0, MOD)区间里这样后面就一劳永逸了。最后提一句如果题目没给模数说明答案本身在unsigned long long范围内那就不取模但也意味着 n 不会特别大f(93) 就已经超过 64 位整数了。这种题目反而更简单因为不需要考虑取模溢出。4. 可直接提交的三语言实现与逐行注释模板这东西光看懂没用得能默写。下面三个版本都是我自己长期用的注释是我给新人讲解时的原话直接抄走就能用。三个版本的逻辑完全一样区别只在于语言特性。4.1 C 版本蓝桥杯赛场的主力语言#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)); } // 构造时清零防止内存里的野值 }; // 2x2 矩阵乘法i-k-j 顺序带零元素跳过 Mat mul(const Mat x, const Mat y) { Mat r; 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) r.a[i][j] (r.a[i][j] x.a[i][k] * y.a[k][j]) % MOD; } return r; } // 矩阵快速幂返回 base^n Mat qpow(Mat base, ll n) { Mat res; res.a[0][0] res.a[1][1] 1; // 单位矩阵不是全零 while (n 0) { if (n 1LL) res mul(res, base); base mul(base, base); n 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n; if (!(cin n)) return 0; Mat M; M.a[0][0] M.a[0][1] M.a[1][0] 1; // M [[1,1],[1,0]] Mat R qpow(M, n); cout R.a[0][1] % MOD \n; // M^n 的右上角就是 f(n) return 0; }几个必须说明的点。第一Mat()构造函数里一定要memset因为局部变量在栈上分配时里面的值是随机的如果不初始化mul函数里r.a[i][j]的初始累加就会带着垃圾值。第二qpow的base是值传递而不是引用传递这一点很关键——函数内部会修改base如果传引用调用方的矩阵就被改掉了。第三n 1LL里加LL后缀是为了避免在n为long long时出现意外的类型转换警告虽然不加也大概率没事但加上更保险。输入用cin n配合ios::sync_with_stdio(false)是足够的n 只有一个数不存在输入瓶颈。如果是多组数据记得每次重新构造Mat M别复用上一轮的矩阵。4.2 Java 与 Python 版本Java 版本要注意的是long和取模。Java 的long是 64 位有符号和 C 的long long一样模数 10^97 下直接乘是安全的。import java.util.Scanner; public class Main { static final long MOD 1000000007L; static long[][] mul(long[][] x, long[][] y) { long[][] r new long[2][2]; for (int i 0; i 2; i) for (int k 0; k 2; k) { if (x[i][k] 0) continue; for (int j 0; j 2; j) r[i][j] (r[i][j] x[i][k] * y[k][j]) % MOD; } return r; } static long[][] qpow(long[][] base, long n) { long[][] res new long[2][2]; res[0][0] res[1][1] 1; while (n 0) { if ((n 1) 1) res mul(res, base); base mul(base, base); n 1; } return res; } public static void main(String[] args) { Scanner sc new Scanner(System.in); long n sc.nextLong(); long[][] m {{1, 1}, {1, 0}}; long[][] r qpow(m, n); System.out.println(r[0][1] % MOD); } }Python 版本适合做对拍和验证因为写起来最快虽然常数大但对拍场景完全够用。MOD 10**9 7 def mat_mul(x, y): r [[0, 0], [0, 0]] for i in range(2): for k in range(2): if x[i][k] 0: continue for j in range(2): r[i][j] (r[i][j] x[i][k] * y[k][j]) % MOD return r def mat_pow(m, n): r [[1, 0], [0, 1]] while n: if n 1: r mat_mul(r, m) m mat_mul(m, m) n 1 return r def fib(n): return mat_pow([[1, 1], [1, 0]], n)[0][1] n int(input()) print(fib(n))Python 有个隐藏优势整数是任意精度的所以模数哪怕是 10^18 也不会溢出不需要__int128或者龟速乘。做对拍的时候如果 C 版本在大模数下 WA 了用 Python 跑一遍就能立刻判断是算法错还是溢出错。5. 赛场上真正会吃掉你罚时的六个边界模板写出来只是开始真正在赛场上丢分的往往是边界。这一节列的问题每一条我都在比赛或者帮别人调代码的时候真实遇到过。5.1 n0、n1、n2 的返回值约定题目通常会明确说“f(1)1, f(2)1”还是“f(0)0, f(1)1, f(2)1”这两种约定的下标起点不一样差了一位。更坑的是有些题目会在样例里把n0的答案标出来有些不会。用M^n取右上角这个形式天然满足f(0)0, f(1)1这套约定n0 时返回 0n1 时返回 1完全正确不需要任何特判。这就是我推荐这个形式的直接原因——少一个特判就少一处出错的可能。但如果题目要求的是f(1)1, f(2)1这套也就是 f(0) 不存在那输入 n 的时候要转成算f(n)而你的函数内部是按f(0)0定义的两者其实是一致的因为 f(1)1 在两种约定下都成立。真正需要小心的是 n 可能为 0 的情况如果题目保证 n≥1那没事如果不保证你输出 0 就是对的。还有一个容易踩的某些题目会问“第 n 项”但下标的起始是 1而你在读题时默认成了 0。这种错误跟你代码写得多好完全无关纯粹是读题不仔细。我自己的习惯是读题时立刻在草稿纸上写三个值n1 时答案?、n2 时答案?、n3 时答案?然后拿这三个值去验代码一遍就能确认下标对齐了没有。5.2 输入范围与数据类型n 的类型必须是long long不能用int。有些题目表面上看 n 不大实际上给的是 10^18 级别用int读进来直接溢出成负数然后你的快速幂里while(n 0)一次都不进返回单位矩阵答案变成I[0][1] 0。这个现象特别有迷惑性因为输出 0 看起来像是“没算出来”你会以为是矩阵构造错了实际上只是读入爆了。另外n 1这个操作在 n 是负数的时候行为是实现定义的虽然主流编译器都是算术右移所以一旦 n 被读成负数整个循环可能死循环。保险起见可以在读入后加一句断言if (n 0) return 0;虽然正常题目不会给负数但调试的时候能帮你快速定位问题。还有一个隐蔽的坑某些题目会给出多组测试数据第一行是 T然后每行一个 n。这时候如果忘记重置res矩阵在qpow内部它是局部变量每次调用都会重新构造所以其实是安全的但如果你把res提到全局就没有这个保障了。我见过有人为了“优化”把矩阵声明成全局的然后多组数据之间没清空第二组开始全错。5.3 多组查询与预处理如果题目要给 10^5 组查询每组一个 n你要算 10^5 次矩阵快速幂每次约 60 次矩阵乘法总共 600 万次乘法C 大概几十毫秒能过。但如果模数大需要用龟速乘常数翻 60 倍就悬了。这种时候可以预处理。做法是把指数按位拆开预先算出M^(2^0),M^(2^1), ...,M^(2^59)这 60 个矩阵存起来然后每组查询只需要按 n 的二进制位把这些预存的矩阵乘起来最多 60 次乘法而不是 60 次“平方 乘法”。节省的量大概是两倍左右而且写法上没啥额外复杂度。另一种情况是查询的 n 是单调递增的。这种时候可以直接维护一个“当前矩阵”每次往前多乘几次总体复杂度是 O(max_n) 次矩阵乘法但要注意 max_n 可能很大只在 max_n 到 10^7 这个量级才划算再大还是得用快速幂。我的建议是先写最朴素的快速幂提交一次看看时间。如果 TLE 了再回来优化别一上来就写复杂的预处理容易在比赛里浪费时间还引入 bug。5.4 几个我真实踩过的坑第一个坑用通项公式算然后四舍五入。f(n) ((1√5)/2)^n / √5理论上是对的但double只有 53 位有效数字n 到 70 左右精度就崩了算出 12.9999999 然后round得到 13实际答案可能是 14。除非题目 n70否则这条路走不通。有的题解会说用高精度浮点但那还不如直接矩阵快速幂。第二个坑把memset用错了位置。memset(a, 0, sizeof(a))里a是数组名sizeof(a)是数组总字节数这是对的。但如果a是指针比如函数参数传进来的int* asizeof(a)就变成了指针大小8 字节只清了一小半剩下的全是垃圾。这个坑在结构体数组传参的时候特别容易踩。第三个坑结果没取模或者取模位置不对。有些人在最后输出的时候才取一次模中间全用原始值累加n 稍微大一点就溢出了。正确做法是每次乘加之后立刻取模虽然多几次除法运算但正确性有保障。第四个坑用int存矩阵元素。模数是 10^97 的时候两个int相乘直接溢出成负数你甚至不会收到任何警告。矩阵元素一律用long long这是底线。6. 从斐波那契往外扩线性递推的通用解法斐波那契只是最小的一种线性递推。真正有价值的是把这个方法推广出去遇到陌生的递推式也能自己构造矩阵。6.1 三阶递推与带常数项的构造假设题目给的是f(n) f(n-1) f(n-2) f(n-3)初始值 f(1)f(2)1, f(3)2。这时候状态向量要从两项扩成三项[f(n), f(n-1), f(n-2)]转移矩阵是 3×3[ f(n) ] [ 1 1 1 ] [ f(n-1) ] [ f(n-1) ] [ 1 0 0 ] * [ f(n-2) ] [ f(n-2) ] [ 0 1 0 ] [ f(n-3) ]对角线上面那行是递推系数下面是一个“移位矩阵”把旧值往下挪一格。这个模式是通用的k 阶递推就用 k×k 矩阵第一行是系数下面形成一个下移的单位阵。如果递推式里带个常数比如f(n) f(n-1) f(n-2) 1处理办法是把状态向量再扩一维最后放一个永远等于 1 的分量[ f(n) ] [ 1 1 1 ] [ f(n-1) ] [ f(n-1) ] [ 1 0 0 ] * [ f(n-2) ] [ 1 ] [ 0 0 1 ] [ 1 ]注意矩阵最后一列是[1, 0, 1]^T因为常数项 1 要和第一行的系数 1 相乘贡献给 f(n)而在第三行要“自我复制”保持为 1。如果题目要的是前 n 项和S(n) S(n-1) f(n)那就再加一维把 S 也放进状态向量里转移矩阵里 S 那一行写成[1, 1, 1, 0]之类的形式。这类变形在各种竞赛题里出现频率极高但套路是完全一样的认准“几阶递推 几个额外状态”就能直接构造出来。有一个判断标准很好用状态向量的维度 递推涉及的项数 常数项个数 求和项个数。维度确定后矩阵的行列数就确定了剩下的只是填系数的机械工作。6.2 一个对拍脚本验证你的模板模板写完一定要对拍这是我最强调的一条经验。人眼看代码看不出错位但随机数据对拍一秒就能暴露。思路很简单写一个暴力版本O(n) 递推再写一个矩阵版本随机生成小范围的 n比较两者输出是否一致。Python 版本最方便import random MOD 10**9 7 def fib_naive(n): if n 0: return 0 a, b 0, 1 for _ in range(n): a, b b, (a b) % MOD return a def mat_mul(x, y): r [[0, 0], [0, 0]] for i in range(2): for k in range(2): if x[i][k] 0: continue for j in range(2): r[i][j] (r[i][j] x[i][k] * y[k][j]) % MOD return r def fib_fast(n): m [[1, 1], [1, 0]] r [[1, 0], [0, 1]] while n: if n 1: r mat_mul(r, m) m mat_mul(m, m) n 1 return r[0][1] for _ in range(2000): n random.randint(0, 300) if fib_naive(n) ! fib_fast(n): print(MISMATCH at n , n) print(naive:, fib_naive(n), fast:, fib_fast(n)) break else: print(all passed)这个脚本跑 2000 组随机数据覆盖 n 从 0 到 300 的范围如果模板有错位、有初始化问题、有溢出问题基本上第一轮就会挂。特别要注意的是它把 n0 也纳入了随机范围因为随机函数的下界是 0这恰好能测出M^n和M^(n-1)两种写法在边界上的差异。如果针对大模数的题目改一下MOD就能测出溢出问题。Python 不会溢出所以如果 Python 过了而 C 挂了那就是 C 的溢出没处理好这个判断非常干脆。我自己还习惯在本地生成一份“暴力答案表”把 n0 到 n100 的答案全部打出来贴在代码旁边改完代码之后肉眼扫一遍前十个基本就能确认没问题。这招看起来笨但在没有时间写对拍脚本的赛场上反而是最高效的自检手段。毕竟蓝桥杯的题型里填空和编程题的提交次数有限多花两分钟检查比提交上去等罚时要划算得多。
斐波那契数列这道题几乎每个打过算法竞赛的人都写过但真正在赛场上把它写对、写稳、写进时间限制里的人并不多。我在带新人刷每日一题的时候发现一个特别有意思的现象大家看到“斐波那契”四个字第一反应都是“这题我会”然后随手写个递归提交看到超时了才回头翻题解翻到“矩阵快速幂”五个字又愣住了。这篇就把斐波那契数列的矩阵快速幂求法从头到尾拆一遍从递推式怎么翻译成矩阵、指数该取 n 还是 n-1、取模为什么会炸 long long一直到赛场上真正会吃掉你罚时的几个边界条件。适合刚接触快速幂的新手也适合那些“知道大概思路但每次写都要现场推一遍”的老选手当模板库用。1. 为什么这道“每日一题”值得单独拎出来讲斐波那契这个题表面上看是把递推式换个写法实际上它是一整类问题的入口。你今天把它吃透了明天遇到“爬楼梯升级版”“统计合法字符串数量”“图上路径计数”脑子里会直接跳出“线性递推 矩阵加速”这个模板而不是从头想动态规划。这是我认为它值得单开一篇的根本原因。1.1 三种写法的失效边界在哪里先摆一个最容易被忽略的事实斐波那契的三种常见写法适用的规模是完全不同的。很多人写题的时候从来不看数据范围凭手感选写法结果就是要么写复杂了浪费时间要么写简单了直接超时。我把三种写法的失效边界整理成了下面这张表数据是我自己在本地实测的机器配置不同会有浮动但数量级是可靠的。写法时间复杂度n10^6n10^9n10^18朴素递归f(n)f(n-1)f(n-2)O(φ^n)φ≈1.618早已爆栈不可行不可行递推 / 记忆化O(n)约 10ms约 1~5s超时风险高不可行矩阵快速幂O(log n)约 1μs约 1μs约 1μs朴素递归的问题不在于它慢而在于它慢得离谱。调用次数大约是2*f(n1)-1n45 的时候 fib(45)1134903170也就是说光函数调用就有二十多亿次。我见过有人在赛场上写了个递归加个#pragma想硬扛结果连样例都没跑完就放弃了。记忆化递推或者直接滚动变量递推是 O(n) 的n 在 10^7 以内基本没问题一秒钟能跑完。但很多题目给的 n 是 10^9 甚至 10^18这时候 O(n) 就成了笑话——你就算给每秒十亿次运算的理想机器10^18 次也需要三十多年。所以看到 n 的量级到了 10^9脑子里那根弦就必须立刻绷起来这是要上快速幂了。1.2 矩阵快速幂把 O(n) 压到 O(log n) 的底层逻辑快速幂能成立靠的是两个前提缺一不可。第一个前提是结合律。矩阵乘法满足结合律也就是(A*B)*C A*(B*C)所以A^n可以任意拆分重组。如果运算不满足结合律快速幂这套东西根本无从谈起。这一点很多人写代码的时候从来没想过但它恰恰是整件事的地基。第二个前提是递推关系是线性的。斐波那契的f(n) f(n-1) f(n-2)里面两个旧值都只乘了常数系数 1没有出现f(n-1)*f(n-2)这种乘积项也没有出现n这种随位置变化的系数。只要是这种“当前项等于前面若干项的常数线性组合”的形式就一定能写成矩阵乘向量的形式。举个生活化的类比你有一个箱子里面装着最近两项的值每推进一步箱子里整体“翻新”一次。翻新这个动作是固定的、不随步骤变化的所以翻新十次等于“翻新操作”的十次方而十次方可以用二进制拆成几次平方来解决。具体到数量级n10^18 时log2(10^18) ≈ 59.8也就是说最多只需要做 60 次矩阵乘法每次 2×2 矩阵相乘是 8 次乘加。总共不到 500 次基本运算任何语言在任何评测机上都是瞬时的。这就是为什么矩阵快速幂在 n 极大的时候反而比暴力递推快得多的原因——它根本不去逐项计算而是直接跳到答案。还有一条路很多人不知道分治公式f(2k) f(k)*(2*f(k1) - f(k))和f(2k1) f(k)^2 f(k1)^2同样是 O(log n) 的。它和矩阵快速幂本质上是等价的只是写法不同。赛场上我一般还是用矩阵因为模板固定、不容易推错分治公式那两个式子记岔一个符号就全盘崩。2. 把递推式翻译成矩阵待定系数法的完整推导这一节是整篇的核心。我见过太多人矩阵是背下来的问他为什么是[[1,1],[1,0]]就答不上来。背模板在平时做题没问题但题目稍微一变——比如让你求前 n 项和或者递推式变成f(n)f(n-1)f(n-2)1——背下来的模板立刻失效。所以推导过程必须自己走一遍。2.1 从两项递推到 2×2 转移矩阵的构造我们的目标是找一个矩阵 M使得把[f(n-1), f(n-2)]这个列向量左乘 M 之后得到[f(n), f(n-1)]。如果能找到那问题就变成了对 M 反复做乘法也就是求 M 的幂。设 M 是 2×2 的元素用待定系数表示M [ a b ] [ c d ]那么[ a b ] * [ f(n-1) ] [ a*f(n-1) b*f(n-2) ] [ c d ] [ f(n-2) ] [ c*f(n-1) d*f(n-2) ]我们要求第一行等于f(n) 1*f(n-1) 1*f(n-2)第二行等于f(n-1) 1*f(n-1) 0*f(n-2)。逐项对比就能直接读出系数a1b1c1d0。所以 M [[1,1],[1,0]]。这个推导过程其实一分钟都用不到但它给了你一个通用的方法待定系数 逐项对比。以后遇到三阶递推你就设一个 3×3 矩阵九个未知数按同样的方式列方程解出来。遇到带常数项的就把向量维度加一常数项当成“永远等于 1 的那个分量”带上。把递推关系写成矩阵形式之后通项公式就出来了[ f(n) ] M^(n-1) * [ f(1) ] M^(n-1) * [ 1 ] [ f(n-1) ] [ f(0) ] [ 0 ]因为[1,0]^T乘以任何矩阵结果就是该矩阵的第一列。所以f(n)正好等于M^(n-1)的左上角元素。这是一个非常有用的简写后面写代码可以直接用。顺便说一个更漂亮的性质。如果直接算M^n会得到M^n [ f(n1) f(n) ] [ f(n) f(n-1) ]这个结论可以用数学归纳法证明也可以直接手算前几项验证。M^1 [[1,1],[1,0]]右上角是 1 f(1)M^2 [[2,1],[1,1]]右上角是 1 f(2)M^3 [[3,2],[2,1]]右上角是 2 f(3)。完全吻合。这个性质的实战价值在于算 M^n 取右上角n0 也能正确处理M^0 是单位阵右上角是 0 f(0)。而算M^(n-1)取左上角n0 的时候指数变成 -1直接出问题。这个差别在后面的边界章节还会展开讲。2.2 指数取 n 还是 n-1一个必须现场确认的错位陷阱这是我见过的最高频的错误没有之一。而且它很恶心——n 比较小的时候你验证样例是过的因为某些位置的值恰好撞上了。陷阱长这样你推导出f(n)是M^(n-1)的左上角结果写代码的时候顺手写了M^n却还是取左上角。这时候你算出来的是f(n1)整体往后错了一位。样例如果给的是n5, 答案是 5你算出来是 8一眼就能发现。但如果题目要的是模 1000000007 之后的结果或者样例恰好是个特殊值你可能根本没意识到错位。我建议的做法是写完之后固定用 n1 到 n6 手算六个值验证一遍。这几个值分别是 1, 1, 2, 3, 5, 8其中 1 出现了两次特别容易暴露错位问题——如果错位了一位n1 和 n2 的答案就会互换但由于它们恰好都是 1你反而看不出来得靠 n3 和 n4 才能区分。为了彻底避免这个问题我个人的习惯是统一用 M^n 取右上角这一种形式并且在纸上写下M^n[0][1] f(n)这个不变式。理由有三个第一n0 天然合法不需要特判第二指数就是 n不需要在代码里写n-1这种容易手滑的东西第三右上角这个位置在M^n里恰好对应 f(n)语义上是“转移 n 次得到第 n 项”直觉上更顺。如果你习惯用M^(n-1)取左上角那也没问题但一定要在代码里显式处理 n0 或者 n1 的情况别让它去算负指数。2.3 两种等价矩阵形式的取舍除了主对角线那一种构造斐波那契还有另一种常见的矩阵形式[ f(n) ] [ 1 1 ] * [ f(n-1) ] [ f(n-1) ] [ 1 0 ] [ f(n-2) ]和[ f(n1) ] [ 1 1 ] * [ f(n) ] [ f(n) ] [ 1 0 ] [ f(n-1) ]这两个其实就是同一个矩阵只是起点的脚标不同。第一种以[f(1), f(0)]为起点第二种以[f(0), f(-1)]为起点通常我们让 f(-1)1 来保证递推一致。实际写代码的时候没人会真的去处理负下标所以第一种更实用。还有一种“上下颠倒”的写法把矩阵写成[[0,1],[1,1]]这时候f(n)就落在左下角或者右下角。这种写法完全等价纯粹是个人偏好。我在比赛里判断一个选手基本功扎不扎实有个很朴素的方法看他能不能在三分钟内把矩阵快速幂的模板默写出来并且说清楚每个下标对应什么。能说清楚的人基本上不会再犯错位这种低级错误。3. 快速幂的三层拆解二进制、乘法、取模矩阵快速幂这个词拆开就是三个部分快速幂二进制拆分、矩阵乘法核心运算、取模数值控制。三个部分任何一环出问题代码就跑不对。这一节挨个拆。3.1 二进制拆分为什么能做到 log 级别快速幂的核心思想用一句话说就是a^13 a^8 * a^4 * a^1。因为 13 的二进制是 1101从低位到高位对应 1、4、8 三个权重恰好都是 2 的幂。为什么这样做能快因为a^1 → a^2 → a^4 → a^8每次只需要在上一项的基础上做一次平方a^2 a*aa^4 (a^2)^2a^8 (a^4)^2。求一个 2^k 次幂只需要 k 次平方而不是 2^k 次乘法。对于 n10^18k 大约 60六十次平方就够了相比逐次乘法的天文数字差距是指数级的。代码骨架是这样的Mat qpow(Mat base, long long n) { Mat res; // 单位矩阵 I res.a[0][0] res.a[1][1] 1; while (n 0) { if (n 1) res mul(res, base); // 当前二进制位是 1累乘 base mul(base, base); // 底数平方次次翻倍 n 1; // 右移看下一位 } return res; }这里的res为什么要初始化成单位矩阵因为矩阵乘法的“单位元”就是单位矩阵 I就像加法里的 0、乘法里的 1。如果初始化成全 0 矩阵那res mul(res, base)永远得到全 0答案直接错误。这个错我见过至少七八次都是手写模板的时候顺手memset(a, 0, sizeof(a))把整个结构体清零了。还有一个细节是base mul(base, base)必须无条件执行不能放在if里面。很多人写快速幂的时候把平方操作也塞进if(n 1)里逻辑就错了——因为无论当前位是 0 还是 1底数都要翻倍准备给下一位用。3.2 二阶矩阵乘法的循环顺序与常数优化2×2 矩阵乘法只有 8 次乘法和 4 次加法性能上其实怎么写都行。但在模板题里养成好习惯遇到 k100 甚至 k200 的大矩阵比如某些图论题的状态转移循环顺序的差别就非常明显了。最朴素的写法是 i-j-k 三层循环for (int i 0; i 2; i) for (int j 0; j 2; j) for (int k 0; k 2; k) r.a[i][j] (r.a[i][j] x.a[i][k] * y.a[k][j]) % MOD;这种写法的问题是内层循环 k 变化时y.a[k][j]的访问是跳跃的跨行缓存不友好而且每次都要读一次r.a[i][j]再做取模取模是除法指令开销不小。改良后的写法是 i-k-jfor (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) r.a[i][j] (r.a[i][j] x.a[i][k] * y.a[k][j]) % MOD; }这种顺序下y.a[k][j]的访问是连续的同一行r.a[i][j]也是连续的缓存命中率高得多。而且x.a[i][k]在内层循环里是常量编译器能把它提到寄存器里少一次内存读取。if (x.a[i][k] 0) continue这个判断在稀疏矩阵很多零元素的时候收益极大稠密矩阵也就是多一次分支预测代价可以忽略。在 k2 的情况下这些优化的收益是纳秒级的但如果是多组查询、需要做上万次矩阵乘法累积起来就能拉开差距。我个人的态度是模板代码反正写一次用一年为什么不写成最优的那一版。3.3 模数不同溢出策略就得换这是最容易被忽视、也是最容易 WA 掉的地方。C 里long long的上限是9.22*10^18。如果模数是常见的1000000007约 10^9两个小于模数的数相乘最大约10^18在long long的安全范围内直接乘没问题。这也是为什么 10^97 成为了竞赛里最受欢迎模数的原因之一——它正好卡在 long long 溢出的边界之内。但如果题目给的模数是10^18级别的呢两个数相乘最大10^36直接溢出成负数或者垃圾值。这时候有两条路第一条路是用__int128GCC 支持蓝桥杯常用的编译器应该都有。把乘法转成 128 位中间变量再取模r.a[i][j] (r.a[i][j] (__int128)x.a[i][k] * y.a[k][j]) % MOD;第二条路是“龟速乘”也就是把乘法改成加法循环用a*2 aa的方式累加每次加完立刻取模。复杂度从 O(1) 变成 O(log)但避免了溢出的问题。long long mul_mod(long long a, long long b, long long mod) { long long r 0; a % mod; while (b 0) { if (b 1) r (r a) % mod; a (a a) % mod; b 1; } return r; }还有一种情况是模数是负数或者题目要求处理负数结果。C 里负数取模结果是负的比如-5 % 3 -2而数学上我们要的是 1。处理办法是(x % MOD MOD) % MOD。在矩阵快速幂里如果初始值有负数比如某些变形题给 f(0) 一个负数初值这个处理就必须要加否则会输出奇怪的结果。我习惯在main函数把所有输入先规整到[0, MOD)区间里这样后面就一劳永逸了。最后提一句如果题目没给模数说明答案本身在unsigned long long范围内那就不取模但也意味着 n 不会特别大f(93) 就已经超过 64 位整数了。这种题目反而更简单因为不需要考虑取模溢出。4. 可直接提交的三语言实现与逐行注释模板这东西光看懂没用得能默写。下面三个版本都是我自己长期用的注释是我给新人讲解时的原话直接抄走就能用。三个版本的逻辑完全一样区别只在于语言特性。4.1 C 版本蓝桥杯赛场的主力语言#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)); } // 构造时清零防止内存里的野值 }; // 2x2 矩阵乘法i-k-j 顺序带零元素跳过 Mat mul(const Mat x, const Mat y) { Mat r; 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) r.a[i][j] (r.a[i][j] x.a[i][k] * y.a[k][j]) % MOD; } return r; } // 矩阵快速幂返回 base^n Mat qpow(Mat base, ll n) { Mat res; res.a[0][0] res.a[1][1] 1; // 单位矩阵不是全零 while (n 0) { if (n 1LL) res mul(res, base); base mul(base, base); n 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n; if (!(cin n)) return 0; Mat M; M.a[0][0] M.a[0][1] M.a[1][0] 1; // M [[1,1],[1,0]] Mat R qpow(M, n); cout R.a[0][1] % MOD \n; // M^n 的右上角就是 f(n) return 0; }几个必须说明的点。第一Mat()构造函数里一定要memset因为局部变量在栈上分配时里面的值是随机的如果不初始化mul函数里r.a[i][j]的初始累加就会带着垃圾值。第二qpow的base是值传递而不是引用传递这一点很关键——函数内部会修改base如果传引用调用方的矩阵就被改掉了。第三n 1LL里加LL后缀是为了避免在n为long long时出现意外的类型转换警告虽然不加也大概率没事但加上更保险。输入用cin n配合ios::sync_with_stdio(false)是足够的n 只有一个数不存在输入瓶颈。如果是多组数据记得每次重新构造Mat M别复用上一轮的矩阵。4.2 Java 与 Python 版本Java 版本要注意的是long和取模。Java 的long是 64 位有符号和 C 的long long一样模数 10^97 下直接乘是安全的。import java.util.Scanner; public class Main { static final long MOD 1000000007L; static long[][] mul(long[][] x, long[][] y) { long[][] r new long[2][2]; for (int i 0; i 2; i) for (int k 0; k 2; k) { if (x[i][k] 0) continue; for (int j 0; j 2; j) r[i][j] (r[i][j] x[i][k] * y[k][j]) % MOD; } return r; } static long[][] qpow(long[][] base, long n) { long[][] res new long[2][2]; res[0][0] res[1][1] 1; while (n 0) { if ((n 1) 1) res mul(res, base); base mul(base, base); n 1; } return res; } public static void main(String[] args) { Scanner sc new Scanner(System.in); long n sc.nextLong(); long[][] m {{1, 1}, {1, 0}}; long[][] r qpow(m, n); System.out.println(r[0][1] % MOD); } }Python 版本适合做对拍和验证因为写起来最快虽然常数大但对拍场景完全够用。MOD 10**9 7 def mat_mul(x, y): r [[0, 0], [0, 0]] for i in range(2): for k in range(2): if x[i][k] 0: continue for j in range(2): r[i][j] (r[i][j] x[i][k] * y[k][j]) % MOD return r def mat_pow(m, n): r [[1, 0], [0, 1]] while n: if n 1: r mat_mul(r, m) m mat_mul(m, m) n 1 return r def fib(n): return mat_pow([[1, 1], [1, 0]], n)[0][1] n int(input()) print(fib(n))Python 有个隐藏优势整数是任意精度的所以模数哪怕是 10^18 也不会溢出不需要__int128或者龟速乘。做对拍的时候如果 C 版本在大模数下 WA 了用 Python 跑一遍就能立刻判断是算法错还是溢出错。5. 赛场上真正会吃掉你罚时的六个边界模板写出来只是开始真正在赛场上丢分的往往是边界。这一节列的问题每一条我都在比赛或者帮别人调代码的时候真实遇到过。5.1 n0、n1、n2 的返回值约定题目通常会明确说“f(1)1, f(2)1”还是“f(0)0, f(1)1, f(2)1”这两种约定的下标起点不一样差了一位。更坑的是有些题目会在样例里把n0的答案标出来有些不会。用M^n取右上角这个形式天然满足f(0)0, f(1)1这套约定n0 时返回 0n1 时返回 1完全正确不需要任何特判。这就是我推荐这个形式的直接原因——少一个特判就少一处出错的可能。但如果题目要求的是f(1)1, f(2)1这套也就是 f(0) 不存在那输入 n 的时候要转成算f(n)而你的函数内部是按f(0)0定义的两者其实是一致的因为 f(1)1 在两种约定下都成立。真正需要小心的是 n 可能为 0 的情况如果题目保证 n≥1那没事如果不保证你输出 0 就是对的。还有一个容易踩的某些题目会问“第 n 项”但下标的起始是 1而你在读题时默认成了 0。这种错误跟你代码写得多好完全无关纯粹是读题不仔细。我自己的习惯是读题时立刻在草稿纸上写三个值n1 时答案?、n2 时答案?、n3 时答案?然后拿这三个值去验代码一遍就能确认下标对齐了没有。5.2 输入范围与数据类型n 的类型必须是long long不能用int。有些题目表面上看 n 不大实际上给的是 10^18 级别用int读进来直接溢出成负数然后你的快速幂里while(n 0)一次都不进返回单位矩阵答案变成I[0][1] 0。这个现象特别有迷惑性因为输出 0 看起来像是“没算出来”你会以为是矩阵构造错了实际上只是读入爆了。另外n 1这个操作在 n 是负数的时候行为是实现定义的虽然主流编译器都是算术右移所以一旦 n 被读成负数整个循环可能死循环。保险起见可以在读入后加一句断言if (n 0) return 0;虽然正常题目不会给负数但调试的时候能帮你快速定位问题。还有一个隐蔽的坑某些题目会给出多组测试数据第一行是 T然后每行一个 n。这时候如果忘记重置res矩阵在qpow内部它是局部变量每次调用都会重新构造所以其实是安全的但如果你把res提到全局就没有这个保障了。我见过有人为了“优化”把矩阵声明成全局的然后多组数据之间没清空第二组开始全错。5.3 多组查询与预处理如果题目要给 10^5 组查询每组一个 n你要算 10^5 次矩阵快速幂每次约 60 次矩阵乘法总共 600 万次乘法C 大概几十毫秒能过。但如果模数大需要用龟速乘常数翻 60 倍就悬了。这种时候可以预处理。做法是把指数按位拆开预先算出M^(2^0),M^(2^1), ...,M^(2^59)这 60 个矩阵存起来然后每组查询只需要按 n 的二进制位把这些预存的矩阵乘起来最多 60 次乘法而不是 60 次“平方 乘法”。节省的量大概是两倍左右而且写法上没啥额外复杂度。另一种情况是查询的 n 是单调递增的。这种时候可以直接维护一个“当前矩阵”每次往前多乘几次总体复杂度是 O(max_n) 次矩阵乘法但要注意 max_n 可能很大只在 max_n 到 10^7 这个量级才划算再大还是得用快速幂。我的建议是先写最朴素的快速幂提交一次看看时间。如果 TLE 了再回来优化别一上来就写复杂的预处理容易在比赛里浪费时间还引入 bug。5.4 几个我真实踩过的坑第一个坑用通项公式算然后四舍五入。f(n) ((1√5)/2)^n / √5理论上是对的但double只有 53 位有效数字n 到 70 左右精度就崩了算出 12.9999999 然后round得到 13实际答案可能是 14。除非题目 n70否则这条路走不通。有的题解会说用高精度浮点但那还不如直接矩阵快速幂。第二个坑把memset用错了位置。memset(a, 0, sizeof(a))里a是数组名sizeof(a)是数组总字节数这是对的。但如果a是指针比如函数参数传进来的int* asizeof(a)就变成了指针大小8 字节只清了一小半剩下的全是垃圾。这个坑在结构体数组传参的时候特别容易踩。第三个坑结果没取模或者取模位置不对。有些人在最后输出的时候才取一次模中间全用原始值累加n 稍微大一点就溢出了。正确做法是每次乘加之后立刻取模虽然多几次除法运算但正确性有保障。第四个坑用int存矩阵元素。模数是 10^97 的时候两个int相乘直接溢出成负数你甚至不会收到任何警告。矩阵元素一律用long long这是底线。6. 从斐波那契往外扩线性递推的通用解法斐波那契只是最小的一种线性递推。真正有价值的是把这个方法推广出去遇到陌生的递推式也能自己构造矩阵。6.1 三阶递推与带常数项的构造假设题目给的是f(n) f(n-1) f(n-2) f(n-3)初始值 f(1)f(2)1, f(3)2。这时候状态向量要从两项扩成三项[f(n), f(n-1), f(n-2)]转移矩阵是 3×3[ f(n) ] [ 1 1 1 ] [ f(n-1) ] [ f(n-1) ] [ 1 0 0 ] * [ f(n-2) ] [ f(n-2) ] [ 0 1 0 ] [ f(n-3) ]对角线上面那行是递推系数下面是一个“移位矩阵”把旧值往下挪一格。这个模式是通用的k 阶递推就用 k×k 矩阵第一行是系数下面形成一个下移的单位阵。如果递推式里带个常数比如f(n) f(n-1) f(n-2) 1处理办法是把状态向量再扩一维最后放一个永远等于 1 的分量[ f(n) ] [ 1 1 1 ] [ f(n-1) ] [ f(n-1) ] [ 1 0 0 ] * [ f(n-2) ] [ 1 ] [ 0 0 1 ] [ 1 ]注意矩阵最后一列是[1, 0, 1]^T因为常数项 1 要和第一行的系数 1 相乘贡献给 f(n)而在第三行要“自我复制”保持为 1。如果题目要的是前 n 项和S(n) S(n-1) f(n)那就再加一维把 S 也放进状态向量里转移矩阵里 S 那一行写成[1, 1, 1, 0]之类的形式。这类变形在各种竞赛题里出现频率极高但套路是完全一样的认准“几阶递推 几个额外状态”就能直接构造出来。有一个判断标准很好用状态向量的维度 递推涉及的项数 常数项个数 求和项个数。维度确定后矩阵的行列数就确定了剩下的只是填系数的机械工作。6.2 一个对拍脚本验证你的模板模板写完一定要对拍这是我最强调的一条经验。人眼看代码看不出错位但随机数据对拍一秒就能暴露。思路很简单写一个暴力版本O(n) 递推再写一个矩阵版本随机生成小范围的 n比较两者输出是否一致。Python 版本最方便import random MOD 10**9 7 def fib_naive(n): if n 0: return 0 a, b 0, 1 for _ in range(n): a, b b, (a b) % MOD return a def mat_mul(x, y): r [[0, 0], [0, 0]] for i in range(2): for k in range(2): if x[i][k] 0: continue for j in range(2): r[i][j] (r[i][j] x[i][k] * y[k][j]) % MOD return r def fib_fast(n): m [[1, 1], [1, 0]] r [[1, 0], [0, 1]] while n: if n 1: r mat_mul(r, m) m mat_mul(m, m) n 1 return r[0][1] for _ in range(2000): n random.randint(0, 300) if fib_naive(n) ! fib_fast(n): print(MISMATCH at n , n) print(naive:, fib_naive(n), fast:, fib_fast(n)) break else: print(all passed)这个脚本跑 2000 组随机数据覆盖 n 从 0 到 300 的范围如果模板有错位、有初始化问题、有溢出问题基本上第一轮就会挂。特别要注意的是它把 n0 也纳入了随机范围因为随机函数的下界是 0这恰好能测出M^n和M^(n-1)两种写法在边界上的差异。如果针对大模数的题目改一下MOD就能测出溢出问题。Python 不会溢出所以如果 Python 过了而 C 挂了那就是 C 的溢出没处理好这个判断非常干脆。我自己还习惯在本地生成一份“暴力答案表”把 n0 到 n100 的答案全部打出来贴在代码旁边改完代码之后肉眼扫一遍前十个基本就能确认没问题。这招看起来笨但在没有时间写对拍脚本的赛场上反而是最高效的自检手段。毕竟蓝桥杯的题型里填空和编程题的提交次数有限多花两分钟检查比提交上去等罚时要划算得多。
