首页 > 代码库 > hdu 4965 Fast Matrix Calculation【矩阵快速幂模板】
hdu 4965 Fast Matrix Calculation【矩阵快速幂模板】
此题只是需要对某个矩阵进行变换相乘之类的,换一下两个矩阵相乘的顺序,利用矩阵快速幂求解即可。
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #define N 1010 using namespace std; const int mod=6; int** mul(int** A,int** B,int n,int m,int l)//A 为n*m的矩阵,B为m*l的矩阵 { int **t=new int*[n]; for(int i=0;i<n;i++) t[i]=new int[l]; for(int i=0;i<n;i++) for(int j=0;j<l;j++){ t[i][j]=0; for(int k=0;k<m;k++) t[i][j]=(t[i][j]+A[i][k]*B[k][j])%mod; } return t; } int** expo(int **p,int k,int n)//P为n*n的矩阵,k为计算k次幂 { if(k==1) return p; int **e=new int*[n]; for(int i=0;i<n;i++) e[i]=new int[n]; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) e[i][j] = (i == j); while(k) { if(k&1) e=mul(e,p,n,n,n); p=mul(p,p,n,n,n); k>>=1; } return e; } int main() { #ifndef ONLINE_JUDGE freopen("D:/in.txt","r",stdin); //freopen("D:/my.txt","w",stdout); #endif int NN,K; while(~scanf("%d%d",&NN,&K)&&(NN||K)) { int **a=new int*[NN]; for(int i=0;i<NN;i++) a[i]=new int[K]; int **b=new int*[K]; for(int i=0;i<NN;i++) b[i]=new int[NN]; int **c; for(int i=0;i<NN;i++) for(int j=0;j<K;j++) scanf("%d",&a[i][j]); for(int i=0;i<K;i++) for(int j=0;j<NN;j++) scanf("%d",&b[i][j]); c=mul(b,a,K,NN,K); int temp=NN*NN-1; c=expo(c,temp,K); c=mul(a,c,NN,K,K); c=mul(c,b,NN,K,NN); int ans=0; for(int i=0;i<NN;i++) for(int j=0;j<NN;j++) ans+=c[i][j]; printf("%d\n",ans); } return 0; }
hdu 4965 Fast Matrix Calculation【矩阵快速幂模板】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。