HDU 4965 Fast Matrix Calculation（矩阵结合律）

题目链接：
HDU 4965 Fast Matrix Calculation
题意：
分别给出一个$n*k$和$k*n$的矩阵A和B，两矩阵相乘得到矩阵C，求出矩阵C的$n*n$次幂矩阵M，
输出将矩阵M中每个元素%6后的元素和。其中n<1000,2<=k<=6.
分析：
因为n实在太大了，开不了1000*1000的矩阵，但是可以利用矩阵相乘的结合律，
$A*B*A*B*A*B*A..*A*B$，可以将先计算中间的$B*A*B*A*..*A$，这样B和A相乘得到的是一个6*6(最多)矩阵,
将这个矩阵用快速幂计算(n*n-1)次幂，在乘上一开始的A和最后的B即可。

//5512K 172MS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1010;int n,k,res;
int A[maxn][10],B[10][maxn],M[maxn][10],MM[maxn][maxn];struct Matrix{int row,col;int data[10][10];
};inline Matrix mul(Matrix a,Matrix b)
{Matrix ans;ans.row=a.row,ans.col=b.col;memset(ans.data,0,sizeof(ans.data));for(int i=1;i<=ans.row;i++){for(int j=1;j<=ans.col;j++){for(int p=1;p<=a.col;p++){ans.data[i][j]+=a.data[i][p]*b.data[p][j]%6;ans.data[i][j]%=6;}}}return ans;
}inline Matrix quick_power(Matrix a,int m)
{Matrix ans,tmp=a;ans.row=ans.col=a.row;memset(ans.data,0,sizeof(ans.data));for(int i=1;i<=ans.row;i++) ans.data[i][i]=1;while(m){if(m&1) ans=mul(ans,tmp);tmp=mul(tmp,tmp);m>>=1;}return ans;
}int main()
{freopen("Ein.txt","r",stdin);while(~scanf("%d%d",&n,&k)&&(n||k)){for(int i=1;i<=n;i++){for(int j=1;j<=k;j++){scanf("%d",&A[i][j]);}}for(int i=1;i<=k;i++){for(int j=1;j<=n;j++){scanf("%d",&B[i][j]);}}Matrix ans;ans.row=ans.col=k;memset(ans.data,0,sizeof(ans.data));for(int i=1;i<=k;i++){for(int j=1;j<=k;j++){for(int p=1;p<=n;p++){ans.data[i][j]+=B[i][p]*A[p][j]%6;ans.data[i][j]%=6;}}}ans=quick_power(ans,n*n-1);//中间部分矩阵乘积memset(M,0,sizeof(M));for(int i=1;i<=n;i++){
   //A*中间矩阵for(int j=1;j<=k;j++){for(int p=1;p<=k;p++){M[i][j]+=A[i][p]*ans.data[p][j]%6;M[i][j]%=6;}}}memset(MM,0,sizeof(MM));for(int i=1;i<=n;i++){
   //再乘以最后的一个B数组for(int j=1;j<=n;j++){for(int p=1;p<=k;p++){MM[i][j]+=M[i][p]*B[p][j]%6;MM[i][j]%=6;}}}res=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){res+=MM[i][j]%6;}}printf("%d\n",res);}return 0;
}