用 matrix_power 将递推转矩阵幂可使时间复杂度从 O(n) 降至 O(log n)，n > 10⁶ 时优势显著；普通循环或递归在 n ≥ 10⁹ 时超时；右移用 n >>= 1 更安全；矩阵乘法需固定 i-j-k 顺序以保证缓存友好和正确性。
直接结论：用 matrix_power 把递推关系转成矩阵幂，时间复杂度从 O(n) 降到 O(log n)，n 超过 10⁶ 就明显快得多。
为什么普通循环或递归撑不住大 n
当 n 达到 10⁹ 或更大（比如洛谷 P1962 数据范围是 n ），迭代法要跑 10⁹ 次加法，实际超时；递归更不用提，栈爆、重复计算、指数爆炸全占了。这时候必须换数学结构——把线性递推“打包”进矩阵，靠快速幂跳着算。
- 斐波那契本质是线性递推：
f(n) = f(n-1) + f(n-2) - 它能被压缩成状态向量
[f(n), f(n-1)]，乘一个固定转移矩阵就推进一步 - 推 100 步 ≠ 做 100 次乘法，而是算转移矩阵的 99 次幂 → 快速幂只需约 log₂(99) ≈ 7 次矩阵乘
关键矩阵怎么构造：别记错下标和初始值
最常用形式是：
[[1, 1], [1, 0]]
它满足：[f(n), f(n-1)] * M = [f(n+1), f(n)]。注意不是左乘，也不是 [f(n-1), f(n)]，顺序错了结果全偏。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
- 若定义
f(0)=0, f(1)=1，则初始向量是[f(1), f(0)] = [1, 0]，求f(n)就算M^(n-1) - 若题设
f(1)=f(2)=1（如洛谷 P1962），初始向量是[f(2), f(1)] = [1, 1]，对应幂次是M^(n-2) - 千万别漏模：中间所有
a[i][k] * b[k][j]都得% MOD，否则 int64 直接溢出
快速幂部分怎么写才不出错
核心是二进制拆分 + 单位矩阵初始化。别手滑写成 res = 0 或漏掉 if (b & 1) 分支。
- 单位矩阵必须是
[[1,0],[0,1]]，不是全 1 或全 0 - 幂次变量要用无符号或 long long，
n >>= 1比n /= 2更安全（避免负数右移未定义行为） - 矩阵乘法三重循环顺序固定：
i行、j列、k求和，别颠倒k层位置，否则 cache 不友好且易索引越界 - 示例片段（C++）：
matrix mul(matrix a, matrix b) {
matrix c = {};
for (int i = 0; i < 2; ++i)
for (int k = 0; k < 2; ++k)
for (int j = 0; j < 2; ++j)
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
return c;
}
<p>matrix pow(matrix base, long long exp) {
matrix res = {{1, 0}, {0, 1}};
while (exp) {
if (exp & 1) res = mul(res, base);
base = mul(base, base);
exp >>= 1;
}
return res;
}容易被忽略的边界和性能点
真正上线或交题时，n=0、n=1、n=2 这几个值最容易让矩阵逻辑崩掉——它们往往不走快速幂主干，但又不能硬返回常量（比如题目要求模意义下，f(0) 可能是 0，也可能是 1）。
- 务必单独判断
n 并按题意返回，别强行塞进矩阵流程 - 矩阵用
std::array<:array long>, 2></:array>比vector<vector>></vector>快，后者动态分配开销大 - 如果要多次查询不同
n，预处理幂表没意义——快速幂本身已足够快，且空间换不来实质收益 - MOD 是
1e9+7还是1e9+9？看题，别默认抄模板里的值
