poj 3233 Matrix Power Series 矩阵快速幂
/*愧疚了，好久没写什么有意思的题了。这道基于二分的矩阵连乘，方法很经典。求幂二分，求和再二分。经典。求幂的时候，若奇数，A^n=A^(n/2)*A^(n/2)*A.偶数时 A^n=A^(n/2)*A^(n/2)。求和的时候，若为奇数，A^1+A^2+...+A^(2*m+1)=(A^1+...+A^m)+(A^1+...+A^m)*A^m*A,若为偶数 A^1+A^2+...+A^(2*m+1)=(A^1+...+A^m)+(A^1+...+A^m)*A^m。奇数的时候，构造0,1单位矩阵。对奇数进行特判。memcpy(a,b,sizeof(int)*N*N);切记memcpy的赋值范围。之前因为太小，答案一直错误。*/#include <stdio.h>#include <cstring>int n,m,k;const int N=31;int ans[N][N],A[N][N];void add(int a[][N],int b[][N]){ for(int i=0; i<n; i++) for(int j=0; j<n; j++) { a[i][j]+=b[i][j]; if(a[i][j]>=m) a[i][j]%=m; }}void mul(int a[][N],int b[][N]){ int tmp[N][N]; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { tmp[i][j]=0; for(int k=0; k<n; k++) { tmp[i][j]+=a[i][k]*b[k][j]; if(tmp[i][j]>=m) tmp[i][j]%=m; } } } memcpy(a,tmp,sizeof(tmp));}void pow(int a[][N],int b[][N],int x){ int tmp[N][N]; memcpy(tmp,b,sizeof(int)*N*N); for(int i=0; i<n; i++) for(int j=0; j<n; j++) { if(i==j) a[i][j]=1; else a[i][j]=0; } while(x) { if(x&1)//最后的结果存在数组a中，因为最后x比为1，符合条件，自己模拟一遍则易知. mul(a,tmp); mul(tmp,tmp); x>>=1; }}void mat_sum(int a[][N],int b[][N],int x){ int c[N][N],d[N][N]; if(x==0) { memset(a,0,sizeof(int)*N*N); return ; } if(x==1) { memcpy(a,b,sizeof(int)*N*N); return ; } mat_sum(a,b,x>>1); pow(c,b,x>>1); memcpy(d,a,sizeof(int)*N*N); mul(a,c); add(a,d); if(x&1) { mul(c,c); mul(c,b); add(a,c); }}int main(){ while(scanf("%d%d%d",&n,&k,&m)==3) { for(int i=0; i<n; i++) for(int j=0; j<n; j++) scanf("%d",&A[i][j]); mat_sum(ans,A,k); for(int i=0; i<n; i++) { printf("%d",ans[i][0]); for(int j=1; j<n; j++) { if(j<n-1) printf(" %d",ans[i][j]); else printf(" %d\n",ans[i][j]); } } } return 0;}