emmmmm..就是矩阵快速幂，直接附代码：
1 #include <cstdio> 2 using namespace std; 3 const int maxn = 100; 4 const int mod = 9973; 5 struct Matrix 6 { 7 int m[maxn][maxn]; 8 }ans,res; 9 int n; 10 Matrix mul(Matrix a,Matrix b) 11 { 12 Matrix tmp; 13 for(int i = 1; i <= n; i++) 14 for(int j = 1; j <= n; j++) 15 tmp.m[i][j] = 0; 16 for(int i = 1; i <= n; i++) 17 for(int j = 1; j <= n; j++) 18 for(int k = 1; k <= n; k++) 19 tmp.m[i][j] += ((a.m[i][k] % mod)*(b.m[k][j] % mod))%mod; 20 return tmp; 21 } 22 23 void quickpow(int N) 24 { 25 for(int i = 1; i <= n; i++) 26 for(int j = 1; j <= n; j++) 27 if(i == j) ans.m[i][j] = 1; 28 else ans.m[i][j] = 0; 29 while(N) 30 { 31 if(N&1) ans = mul(ans,res); 32 res = mul(res,res); 33 N = N >>1; 34 } 35 } 36 37 int main() 38 { 39 int t,k,wu; 40 scanf("%d",&t); 41 while(t--) 42 { 43 scanf("%d%d",&n,&k); 44 wu = 0; 45 for(int i = 1; i <= n; i++) 46 for(int j = 1; j <= n; j++) 47 scanf("%d",&res.m[i][j]); 48 quickpow(k); 49 for(int i = 1; i <= n; i++) 50 for(int j = 1; j <= n; j++) 51 if(i == j) wu += ans.m[i][j]; 52 printf("%d ",wu%mod); 53 } 54 return 0; 55 }