看到今天的每日一题标题是“波斐契那数列”我第一反应是这题名从哪儿翻译来的错别字。等点进去把题面读完才发现它定义的递推关系是F(n) F(n-1) F(n-2)初始项F(0) F(1) 1。这其实就是经典的斐波那契数列只是命名上拐了个弯。我没有简单地把这道题当一次普通打卡就完事。当晚在 tracker 里做复盘时我顺手把从暴力递归到矩阵快速幂的几种解法全部写了一遍还对照了运行时间和内存占用整理出这篇记录。适合想搞懂递推数列大数场景优化的人也适合刚接触矩阵快速幂、想找个具体题目入手的初学者。下面我会把题目还原、三种解法的取舍、五个容易让人交白卷的坑以及我自己的打卡复盘过程一次讲清楚。1. 题目还原波斐契那数列到底在考什么1.1 从名字到手写递推式的距离这道题表面叫“波斐契那数列”但打开题目附带的定义你会发现它根本不是乱七八糟的新物种F(0) 1F(1) 1当n 2时F(n) F(n-1) F(n-2)把前几项写出来就是1, 1, 2, 3, 5, 8, 13, 21 ...。这跟常见的教科书版斐波那契F(0)0, F(1)1在初始项上有差别但递推规律一模一样。也就是说“波斐契那数列”本质上是斐波那契数列的一个变体把初始条件换了换。题目起这个名字与其说是在考数学知识不如说是在考“你是否能不被名字骗到老老实实读题面定义”。在刷题场景里这种“套了陌生名字的老套路”非常常见。遇到任何不熟悉的数列名正确的第一反应不是去网上搜这个数列的公式而是直接看题目给出的递推式、初始值和询问内容。题目说什么你就按什么写代码不要带入先验知识。1.2 隐藏的边界条件与输入约束这道题真正决定用什么解法的不是递推式本身而是数据范围。我当时在 tracker 里记下了题面的几个关键点题面参数数值说明询问组数 T最多 10^6意味着每组测试数据都要足够快n 的范围0 到 10^18线性循环绝对无望结果要求对 1000000007 取模防止大数溢出和结果超级大初始项F(0)1, F(1)1注意不是 F(0)0n的上限直接决定了朴素循环不可行即使每次只做一个加法做到n 10^18也是天文数字。所以这道题至少需要O(log n)级别的解法。取模常数1000000007是个很经典的质数模数它后面的含义是结果随时可能大到连 64 位整数都装不下必须在每一步中间过程里就进行取模运算。这里还埋着一个很常见的边界问题F(0)到底算不算这样一道题我在第一次提交时就因为没有单独处理n 0的情况而险些翻车。题目给出F(0) 1后说明下标确实从 0 开始那么矩阵快速幂的初始状态必须把它考虑进去不能直接套教科书的F(0)0版本。2. 三种解法从循环到矩阵快速幂的升级路径2.1 纯循环递推O(n) 的底线解法如果你没看到n的上限第一反应一定是写一个循环数组MOD 1000000007 def fib_linear(n): if n 0: return 1 if n 1: return 1 a, b 1, 1 for _ in range(2, n 1): a, b b, (a b) % MOD return b这个做法的思路很朴素维护两个变量a和b每次循环里把b作为新的当前项把a更新为上一项。空间复杂度是O(1)时间复杂度是O(n)。在n只有几十万或者几百万时这个写法干净利落没有任何问题。评论区总有人问“为什么不用列表把所有值都存下来”我的习惯是能滚动更新就不要开数组。因为你并不知道题目的n会不会在某个 edge case 里变得特别大开一个长度为n1的列表空间开销是O(n)在一些内存限制为 64MB 的老题目里可能直接就内存超限了。滚动变量每次循环只保留前两项本来就是递推数列的最优空间写法还省掉了数组下标越界的烦恼。2.2 取模的正确姿势边加边取不要攒到最后在上面这段代码里我每次都做了(a b) % MOD。有读者可能觉得多此一举既然最终结果也是取模为什么不先算出完整结果再一次性取模这个想法在n很小时成立在n较大会爆炸。因为F(100)就已经有 21 位数字了F(1000)超过 200 位哪怕用 Python 的大整数计算和维护这种超级大数的开销也比普通整数大得多。C 的long long更不用说最多只能存到F(90)左右F(93)就超过9.2e18的上限了。正确的做法是在每次加法之后立刻取模。这利用了模运算的分配律(A B) % MOD ((A % MOD) (B % MOD)) % MOD所以中间过程里每一项都保持在一个小于模数的数值范围内加法结果最多不超过2 * MOD依然在 64 位整数的安全区间里。这也是整个递推过程中可以放心使用快速幂的前提——每个中间矩阵元素都不会失控膨胀。2.3 矩阵快速幂真正能在 10^18 面前活下来的解法n高达10^18时O(n)的循环即使每次迭代只花 1 纳秒也需要约 30 年才能跑完。要对付这个量级必须把递推关系转化成矩阵幂运算然后用二进制幂加速。递推关系可以改写为矩阵形式[F(n) ] [1 1] * [F(n-1)][F(n-1)] [1 0] [F(n-2)]如果设初始向量为V(1) [F(1), F(0)]^T [1, 1]^T那么V(n) M^(n-1) * V(1)其中M就是矩阵[[1, 1], [1, 0]]。这样就把“算第 n 项”变成了“计算矩阵的 n-1 次幂”而矩阵幂可以用快速幂在O(log n)时间内完成。每次矩阵乘法只涉及四个元素都是常数次 64 位整数乘法和加法所以总时间复杂度大约是O(8 * log n)。核心代码如下#include cstdio const long long MOD 1000000007LL; struct Mat { long long a[2][2]; Mat() { a[0][0] 1; a[0][1] 1; a[1][0] 1; a[1][1] 0; } }; Mat mul(Mat A, Mat B) { Mat C; C.a[0][0] 0; C.a[0][1] 0; C.a[1][0] 0; C.a[1][1] 0; for (int i 0; i 2; i) { for (int j 0; j 2; j) { for (int k 0; k 2; k) { C.a[i][j] (C.a[i][j] A.a[i][k] * B.a[k][j]) % MOD; } } } return C; } Mat power(Mat base, long long exp) { Mat res; res.a[0][0] 1; res.a[0][1] 0; res.a[1][0] 0; res.a[1][1] 1; while (exp 0) { if (exp 1) res mul(res, base); base mul(base, base); exp 1; } return res; } int main() { long long n; while (scanf(%lld, n) 1) { if (n 0 || n 1) { printf(1\n); continue; } Mat M; Mat R power(M, n - 1); long long ans (R.a[0][0] R.a[0][1]) % MOD; printf(%lld\n, ans); } return 0; }这里的Mat默认构造函数就把矩阵初始化为[[1,1],[1,0]]。power函数执行快速幂res初始化为单位矩阵。最后ans (R.a[0][0] R.a[0][1]) % MOD是怎么来的因为最终状态向量是[F(n) ] R * [F(1)] R * [1][F(n-1)] [F(0)] [1]所以F(n)恰好等于矩阵第一行两个元素之和。这个细节非常容易写错我见过不少人明明矩阵快速幂写对了最后却返回了R.a[0][0]单独一个值结果只对了一半。3. 完美踩坑记录五个让你 TLE 或 WA 的细节3.1 递归解法在大 n 下爆栈又爆时间很多人的第一版是递归def fib(n): if n 0 or n 1: return 1 return fib(n - 1) fib(n - 2)这段代码在n 40左右还能勉强跑完但到n 50就已经肉眼可见地卡顿。因为这个递归会指数级分裂时间复杂度是O(phi^n)phi大约是 1.618。更致命的是如果n继续变大Python 的默认递归深度限制大约 1000 层会直接触发RecursionErrorC 则可能爆栈程序崩溃。我自己的经验是除非题目明确要求“用递归实现”否则递推数列题一律不要用递归写。递归在这种场景下唯一的用处是帮助你在草稿纸上理清递推关系真的提交时还是老老实实循环或者矩阵快速幂。如果你非要在递归里用记忆化搜索也要注意n 10^18时根本不可能开这么大的缓存数组这条路依然走不通。3.2 取模时机不同结果天差地别我在第一次写矩阵乘法时为了“少做几次取模”把取模放在了三层循环结束之后for (int i 0; i 2; i) for (int j 0; j 2; j) { int s 0; for (int k 0; k 2; k) s s A.a[i][k] * B.a[k][j]; // 错 C.a[i][j] s % MOD; }问题在于A.a[i][k]已经是取模后的值小于MOD两个相乘小于1e18这没问题。但是四个乘积加在一起就超过了long long的表示上限。C 里发生溢出之后的行为是未定义的可能是负数也可能是个莫名其妙的数甚至不同编译器结果都不一样。正确做法是把每次乘积结果及时取模然后加入累加器或者用__int128做中间类型。我发现更稳妥的方案是“乘一次加一次立刻取模”也就是这篇文章前面mul函数里的写法。虽然看起来多写了几个%实际耗时差别几乎可以忽略换来的是长期安全。3.3 快速幂的初始矩阵必须是单位矩阵这也是一个经典的隐藏坑。初学快速幂时我们处理数字幂时会把res初始化为 1因为 1 是乘法单位元。到了矩阵快速幂res就必须是单位矩阵[[1,0],[0,1]]而不是[[1,1],[1,0]]。我第一次写这段代码时图省事直接Mat res;结果res被默认构造成了递推矩阵快速幂算出来自然是错的。这个 bug 很难发现因为n 0和n 1你通常已经单独特判了n 2时结果可能碰巧正确到n 5以后才越来越离谱。排查的方式是手动验算几个小数据比如n 2期望输出 2n 3期望输出 3一旦结果不对优先检查初始矩阵和最终取答案的方式。3.4 多组输入时矩阵状态必须每次重置题目给了多组测试数据类似while (scanf(%lld, n) 1) { // 处理每组 n }有些同学把矩阵定义成了全局变量快速幂函数每次都会修改它。如果在第一组数据跑完后没有重新初始化第二组就会沿用上一轮的残留状态导致输出错乱。处理办法有两种要么像我在完整代码里那样在while循环内部每次重新定义Mat M;构造一个新矩阵要么定义全局矩阵但每次进入while时显式重置四个元素。我偏向于前者因为局部变量的生命周期天然保证每次都是全新的省心。3.5 Python 大整数和 C 长整数的边界思维差异如果你是 Python 选手可能会觉得取模和溢出都不是事因为 Python 的整数可以无限长。但实际刷题时Python 的“无限长”反而是个陷阱大整数运算比普通整数慢很多如果不做每步取模到了几千位的大数运算时间会指数级上升导致超时。C 选手则要时刻记住long long的上限大约是9.22e18。模数是1000000007乘法后最大值约1e18两个乘积相加不会超过2e18这还在安全范围内。但如果你把模数改成一个更大的数比如1e18级别的模数那么乘法后的结果就可能溢出。做题前看一眼模数大小判断中间步骤的乘积是否会超过9e18是个非常重要的习惯。4. tracker 里的复盘笔记我是怎么把这道题吃透的4.1 一刷记录先求通过再求优化我的打卡 sheet 里第一行记的是这样一串信息轮次解法运行时间内存结果一刷循环递推1.2s2MB超时数据点 n 较大二刷递归记忆化无法运行栈溢出放弃三刷矩阵快速幂约 20ms2MB通过一刷直接写循环是因为我先看样例没注意数据范围。提交后看到超时才点开题目下方的说明发现n居然能到10^18。这是我熟悉的剧情很多题目不是算法有多难而是你是否愿意花 30 秒去读完整的数据范围约束。从那以后我的每日一题流程变成了“先看约束再看题目描述”看到10^18这种数字第一反应就是快速幂、二分、数论这些对数级方案。4.2 二刷对比不同写法在不同语言下的差距为了把这道题吃透我在本地额外测了三种语言的矩阵快速幂语言实现方式耗时n 10^181000 组备注C手写矩阵快速幂约 18ms最快注意long longJava二维数组实现约 35ms主要耗在对象创建Python列表实现约 90ms能过但要注意每步取模这个对比带给我的启发是矩阵快速幂的耗时核心不是语言而是“矩阵乘法是否常数足够小”。2x2 矩阵的乘法只有 8 次乘法和 4 次加法即使 Python 也能接受。如果哪天遇到 3x3 甚至更高阶的递推维度变大的开销是立方的那才是真正需要压常数的时刻。4.3 举一反三从波斐契那数列到高阶递推复盘的最后一步我把“波斐契那数列”这道题跟一系列递推题联系在了一起。比如经典的“泰波那契数列”规则是前三项之和矩阵就变成了[[1,1,1],[1,0,0],[0,1,0]]维度是 3x3。再比如一些带系数的递推式F(n) 2*F(n-1) F(n-2)矩阵就变成[[2,1],[1,0]]。万变不离其宗只要递推关系是线性的、常系数的都可以用矩阵快速幂转换成O(log n)求解。所以我在打卡表的“扩展思路”一栏里写了一条给自己看的经验以后再遇到任何线性递推的题目不管对不对先把递推式写成矩阵乘法的形式这是最不容易错的一步。从递推式到矩阵的转换过程本质上是个形式化的体力活但一旦跨过这个门槛题目就变成了纯粹的快速幂模板题。我想很多人刷题时都有类似的体会最难的往往不是代码实现而是“意识到该用什么模型”。波斐契那数列这道题其实是个极其标准的引路人——名字看起来陌生内核却无比亲切。它教我的不是背模板而是如何从题面的一堆文字里快速抓住“递推关系 数据范围 模数”这三个关键变量然后选择合适的工具。如果你也在打卡刷题建议把这道题的个人复盘写得细一点尤其是把“为什么用矩阵快速幂”“为什么每步取模”“边界怎么处理”这些思考过程记录下来。光看别人的题解是记不牢的亲手写一遍、错一遍、再改一遍才真正算自己的东西。