矩阵快速幂不能复用整数快速幂代码，因需手写逻辑并替换乘法为自定义矩阵乘法；单位矩阵初始化、乘法顺序、零指数处理、三重循环顺序、防溢出模运算、固定大小用array、迭代版细节及状态向量维度匹配均须严格遵循。
直接用 std::pow 对矩阵无效，它只接受标量（double、int），传 vector<vector long>></vector> 会编译失败：no matching function for call to 'pow'。必须手写快速幂逻辑，并把“乘法”替换为自定义的矩阵乘法。
为什么矩阵快速幂不能复用整数快速幂代码
表面看只是把 res *= base 换成 res = mat_mult(res, base)，但隐藏陷阱极多：
- 单位矩阵初始化必须是
res[i][i] = 1，不是全 1，更不能用memset(res, 1, sizeof(res))——那会把所有字节设为 1，导致非对角线也变成 0x01010101 - 矩阵乘法顺序必须一致：若定义
mat_mult(A, B)表示 A × B，则快速幂中必须写res = mat_mult(res, base)，不能反着来；否则转移矩阵作用方向错误，结果全乱 - 指数为 0 时必须返回单位矩阵，漏判会导致
n == 0输出全零矩阵，而数学上 A⁰ 应为 I -
mat_mult的三重循环顺序必须是i-k-j（而非i-j-k），否则大矩阵下缓存命中率暴跌，性能差 3 倍以上
如何写一个防溢出的 mat_mult 函数
矩阵元素相乘极易爆 long long：两个 1e9 相乘就是 1e18，再累加几次就超限。不能只在最后取模。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 每一步点积都做模运算：
sum = (sum + 1LL * a[i][k] * b[k][j]) % mod，其中1LL *强制提升为long long防 int 溢出 - 如果
mod接近 1e9+7，且输入可能达 1e9，则1LL * a[i][k] * b[k][j]仍可能超 2⁶³−1（≈9e18）；此时 GCC 下推荐用__int128中转：(__int128)a[i][k] * b[k][j] % mod - 不要省略
mod参数——即使题目没说取模，也应传LLONG_MAX或一个足够大的数，避免中间值无声溢出 - 矩阵大小固定（如 2×2、3×3）时，用
std::array<:array long n>, N></:array>替代vector<vector long>></vector>，快 3–5 倍且无动态分配开销
迭代版 mat_pow 的关键细节
递归版易理解但有栈风险，工业级代码一律用迭代。核心逻辑和整数快速幂一致，但初始化和更新必须严格对应矩阵语义：
立即学习“C++免费学习笔记（深入）”；
- 初始
res必须是单位矩阵：for(int i = 0; i ，其他位置默认为 0（别依赖 vector 初始化） - 循环条件用
while (exp > 0)，不是!= 0，避免无符号类型误判 - 判断位用
exp & 1，不是exp % 2 == 1，前者更快且无符号安全 - 每次更新后必须右移：
exp >>= 1，漏写这句就是死循环 - 底数平方和结果累积都要调用
mat_mult，且模数参数必须一致，否则不同步取模会导致误差累积
最常被忽略的是：状态向量维度必须与转移矩阵严格匹配。比如用 3×3 矩阵推导含常数项的递推式，初始向量必须是 3×1，写成 2×1 不报错但内存越界——值全错还难 debug。
