1 #include<cstdio> 2 #include<cstring> 3 const int Mod= 9973; 4  5 struct matrix{ 6     int a[12][12], n; 7     matrix(int _n){ 8         n =_n; 9         memset(a,0,sizeof(a));10     }11     void identity(){12         for(int i=1; i<=n; ++i)        //单位矩阵的初始化，切记！ 13             a[i][i]= 1;        //如果没有这个的话就不能直接相乘了14     }15     matrix operator *(const matrix m2){16         matrix mul(this->n);17         for(int i=1; i<=n; ++i)18             for(int j=1; j<=n; ++j)19                 for(int k=1; k<=n; ++k)20                     mul.a[i][j]= (mul.a[i][j]+ this->a[i][k]*m2.a[k][j]%Mod)% Mod;21         return mul;22     }23 };24 25 matrix quick_mod(matrix &m, int p)26 {27     matrix ans(m.n);28     ans.identity();        // ans一定要为单位矩阵的！ 29     while(p){30         if(p&1)    ans= ans*m;31         m= m*m;32         p>>=1;33     }34     return ans;35 }36 37 int main()38 {39     int t,n,k,i,j;40     scanf("%d",&t);41     while(t--){42         scanf("%d%d",&n,&k);43         matrix m(n);44         for(i=1; i<=n; ++i)45             for(j=1; j<=n; ++j)46                 scanf("%d",&m.a[i][j]);47         matrix ans(n);48         ans= quick_mod(m,k);49         int sum= 0; 50         for(i=1; i<=n; ++i)51             sum= (sum+ ans.a[i][i])%Mod;52         printf("%d\n",sum);53     }54     return 0;55 }