要求求解Tr(a^k)%9937,注意不要到最後才余，在每處理完一次的時候就余一下（矩陣性質：矩陣中的每個數同時除以/乘以相同整數，矩陣的性質均不變（包括矩陣的跡、矩陣的秩、矩陣的最簡階梯行列式等等）否則數字過大會溢出。 [cpp] #include <iostream> #include <cmath> #include <cstring> using namespace std; class Mat { public: int mat[15][15]; }; int n; //維度,即矩陣A的行數 int MOD=9973;//好多問題要求給出取余之後的數字 Mat E; void initE() { for(int i=0;i<15;i++) E.mat[i][i]=1; } Mat operator*(Mat a,Mat b) { int i,j,k; Mat c; for (i=0;i<n;i++) { for (j=0;j<n;j++) { c.mat[i][j] = 0; for (k=0;k<n;k++) { c.mat[i][j]+=(a.mat[i][k]*b.mat[k][j]); } c.mat[i][j]%=MOD; } } return c; } Mat operator+(Mat a,Mat b) { Mat c; int i,j; for (i=0;i<n;i++) { for (j=0;j<n;j++) c.mat[i][j] = a.mat[i][j]+b.mat[i][j]; c.mat[i][j]%=9973; } return c; } Mat operator^(Mat a,int x) { Mat p = E,q = a; while (x>=1) { if(x%2==1) p = p*q; x/=2; q = q*q; } return p; } Mat solve(Mat a,int p) { if(p==1) return a; else if(p&1) return (a^p)+solve(a,p-1); else return ((a^(p>>1))+E)*solve(a,p>>1); } int main() { int testcase; cin>>testcase; Mat at,bt; int res; int kp; while(testcase--) { res=0; initE(); memset(at.mat,0,sizeof(at.mat)); memset(bt.mat,0,sizeof(bt.mat)); cin>>n>>kp; for(int i=0;i<n;i++) { www.2cto.com for(int j=0;j<n;j++) { cin>>at.mat[i][j]; } } bt=at^kp; for(int i=0;i<n;i++) { res+=bt.mat[i][i]; } cout<<res%9973<<endl; } return 0; }
