因为n达10⁹时o(n)dp和指数递归不可行，矩阵快速幂可将时间优化至o(log n)；爬楼梯是斐波那契递推，对应2×2转移矩阵[[1,1],[1,0]]，通过m^(n−1)左乘初始向量即可得f(n)。
为什么爬楼梯要用矩阵快速幂而不是递归或DP？
因为当 n 达到 10⁹ 级别时，普通线性 DP 的 O(n) 时间和递归的指数爆炸都不可接受；而矩阵快速幂能把时间压到 O(log n)，空间也只用 O(1) —— 前提是你确认递推关系能写成固定维度的线性变换。
爬楼梯（每次走 1 或 2 阶）本质是斐波那契：f(n) = f(n−1) + f(n−2)。这个二阶线性递推，刚好对应一个 2×2 转移矩阵。
怎么构造转移矩阵并验证它？
目标是把状态向量 [f(n), f(n−1)]ᵀ 变成 [f(n+1), f(n)]ᵀ。代入递推式：
f(n+1) = f(n) + f(n−1)
f(n) = f(n)
所以：
[f(n+1)] [1 1] [f(n) ]<br>[f(n) ] = [1 0] [f(n−1)]
即转移矩阵 M = {{1,1},{1,0}}。只要初始向量是 [f(1), f(0)] = [1, 1]（注意：f(0)=1 表示“站在地面也算 1 种方式”），那么 M^(n−1) * [f(1),f(0)]ᵀ 就给出 [f(n), f(n−1)]ᵀ。
常见错误：
- 初始状态搞错：f(0) 取 0 还是 1？取决于题意——若 n=0 是合法输入且答案为 1，则 f(0)=1；否则按题干定义对齐
- 矩阵乘法顺序写反：C++ 中习惯左乘，确保
result = M^k * base，不是base * M^k - 没处理 n=0 或 n=1 的边界，直接套快速幂导致越界或结果错
C++ 实现矩阵快速幂要注意哪些细节？
核心是自定义 2×2 矩阵乘法 + 快速幂模板，所有运算需模 MOD（题目若没要求可设为 1e9+7 防溢出）。
关键点：
- 用
vector<vector long>></vector>或结构体封装矩阵，但 2×2 固定大小推荐用数组：array<array long>, 2></array> - 单位矩阵是
{{{1,0},{0,1}}}，不是全 1 - 快速幂中，指数为 0 时直接返回单位矩阵；n=1 时不能跳过，要进循环或单独判
- 乘法中间结果可能超
long long：用__int128（GCC）或手动模乘防溢出，例如：(a * b) % MOD改成(a % MOD) * (b % MOD) % MOD
简短骨架：
array<array long>, 2> matMul(auto& A, auto& B, long long MOD) {<br> array<array long>, 2> C{};<br> for (int i = 0; i for (int j = 0; j for (int k = 0; k C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;<br> return C;<br>}<br><br>array<array long>, 2> matPow(array<array long>, 2> M, long long n, long long MOD) {<br> array<array long>, 2> res = {{{1,0},{0,1}}};<br> while (n) {<br> if (n & 1) res = matMul(res, M, MOD);<br> M = matMul(M, M, MOD);<br> n >>= 1;<br> }<br> return res;<br>}</array></array></array></array></array>
如何从矩阵结果还原 f(n)？
算出 M^(n−1) 后，左乘初始向量 [f(1), f(0)]。由于我们只关心 f(n)，其实只需取结果矩阵第一行与初始向量的点积：
f(n) = M^(n−1)[0][0] * f(1) + M^(n−1)[0][1] * f(0)
若 f(0)=1、f(1)=1，则 f(n) = M^(n−1)[0][0] + M^(n−1)[0][1]；若 f(0)=1、f(1)=1，且 n=0 单独返回 1，那统一写法是：
- n == 0 → return 1
- n == 1 → return 1
- n >= 2 → 计算
M^(n−1)，再按上式组合
容易被忽略的是：不同题目对 f(0) 定义不一致。LeetCode 70 默认 n ≥ 1，f(1)=1、f(2)=2，此时初始向量应为 [f(2), f(1)] = [2,1]，转移后求的是 M^(n−2)。务必核对题干的起始条件。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
