首页 > 代码库 > HDU_4965 Fast Matrix Calculation 2014多校9 矩阵快速幂+机智的矩阵结合律
HDU_4965 Fast Matrix Calculation 2014多校9 矩阵快速幂+机智的矩阵结合律
一开始看这个题目以为是个裸的矩阵快速幂的题目，
后来发现会超时，超就超在 M = C^(N*N). 这个操作，而C本身是个N*N的矩阵，N最大为1000。
但是这里有个巧妙的地方就是 C的来源其实 是= A*B， A为一个N*k的矩阵，B为一个k*N的矩阵，k最大为10，突破的就在这里，矩阵的结合律要用起来
即我先不把A*B结合，我先把B*A结合，这样M不是要C^N*N吗，就先把里面N*N个（B*A）算出来，就10*10再乘以logN*N即可。最后再两端乘一下A和B即可
也挺机智的，我没想到结合律。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define LL __int64using namespace std;LL matA[1010][10],matB[10][1010];LL matC[1010][10];LL MM[1010][1010];int n,k;struct Mat{ LL mat[10][10];}E;Mat operator *(Mat a,Mat b){ Mat c; for (int i=0;i<k;i++) for (int j=0;j<k;j++){ c.mat[i][j]=0; for (int w=0;w<k;w++){ c.mat[i][j]+=a.mat[i][w]*b.mat[w][j]; c.mat[i][j]%=6; } } return c;}Mat operator ^(Mat a,int x){ Mat c=E; for (int i=x;i;i>>=1){ if (i&1){ c=c*a; } a=a*a; } return c;}int main(){ memset(E.mat,0,sizeof E.mat); for (int i=0;i<10;i++) E.mat[i][i]=1; while (scanf("%d%d",&n,&k)!=EOF) { if (n==0 && k==0) break; for (int i=0;i<n;i++) for (int j=0;j<k;j++) scanf("%I64d",&matA[i][j]); for (int i=0;i<k;i++) for (int j=0;j<n;j++) scanf("%I64d",&matB[i][j]); Mat a; for (int i=0;i<k;i++) for (int j=0;j<k;j++){ a.mat[i][j]=0; for (int w=0;w<n;w++){ a.mat[i][j]+=matB[i][w]*matA[w][j]; } //cout<<i<<" aaa "<<j<<" "<<a.mat[i][j]<<endl; } Mat M=a^(n*n-1); for (int i=0;i<n;i++) for (int j=0;j<k;j++){ matC[i][j]=0; for (int w=0;w<k;w++) matC[i][j]+=matA[i][w]*M.mat[w][j]; // cout<<matC[i][j]<<" Matc "<<endl; } int ans=0; for (int i=0;i<n;i++) for (int j=0;j<n;j++){ MM[i][j]=0; for (int w=0;w<k;w++){ MM[i][j]+=matC[i][w]*matB[w][j]; } // cout<<MM[i][j]<<" qwe "<<endl; ans+=MM[i][j]%6; } printf("%d\n",ans); } return 0;}
HDU_4965 Fast Matrix Calculation 2014多校9 矩阵快速幂+机智的矩阵结合律
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。