http://acm.hdu.edu.cn/showproblem.php?pid=1575
思路：直接用矩阵快速幂即可，（记得初始化数组，不然会wa）
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MOD 9973 using namespace std; int k,n,t; struct Matrix { int matrix[12][12]; }a,b; Matrix matrix_mul(Matrix x1,Matrix y1) { Matrix c; memset(c.matrix,0,sizeof(c.matrix)); for(int x=0;x<n;x++) for(int y=0;y<n;y++) for(int z=0;z<n;z++) c.matrix[x][y]+=x1.matrix[x][z]*y1.matrix[z][y],c.matrix[x][y]%=MOD; return c; } void matrix_quick_power() { memset(b.matrix,0,sizeof(b.matrix)); for(int x=0;x<n;x++) b.matrix[x][x]=1; while(k) { if(k&1) b=matrix_mul(a,b); a=matrix_mul(a,a); k=k/2; } } int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); for(int x=0;x<n;x++) for(int y=0;y<n;y++) scanf("%d",&a.matrix[x][y]); matrix_quick_power(); int sum=0; for(int x=0;x<n;x++) sum+=b.matrix[x][x],sum%=MOD; printf("%d\n",sum); } }