首页 > 代码库 > HDU 4965 Fast Matrix Calculation 【矩阵】
HDU 4965 Fast Matrix Calculation 【矩阵】
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4965
题目大意:给你一个N*K的矩阵A以及一个K*N的矩阵B (4 <= N <= 1000)以及 (2 <=K <= 6),然后接下来四步:
- 算一个新的矩阵C=A*B
- 算M=C^ (N*N)
- 对于M中的每个元素%6
- 将M中每个元素加起来,算出和。
也就是求出A*B * A*B * A*B * A*B * A*B *……* A*B 但是A*B形成的矩阵是N*N,而N大小有可能是1000,所以时间复杂度很高,即使是快速幂也过不了
现在有一个转换:A* B*A * B*A * B*A *……* B*A * B*A * B 现在就转换成了K*K的矩阵,K最大是6,这样时间复杂度就省下来了,注意算出pow(B*A,N*N-1)之后,要对结果左乘一个A,右乘一个B,就可以得出答案了。
竟然最后没有做这个题目(时间没有合理分配,卡题了= =).......
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int MAXN = 1017; #define M 6 struct Matrix { int v[6][6]; }; int n, m, k;//矩阵大小 int A[MAXN][6],B[6][MAXN],C[MAXN][6],D[MAXN][MAXN]; Matrix T, E; Matrix mtMul(Matrix A, Matrix B) // 求矩阵 A * B { int i, j, k; Matrix C; for(i = 0; i < m; i ++) for(j = 0; j < m; j ++) { C.v[i][j] = 0; for(k = 0; k < m; k ++) C.v[i][j] = (A.v[i][k] * B.v[k][j] + C.v[i][j]) % M; } return C; } Matrix mtPow(Matrix origin,int k) //矩阵快速幂 { int i; Matrix res; memset(res.v,0,sizeof(res.v)); for(i=0;i<m;i++) res.v[i][i]=1; while(k) { if(k&1) res=mtMul(res,origin); origin=mtMul(origin,origin); k>>=1; } return res; } void out(Matrix A) { for(int i=0;i<m;i++) { for(int j=0;j<m;j++) cout<<A.v[i][j]<<" "; cout<<endl; } cout<<endl; } void init() { memset(T.v,0,sizeof(T.v)); memset(C,0,sizeof(C)); memset(D,0,sizeof(D)); } int main() { while(~scanf("%d%d",&n,&m)) { if(n == 0 && m == 0) break; init(); for(int i = 0; i < n; i++)//矩阵A的大小n*m { for(int j = 0; j < m; j++) { scanf("%d",&A[i][j]); } } for(int i = 0; i < m; i++)//矩阵B的大小m*n { for(int j = 0; j < n; j++) { scanf("%d",&B[i][j]); } } for(int i = 0; i < m; i++)//矩阵T = B*A大小为m*m { for(int j = 0; j < m; j++) { for(int k = 0; k < n; k++) { T.v[i][j] += B[i][k]*A[k][j]; T.v[i][j] %= M; } } } //out(T); E = mtPow(T,n*n-1); for(int i = 0; i < n; i++)//矩阵C = A*E 大小为n*m { for(int j = 0; j < m; j++) { for(int k = 0; k < m; k++) { C[i][j] += A[i][k]*E.v[k][j]; C[i][j] %= M; } } } int ans = 0; for(int i = 0; i < n; i++)//矩阵D = C*B大小为n*n { for(int j = 0; j < n; j++) { for(int k = 0; k < m; k++) { D[i][j] += C[i][k]*B[k][j]; } ans += D[i][j]%M; } } printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。