std::pow对矩阵无效，因其专为标量设计，不支持自定义类型；必须手写矩阵快速幂，以单位矩阵为初始值、自实现矩阵乘法为核心，通过二分迭代将时间复杂度优化至O(log n)。
为什么直接用 std::pow 对矩阵无效
因为 std::pow 是为标量（double、int）设计的，不接受自定义类型或二维数组。C++ 标准库没有内置矩阵类型，更不会自动重载幂运算——你传个 vector<vector>></vector> 进去，编译器直接报错 no matching function for call to 'pow'。
必须手写快速幂逻辑，并封装矩阵乘法作为基础操作。
- 矩阵乘法不能复用
std::multiplies，得自己实现：结果第i行第j列 = 原矩阵第i行与第j列的点积 - 单位矩阵不是全 1，而是对角线为 1、其余为 0 的方阵；它是快速幂的初始“基数”
- 指数为 0 时必须返回单位矩阵，这点容易漏判，导致
n == 0时输出全零矩阵
如何写一个通用的矩阵快速幂函数（支持任意大小方阵）
核心是把整数快速幂的思路平移过来：把指数不断右移（n >>= 1），底数平方（mat = mat * mat），遇到奇数位就累积到结果中（res = res * mat）。区别只在“乘法”被替换为矩阵乘法。
下面是一个基于 vector<vector long>></vector> 的简洁实现，支持模运算（防溢出）：
vector<vector long>> mat_mult(const vector<vector long>>& a, const vector<vector long>>& b, long long mod) {
int n = a.size();
vector<vector long>> c(n, vector<long long>(n));
for (int i = 0; i vector<vector long>> mat_pow(vector<vector long>> base, long long exp, long long mod) {
int n = base.size();
vector<vector long>> res(n, vector<long long>(n));
for (int i = 0; i <pre class="brush:php;toolbar:false;">while (exp > 0) {
if (exp & 1) res = mat_mult(res, base, mod);
base = mat_mult(base, base, mod);
exp >>= 1;
}
return res;
}
- 三重循环顺序是
i-k-j，利于 CPU 缓存局部性；换成i-j-k在大矩阵下会明显变慢 -
mod参数建议始终传入（哪怕为0或LLONG_MAX），避免中间结果溢出——long long乘两个1e9就爆了 - 如果矩阵固定为 2×2（如斐波那契），可展开循环、用 4 个变量代替 vector，性能提升 3–5 倍
常见错误：维度不匹配、越界、未取模导致 WA
提交 OJ 时最常卡在这几类运行时/答案错误：
-
mat_mult中没检查a[0].size() == b.size()，输入非方阵时静默出错（应加断言或抛异常） - 初始化
res时用了vector(n, vector(n, 1))，结果得到全 1 矩阵，而非单位矩阵 - 模运算是
(a + b) % mod，但乘法部分写成a[i][k] * b[k][j] % mod—— 漏了外层括号，先取模再加，导致精度丢失 - 指数为负数？标准快速幂不处理，需提前判断并返回逆矩阵（一般题目不涉及）
什么时候不该用矩阵快速幂
它只适用于**线性递推关系能表示为固定系数方阵乘法**的场景，比如斐波那契、线性同余生成器、图上路径计数（边权为 1）等。以下情况不适合：
- 递推式含非线性项（如
f(n) = f(n-1) * f(n-2) + n）——无法写成A × F(n-1)形式 - 系数随
n变化（如f(n) = n × f(n-1) + f(n-2)）——矩阵A不再恒定 - 矩阵规模 > 100×100 且
exp不大（如）——普通快速幂的 <code>O(logN)优势被O(N³)乘法抵消，暴力累乘反而更快
真正省时间的地方，是当 exp 达到 1e18 而矩阵仅 2×2 或 3×3 时——此时乘法开销可忽略，log 次迭代才是关键。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
