矩阵快速幂模板
今天学习了一下小红书上的矩阵快速幂
以为他写的那么短会写的多么高大上
原来只是把运算符重载了一下
先定义矩阵数据结构：
struct Mat {
double mat[N][N];
};
O(N^3)实现一次矩阵乘法
Mat operator * (Mat a, Mat b) {
Mat c;
memset(c.mat, 0, sizeof(c.mat));
int i, j, k;
for(k = 0; k < n; ++k) {
for(i = 0; i < n; ++i) {
if(a.mat[i][k] <= 0) continue; //不要小看这里的剪枝，cpu运算乘法的效率并不是想像的那么理想（加法的运算效率高于乘法，比如Strassen矩阵乘法）
for(j = 0; j < n; ++j) {
if(b.mat[k][j] <= 0) continue; //剪枝
c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
}
}
}
return c;
}