题意：给出n*k的矩阵A和k*n的B，求(AB)^(n*n)结果矩阵中各元素模6 之和。（n<=1000,k<=6)
思路：A*B的矩阵是n*n（1000*1000）的矩阵，再快速幂肯定超时，用乘法结合律A^(N*N) * B^(N*N) = A*B*A*B*A*B*A··· = A*(B*A)*(B*A)···，，以B*A的6*6的矩阵再快速幂即可
//62MS 1716K 1968 B C++ #include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;struct mat{int a[10][10];int r,c;mat(){memset(a,0,sizeof(a));r=c=0;}void mem(){memset(a,0,sizeof(a));}};int n,l;mat I;int A[1010][10],B[10][1010];mat mul(mat m1,mat m2){mat ans;for(int i=1;i<=l;i++)for(int j=1;j<=l;j++)if(m1.a[i][j])for(int k=1;k<=l;k++)ans.a[i][k]=(ans.a[i][k]+m1.a[i][j]*m2.a[j][k])%6;return ans;}mat quickmul(mat m,int k){mat ans;for(int i=1;i<=l;i++) ans.a[i][i]=1;while(k){if(k&1) ans=mul(ans,m);m=mul(m,m);k>>=1;}return ans;}int Ans[1010][10];void ini(){memset(Ans,0,sizeof(Ans));I.mem();}int main(){while(scanf("%d%d",&n,&l),(n||l)){ini();for(int i=1;i<=n;i++)for(int j=1;j<=l;j++)scanf("%d",&A[i][j]);for(int i=1;i<=l;i++)for(int j=1;j<=n;j++)scanf("%d",&B[i][j]);for(int i=1;i<=l;i++) //计算B*A矩阵for(int j=1;j<=n;j++)if(B[i][j])for(int k=1;k<=l;k++)I.a[i][k]=(I.a[i][k]+B[i][j]*A[j][k])%6;mat tmp=quickmul(I,n*n-1);for(int i=1;i<=n;i++) //A*(B*A)^(n-1)for(int j=1;j<=l;j++)if(A[i][j])for(int k=1;k<=l;k++)Ans[i][k]=(Ans[i][k]+A[i][j]*tmp.a[j][k])%6;int ans=0;for(int i=1;i<=n;i++) //A*(B*A)^(n-1)^B=(A*B)^nfor(int j=1;j<=n;j++){int tmp=0;for(int k=1;k<=l;k++){tmp+=Ans[i][k]*B[k][j];}ans+=(tmp%6);}printf("%d\n",ans);}return 0;}
生命不是一场赛跑，而是一次旅行。比赛在乎终点，而旅行在乎沿途风景。
