A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。
直接矩阵快速幂取模。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 #define LL long long 6 const int mod=9973; 7 struct P{ 8 int a[15][15]; 9 }c,s; 10 int t,n; 11 LL k; 12 P mult(P a,P b) 13 { 14 P q; 15 for(int i=1;i<=n;i++) 16 { 17 for(int j=1;j<=n;j++) 18 { 19 q.a[i][j]=0; 20 for(int k=1;k<=n;k++) 21 q.a[i][j]=(q.a[i][j]+a.a[i][k]*b.a[k][j] )%mod; 22 } 23 } 24 return q; 25 } 26 void fuc(int p) 27 { 28 memset(c.a,0,sizeof(c.a)); 29 for(int i=1;i<=n;i++) c.a[i][i]=1; 30 while(p) 31 { 32 if(p&1) 33 { 34 c=mult(c,s); 35 } 36 s=mult(s,s); 37 p>>=1; 38 } 39 } 40 int main() 41 { 42 scanf("%d",&t); 43 while(t--) 44 { 45 scanf("%d%lld",&n,&k); 46 for(int i=1;i<=n;i++) 47 for(int j=1;j<=n;j++) 48 scanf("%d",&s.a[i][j]); 49 fuc(k); 50 int ans=0; 51 for(int i=1;i<=n;i++) ans=(ans+c.a[i][i])%mod; 52 printf("%d ",ans); 53 } 54 }