矩阵快速幂 和一般的整数快速幂 是非常相似的 首先会以下 一般的快速幂
int pow(int n,int k) { int ans=1; while(k) { if(k&1) ans*=n; k>>=1; n*=n; } return ans; }那么现在运用优秀的推理能力 我们把上边的乘法 换成 矩阵乘法 问题不就解决了吗？
以下为代码（不一定能AC。。貌似有点小bug。。我留错了版本。。不过这样才更有意思不是吗。。）
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int mod=9973; int n,k; struct matrix { int a[12][12]; }init,unit; matrix mul(matrix t1,matrix t2) { matrix ans; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { ans.a[i][j]=0; for(int k=0;k<n;k++) ans.a[i][j]=ans.a[i][j]+t1.a[i][k]*t2.a[k][i]; ans.a[i][j]%=mod; } } return ans; } matrix Pow(matrix a,matrix b,int n) { while(n) { if(n&1) b=mul(b,a); n>>=1; a=mul(a,a); } return b; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); for(int i=0; i<n; i++) for(int j=0; j<n; j++) { scanf("%d",&init.a[i][j]); unit.a[i][j]=init.a[i][j]; } matrix res=Pow(init,unit,k-1); int ans=0; for(int i=0; i<n; i++) ans=(ans+res.a[i][i])%mod; printf("%d\n",ans%mod); } return 0; }
