矩阵快速幂是将整数快速幂的二分乘法逻辑迁移到矩阵运算，需自定义矩阵乘法、正确初始化单位矩阵、按齐次线性递推构造转移矩阵，并在每步乘加中及时取模防溢出。
矩阵快速幂的核心就是把 pow 换成矩阵版的二分乘法
普通整数快速幂是用二进制拆分指数，每次平方底数、按位累乘；矩阵快速幂完全照搬这个逻辑，只是把 int 乘法换成矩阵乘法。关键不是“怎么造轮子”，而是“怎么让矩阵乘法能套进快速幂框架里”。
- 必须自己写
matmul函数，不能依赖std::vector的默认行为——它不支持重载*，且动态分配开销大 - 单位矩阵初始化要写对：
res[i][i] = 1，其他为 0；别用memset(res, 1, sizeof(res))这种粗暴操作 - 矩阵大小固定时（比如都是
2x2或3x3），优先用std::array<:array long n>, N></:array>，比vector<vector>></vector>快 3–5 倍，也避免越界访问
递推式怎么转成转移矩阵？看齐次线性关系的“维数”
不是所有递推都能压成矩阵，只有形如 f(n) = a·f(n−1) + b·f(n−2) + ... 这种无常数项、系数固定的齐次线性递推才行。非齐次（比如带 +1）或非线性（比如 f(n) = f(n−1) * f(n−2)）得先变形或放弃。
-
f(n) = f(n−1) + f(n−2)→ 需要 2 维状态：[f(n), f(n−1)]^T，转移矩阵是{{1,1},{1,0}} -
f(n) = 2*f(n−1) − f(n−2) + 3→ 含常数项，得升一维：状态扩成[f(n), f(n−1), 1]^T，最后一行补[0,0,1]来维持常数 1 不变 - 初始向量顺序必须和转移矩阵行列严格对应，错一位结果全乱——常见错误是把
[f(1), f(0)]写成[f(0), f(1)]
模运算下容易爆 long long？乘法中间结果必须及时取模
矩阵乘法本质是大量 a[i][k] * b[k][j] 累加，哪怕单个元素 ≤ 1e9，相乘就可能到 1e18，再加几次直接溢出。C++ 没有自动模乘，必须手动控制。
- 不要只在最后
% MOD，要在每一步乘加后都做：sum = (sum + 1LL * a[i][k] * b[k][j]) % MOD -
1LL *强制提升为long long，否则int * int先溢出再转，没用 - 如果
MOD接近2^31，连1LL * a * b都可能超2^63−1，这时得用__int128（GCC 支持）或龟速乘（不推荐，慢 10 倍）
为什么有时结果不对？检查这三个地方
矩阵快速幂代码短，但错一个下标或漏一次取模，输出就是错的，而且很难 debug。最常卡在：
立即学习“C++免费学习笔记（深入）”；
- 快速幂循环里写成了
while (n > 0)却忘了n >>= 1，死循环 - 转移矩阵行列搞反了：左乘还是右乘？标准是
res = M^k * init，所以矩阵乘法实现必须是A * B表示“先 B 后 A”作用，别颠倒 - 初始向量维度和矩阵不匹配：比如 3×3 矩阵配了 2×1 向量，编译不报错但运行时内存踩踏，值全乱
实际写的时候，先手算小样例（比如斐波那契第 5 项），把每一步矩阵和向量打印出来，比对着看哪步开始偏移，比瞎猜快得多。