企业官网建设流程全解析

1. 为什么爬楼梯这道题，值得用快速幂重新做一遍

如果你刷过 LeetCode 的 70 题“爬楼梯”，大概率第一反应是动态规划。dp[i] = dp[i-1] + dp[i-2]，一个循环搞定，代码短、思路直白，看起来没有任何问题。我一开始也是这么写的，直到有一次在讨论区看到有人提起“这题能用矩阵快速幂做到 O(log n)”，我才意识到自己对这道题的理解其实停留在最表层。

爬楼梯的题干大家都熟：每次可以爬 1 级或 2 级台阶，问爬到第 n 级有多少种不同的方法。n 的范围在 LeetCode 原题里是 1 到 45，这个规模下 DP 的 O(n) 和快速幂的 O(log n) 在耗时上几乎没有肉眼可见的差别，跑出来都是 0ms 级别。但问题是：如果 n 变成 10^18 呢？或者更实际一点，如果这题出现在面试里，面试官追问一句“你能不能把时间复杂度再降一档”，你该怎么办？

这篇文章就是把这件事讲透：从斐波那契数列的矩阵形式出发，讲清楚怎么把爬楼梯的递推关系改写成矩阵乘法，再讲快速幂怎么把 O(n) 的循环压成 O(log n) 的二进制拆分运算。全程 C++ 实现，关键步骤给注释，顺便把取模、整数溢出这类实际写代码时一定会踩的坑也一起说了。

适用的人：已经会用 DP 解爬楼梯、但对“更优解”只有模糊概念的刷题党；准备面试、担心被追问复杂度的求职者；以及对矩阵运算在算法题里的应用感兴趣、想建立“线性递推都能用矩阵快速幂加速”这个思维模型的人。

2. 从 DP 到矩阵乘法：爬楼梯的递推关系藏着一个线性代数结构

先回到最基础的递推式。设f(n)表示爬到第 n 级台阶的方法数，那么：

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

边界条件是f(1) = 1，f(2) = 2。这个式子的含义很直观：到达第 n 级台阶，要么从第 n-1 级跨 1 步上来，要么从第 n-2 级跨 2 步上来，两种情况互斥，所以方法数是两者之和。

2.1 递推式的“状态”视角：把两个连续项打包成向量

DP 的写法是维护一个一维数组，从左往右填。但如果我们换一个视角，把“当前状态”定义为一个二维向量：

v(n) = [ f(n) ] [ f(n-1) ]

那么从v(n-1)到v(n)的转移，能不能用一个矩阵来表示？观察一下：

f(n) = 1 * f(n-1) + 1 * f(n-2) f(n-1) = 1 * f(n-1) + 0 * f(n-2)

把这两行写成矩阵形式：

[ f(n) ] [ 1 1 ] [ f(n-1) ] [ f(n-1) ] = [ 1 0 ] * [ f(n-2) ]

定义转移矩阵M = [[1, 1], [1, 0]]，那么：

v(n) = M * v(n-1)

再往前推：

v(n) = M^(n-2) * v(2)

其中v(2) = [f(2), f(1)]^T = [2, 1]^T。所以问题从“算一个递推数列的第 n 项”变成了“算一个 2x2 矩阵的 n-2 次幂，再乘一个向量”。这就是快速幂可以介入的地方。

2.2 为什么这个改写不是“炫技”，而是复杂度本质的改变

DP 一次循环只算一个f(i)，每一步依赖前一步的结果，是一个天然的串行过程，O(n) 跑不掉。而矩阵乘法有一个关键性质：矩阵乘法满足结合律。这意味着M^8可以拆成(M^4)^2，M^4可以拆成(M^2)^2，于是幂次可以二分地“跳”上去：算M^n只需要 O(log n) 次矩阵乘法，而不是 O(n) 次。

生活化一点理解：DP 是爬楼梯，一步一级，想上到第 100 级就得走 100 步；快速幂是坐电梯，电梯每按一次键，楼层数翻一倍，按 7 次就能到 128 层。这种复杂度量级的差异，在 n 很小的时候体现不出来，但 n 一旦来到 10^9 级别，O(n) 的循环可能需要几秒甚至更久，而 O(log n) 的矩阵快速幂只需要几十次运算，毫秒级出结果。

2.3 从爬楼梯到斐波那契：一个模型的两种面孔

爬楼梯的递推式f(n) = f(n-1) + f(n-2)本质上就是斐波那契数列，只是初始条件不同。经典斐波那契是F(0) = 0, F(1) = 1，而爬楼梯是f(1) = 1, f(2) = 2。所以矩阵快速幂这套方法，练会了爬楼梯这道题，等于顺手把 LeetCode 上所有斐波那契类的题目都打通了——比如“第 N 个泰波那契数”这类题，只需要把转移矩阵从 2x2 扩展成 3x3，思路完全一致。

这也是我建议大家不要只背 DP 写法的原因：同一套递推骨架，换一个数学视角，就能覆盖一大类题目，这个“迁移能力”才是刷题真正要训练的东西。

3. 矩阵快速幂的完整推导：从二进制拆分到 2x2 矩阵的乘法实现

快速幂这个名字，刷题的人通常第一反应是“整数的快速幂”，比如算3^10 mod 1000。思路是把指数拆成二进制，10 = 1010，于是3^10 = 3^8 * 3^2，幂次通过不断自乘得到，指数通过位运算右移遍历。矩阵快速幂没有任何新东西，就是把底数从整数换成矩阵，乘法从整数乘法换成矩阵乘法，仅此而已。

3.1 整数快速幂的二进制原理：先把这个彻底搞懂

假设要算a^13。13 的二进制是1101，也就是13 = 8 + 4 + 1。于是：

a^13 = a^(8+4+1) = a^8 * a^4 * a^1

快速幂的做法是：用一个变量base存储a^(2^i)，初始时i = 0，base = a。每次把指数右移一位，同时base = base * base，让 base 变成a^2, a^4, a^8……在移位的过程中，如果当前最低位是 1，就把 base 乘到结果变量result里。

C++ 代码长这样：

long long fastPow(long long a, long long n) { long long result = 1; while (n > 0) { if (n & 1) { result *= a; } a *= a; n >>= 1; } return result; }

这段代码的关键点：if (n & 1)判断当前二进制位是否为 1，n >>= 1把指数右移，a *= a让底数加速自乘。循环次数等于 n 的二进制位数，即log2(n)级别。

3.2 从整数到矩阵：把乘法规则换成矩阵乘法

把上述代码里的整数换成 2x2 矩阵，就得到了矩阵快速幂。C++ 里面表示矩阵，最朴素的方式是定义一个结构体，或者直接用vector<vector<long long>>。考虑到性能和代码可读性之间的平衡，我推荐用结构体加定长数组的方式，因为 2x2 矩阵的乘法规则是固定的，没必要用动态数组增加复杂度。

矩阵乘法是快速幂的核心运算，两个 2x2 矩阵相乘的公式先明确一下：

C[0][0] = A[0][0]*B[0][0] + A[0][1]*B[1][0] C[0][1] = A[0][0]*B[0][1] + A[0][1]*B[1][1] C[1][0] = A[1][0]*B[0][0] + A[1][1]*B[1][0] C[1][1] = A[1][0]*B[0][1] + A[1][1]*B[1][1]

为什么 2x2 矩阵乘法是“左边行乘右边列”这个规则？线性代数里的定义：结果矩阵C[i][j]等于 A 的第 i 行与 B 的第 j 列对应元素乘积之和。这个规则不是拍脑袋来的，它是为了保持线性变换的复合性质——先做变换 B 再做变换 A，等价于一个变换矩阵 A*B。这个性质正是矩阵快速幂能够加速递推计算的数学根基。

在 C++ 里实现 2x2 矩阵乘法，建议先封装一个函数：

using Matrix = array<array<long long, 2>, 2>; Matrix multiply(const Matrix& a, const Matrix& b) { return {{ {a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]}, {a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]} }}; }

用std::array而不是vector，因为大小在编译期就固定了，没有堆分配，性能更好，代码也更接近“数学定义”本身。

3.3 矩阵快速幂的完整实现：模板化的幂函数

有了乘法函数，快速幂函数水到渠成：

Matrix identity() { return {{ {1, 0}, {0, 1} }}; } Matrix fastPow(Matrix base, long long exp) { Matrix result = identity(); // 单位矩阵等价于整数快速幂中的 1 while (exp > 0) { if (exp & 1) { result = multiply(result, base); } base = multiply(base, base); exp >>= 1; } return result; }

这里有一个很容易忽略的点：为什么初始 result 是单位矩阵，而不是全 0 矩阵？因为单位矩阵在矩阵乘法里的角色等同于整数里的 1。任何矩阵乘以单位矩阵都保持自身不变，这保证了在指数二进制位为 0 的那些幂次被跳过时，结果不会受到干扰。如果你把 result 初始化成全 0，那么无论 exp 是什么，最终结果都是全零矩阵——这是一个非常隐蔽、但几乎每个自己写过矩阵快速幂的人都会踩一次的坑。

3.4 从矩阵幂到最终答案：别忘了边界项的调整

现在有了M^(n-2)之后，怎么得到f(n)？

回顾前面的推导：

v(n) = M^(n-2) * v(2)

其中v(2) = [f(2), f(1)]^T = [2, 1]^T。所以：

f(n) = M^(n-2)[0][0] * 2 + M^(n-2)[0][1] * 1

用代码表示：

int climbStairs(int n) { if (n <= 2) return n; Matrix M = {{ {1, 1}, {1, 0} }}; Matrix powM = fastPow(M, n - 2); return powM[0][0] * 2 + powM[0][1] * 1; }

到这里，爬楼梯的矩阵快速幂解法已经完整了。但实际跑 LeetCode 的时候，你可能会发现返回类型是int，而矩阵里的中间结果可能超过int范围，这里又涉及一个取模和类型选择的问题，下一节细说。

4. 实际提交时的几个坑：取模、数据类型和边界条件

理论推导再漂亮，落到代码里总有几道坎。矩阵快速幂解爬楼梯，我实际写的时候踩过几个坑，逐个说一下。

4.1 原题 n 只有 45，为什么还要考虑溢出和取模

LeetCode 70 题的 n 最大是 45，这个规模下f(45)大约是 18 亿，还在int范围内（有符号 32 位整数的上限约 21.47 亿）。所以如果只是为了过这道题，用int也不会溢出。

但问题是这个解法不该被限制在 45 以内。LeetCode 的讨论区里经常有人把题目改造成“如果 n 很大怎么办”，面试官也可能追问。更常见的场景是：如果题目要求结果对 1e9+7 取模，比如 LeetCode 上很多动态规划题目的标准操作。这时候矩阵快速幂的优势才真正体现出来：n 再大，也能在几十次乘法内算出模意义下的答案。

所以我的建议是：直接用long long存储中间结果，并在乘法过程中适时取模。这样代码既能应对原题的规模，也能无缝扩展到“大 n 取模”的变体题。

4.2 C++ 负数取模的坑：%在中间结果上怎么用才对

C++ 里%运算对负数的行为是：结果符号跟随被除数。也就是说-1 % 1000000007的结果是-1，而不是数学意义上的1000000006。

在矩阵快速幂里，如果所有输入都是非负的，乘法结果也是非负的，取模不会出现负数问题。这也是为什么我建议不要用“先乘再减”之类的小聪明来优化——保持矩阵元素始终非负，取模就永远是安全的。

const long long MOD = 1000000007LL; Matrix multiply(const Matrix& a, const Matrix& b) { return {{ {(a[0][0]*b[0][0] % MOD + a[0][1]*b[1][0] % MOD) % MOD, (a[0][0]*b[0][1] % MOD + a[0][1]*b[1][1] % MOD) % MOD}, {(a[1][0]*b[0][0] % MOD + a[1][1]*b[1][0] % MOD) % MOD, (a[1][0]*b[0][1] % MOD + a[1][1]*b[1][1] % MOD) % MOD} }}; }

注意每一对乘积相加前都先取了模，避免两个long long相乘后再相加溢出long long。这一步在竞赛里叫“边乘边模”，是避免溢出的标准姿势。

4.3 n 为 1 和 2 时，别让矩阵参与计算

n <= 2时直接返回 n，这个提前 return 不只是性能优化，更是逻辑正确性的要求。因为矩阵快速幂基于M^(n-2)，当n=1时n-2为-1，指数变成负数，快速幂的循环根本不会执行，返回的单位矩阵再乘v(2)得到的结果完全不对。

更稳妥的做法是单独处理小规模情况。LeetCode 的climbStairs函数里用if (n <= 2) return n;一挡，后面的矩阵运算就只处理n >= 3的情况，安全又清晰。

4.4std::array初始化一个容易编译报错的细节

std::array的初始化方式比较死板：必须用双花括号。我第一次写矩阵结构体时，写成了单层花括号，编译直接报错。正确写法是：

using Matrix = array<array<long long, 2>, 2>; Matrix M = {{ {1, 1}, {1, 0} }};

外层花括号对应整个array，内层花括号对应内部的每一个array<long long, 2>。如果嫌这个语法烦，也可以用函数返回的方式：

Matrix matrix = {{ {1, 1}, {1, 0} }};

或者定义一个 helper 函数返回初始矩阵，让调用处更简洁。这个细节写一次就会记住，但第一次写的人大概率要被报错折磨几分钟。

5. 完整题解代码与本地调试建议

把上面的内容整合成一份可以在 LeetCode 上直接提交的完整 C++ 代码：

#include <array> using namespace std; using Matrix = array<array<long long, 2>, 2>; const long long MOD = 1000000007LL; Matrix multiply(const Matrix& a, const Matrix& b) { return {{ {(a[0][0]*b[0][0] + a[0][1]*b[1][0]) % MOD, (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % MOD}, {(a[1][0]*b[0][0] + a[1][1]*b[1][0]) % MOD, (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % MOD} }}; } Matrix identity() { return {{ {1, 0}, {0, 1} }}; } Matrix fastPow(Matrix base, long long exp) { Matrix result = identity(); while (exp > 0) { if (exp & 1) { result = multiply(result, base); } base = multiply(base, base); exp >>= 1; } return result; } class Solution { public: int climbStairs(int n) { if (n <= 2) return n; Matrix M = {{ {1, 1}, {1, 0} }}; Matrix powM = fastPow(M, n - 2); return (powM[0][0] * 2 % MOD + powM[0][1] % MOD) % MOD; } };

有人说 LeetCode 原题不要求取模，你在代码里加了MOD会不会返回错误结果？不会。因为原题 n 最大 45，结果远小于 MOD，取模前后值完全一致。加了 MOD 之后，代码能跑原题，也能跑任何“结果取模”的变体，属于向前兼容。

本地调试的时候，我建议你手动跑几个小用例验证正确性：

n=1 -> 1 n=2 -> 2 n=3 -> 3（1+1+1, 1+2, 2+1） n=4 -> 5 n=5 -> 8

对应 LeetCode 的示例输出。如果这几个用例过了，基本逻辑就不会有问题。

6. 从爬楼梯到竞赛常用技巧：矩阵快速幂还能加速什么样的递推

爬楼梯只是矩阵快速幂最基础的应用场景。刷题圈子里流传一句话：“一切线性递推都可以用矩阵快速幂加速到 O(log n)。”这句话怎么理解？关键在于识别“线性”两个字。

6.1 什么样的递推式能套矩阵快速幂：线性递推的判定标准

设一个序列的第 n 项可以由前面若干项的线性组合表示，即满足形如：

F(n) = a1*F(n-1) + a2*F(n-2) + ... + ak*F(n-k)

并且系数 a1..ak 是常数，不随 n 变化，那么这个递推式就一定能写成 k 维向量的矩阵转移形式。比如斐波那契是二阶线性递推F(n) = F(n-1) + F(n-2)，对应 2x2 转移矩阵；泰波那契是三阶线性递推T(n) = T(n-1) + T(n-2) + T(n-3)，对应 3x3 转移矩阵。

如果递推式里带了常数项，比如F(n) = F(n-1) + F(n-2) + c，只要把状态向量从 k 维扩展成 k+1 维，把常数 c 作为一维恒为 1 的分量放进去，矩阵规模加一，仍然可以处理。如果系数本身还随 n 变化，矩阵快速幂就不适用了，因为转移矩阵不再固定，无法用幂运算合并多个转移步骤。

6.2 LeetCode 里适合用矩阵快速幂热身/练手的几类题

• 斐波那契数（509）：最基本的 2x2 矩阵，和爬楼梯几乎一样，适合验证模板代码的正确性。
• 第 N 个泰波那契数（1137）：T(n) = T(n-1) + T(n-2) + T(n-3)，需要 3x3 矩阵，可以练状态向量扩展的手感。
• 铺瓷砖 / 多米诺骨牌类问题（很多变体）：本质上是转移矩阵不同的线性递推，识别出递推式以后直接套模板。
• 一些组合计数类问题：比如“用 1x2 和 2x1 的多米诺骨牌铺满 2xn 的棋盘”，递推式恰好也是F(n) = F(n-1) + F(n-2)，只是看起来和爬楼梯完全不同，但数学结构一模一样。

如果你把爬楼梯的矩阵快速幂源码存成一个模板，遇到线性递推的题目时改一下状态维度和转移矩阵，就能快速出解。这个模板的复用价值，比单独背一道题的解法要大得多。

6.3 选这个解法，还是选 DP？一个实用的决策建议

很多读者会问：面试碰到爬楼梯，到底该写 DP 还是写矩阵快速幂？

我的建议是：先花 30 秒写 DP 保证正确性，再花一两分钟提一嘴“如果 n 很大，可以用矩阵快速幂优化到 O(log n)”。面试官真正想考察的是你能不能意识到 DP 的解有时间复杂度上的天花板，以及你有没有能力换一个数学视角重新建模。直接上来写矩阵快速幂，一方面代码量大、容易出错，另一方面如果面试官只是想看你有没有掌握基础 DP，反而显得用力过猛。

但在面试的追问环节，矩阵快速幂是一个非常加分的“第二解”。能把递推改写成矩阵乘法、能解释清楚结合律为什么让幂运算可行、能分析出 O(log n) 的时间复杂度——这三步走完，面试官对你的评价会明显上一个台阶。

7. 一组快速验证的对照数据：从 n=1 到 n=10 的爬楼梯结果

算法题做到最后，最怕的不是不会写，而是写了但不知道自己写对没有。矩阵快速幂里有矩阵乘法、二进制拆分这些环节，出错的地方比纯 DP 多，所以一套可靠的对照数据特别重要。

以下是从 n=1 到 n=10 的爬楼梯方法数，都是手算+DP 双重验证过的：

这个数列就是斐波那契数列去掉第一项之后的结果。如果快速幂版代码跑出来的前 10 项和这张表完全一致，说明矩阵乘法和幂次部分基本没有逻辑错误。

再给一个稍大的值：n = 30时，爬楼梯方法数是 1346269。n = 40时是 165580141。n = 45时是 1836311903，注意这个数已经逼近int上限（2147483647）了，所以原题才把 n 的上限定为 45——如果 n 再大一点，int就装不下了。这也是 LeetCode 设计题目时留的一个“安全边界”，细想挺有意思。

如果你把 n 改到 50 甚至 100，用 DP 跑没问题，但用矩阵快速幂跑速度更快，因为运算次数是 log n 级别。n = 100的爬楼梯方法数是573147844013817084101，这个数字已经远超long long的上限（约 9.22e18），所以实际竞赛中遇到大 n 一定会要求取模。取模版代码在这种情况下才是真正发挥价值的时候。

8. 总结一下我对爬楼梯+快速幂这个组合的实操体会

这道题我前后用 DP、矩阵快速幂各写了一遍，耗时上在 LeetCode 原题规模下没有区别，但理解深度差别很大。DP 解法让我记住了递推公式，矩阵快速幂解法让我真正理解了“为什么这个递推可以用更快的算法”。

几个实操层面的经验和建议，在这里一并分享：

第一，矩阵快速幂的代码模板一定要独立存储。不要每次临时推倒重写。把multiply、identity、fastPow这三个函数作为固定模板保存下来，遇到线性递推题目时只改矩阵维度、矩阵内容和最终取值公式，能节省大量时间。我自己的模板放在本地一个独立的matrix_pow_template.h文件里，刷题时直接拖过来用。

第二，取模别偷懒。即使原题不要求取模，也建议在中间步骤加MOD常量。原因一是防止未来题目改造成大 n 场景，原因二是培养边乘边模的肌肉记忆——等你真的遇到需要取模的题目时，再临时改代码容易漏改某个乘法，产生隐蔽 bug。我见过不止一个人因为中间某一处乘积没有取模，导致整个答案错误且难以排查。

第三，面试时先给 DP 解，再给快速幂解，这个顺序不要乱。上来就秀矩阵运算，如果面试官本身不熟悉线性代数，你解释起来费劲不说，还可能让他觉得你在背模板。先给出最直观、最稳妥的 DP 解法，留下一个“有没有更优解”的尾巴，等面试官追问时再引出矩阵快速幂，节奏更自然，也更符合真实工作中“先求正确、再求优化”的工程思维。

爬楼梯这道题本身不难，但它是通往“矩阵快速幂”这个强大算法家族的一扇门。把这道题彻底吃透，后续遇到任何二阶、三阶、甚至更高阶的线性递推，你都会比别的刷题者多一个趁手的工具。这也算是我刷题过程中，少数几道“一道题带出一类题”的代表作了。