题意：输入一个A:n×k和B:k×n的矩阵然后求两个矩阵的n*n次方如果直接求的话n很大会爆
我们可以转化为A×（B×A）^N*N-1*B然后B×A的矩阵很小就可以用快速幂直接求
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; const int mx = 1005; struct mat{ int a[mx][mx]; }c,r,x; int n,m; void getx(){ for(int i = 0; i < m; i++) for(int j = 0; j < m; j++){ x.a[i][j] = 0; for(int k = 0; k < n; k++) x.a[i][j] += r.a[i][k]*c.a[k][j]; } } mat calc(mat &x,mat &y){ mat z; for(int i = 0; i < m; i++) for(int j = 0; j < m; j++){ z.a[i][j] = 0; for(int k = 0; k < m; k++) z.a[i][j] += x.a[i][k]*y.a[k][j]; z.a[i][j]%=6; } return z; } mat getcnt(int n){ mat cnt = x; while(n){ if(n%2) { cnt = calc(cnt,x); } x = calc(x,x); n /= 2; } return cnt; } mat ans,z; int main(){ while(scanf("%d%d",&n,&m),n||m){ for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) scanf("%d",&c.a[i][j]); for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) scanf("%d",&r.a[i][j]); getx(); ans = getcnt(n*n-2); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){ z.a[i][j] = 0; for(int k = 0; k < m; k++) z.a[i][j] += c.a[i][k]*ans.a[k][j]; z.a[i][j]%=6; } for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){ ans.a[i][j] = 0; for(int k = 0; k < m; k++) ans.a[i][j] += z.a[i][k]*r.a[k][j]; ans.a[i][j]%=6; } int sum = 0; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) sum += ans.a[i][j]; printf("%d\n",sum); } return 0; }