构造矩阵
1 #include <cstdio> 2 const int MAXN=100; 3 struct Matrix{int a[MAXN][MAXN];}O,I;int N; 4 void OI(int n){N=n;for(int i=0;i<MAXN;i++)for(int j=0;j<MAXN;j++)O.a[i][j]=0,I.a[i][j]=(i==j);} 5 Matrix Mul(Matrix A,Matrix B,int MOD){ 6 Matrix C=O; 7 for(int i=1;i<=N;i++) 8 for(int j=1;j<=N;j++) 9 for(int k=1;k<=N;k++) 10 C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%MOD; 11 return C; 12 } 13 Matrix Pow(Matrix A,int n,int MOD){ 14 Matrix B=I; 15 for(;n;A=Mul(A,A,MOD),n>>=1)if(n&1)B=Mul(B,A,MOD); 16 return B; 17 } 18 Matrix B(int n){ 19 Matrix B=O; 20 for(int i=1;i<=n;i++) 21 for(int j=1;j<=n;j++) 22 scanf("%d",&B.a[i][j]); 23 for(int i=1;i<=n;i++) 24 B.a[i+n][i+n]=B.a[i][i+n]=1; 25 return B; 26 } 27 int main(){ 28 int n,m,k;scanf("%d%d%d",&n,&m,&k),OI(2*n); 29 Matrix A=Pow(B(n),m+1,k); 30 for(int i=1;i<=n;i++){ 31 for(int j=1;j<=n;j++) 32 printf("%d ",(A.a[i][j+n]-(i==j)+k)%k); 33 puts(""); 34 } 35 return 0; 36 }