首页 > 代码库 > HDU 4965 Fast Matrix Calculation(矩阵快速幂)
HDU 4965 Fast Matrix Calculation(矩阵快速幂)
HDU 4965 Fast Matrix Calculation
题目链接
矩阵相乘为AxBxAxB...乘nn次,可以变成Ax(BxAxBxA...)xB,中间乘nn - 1次,这样中间的矩阵一个只有6x6,就可以用矩阵快速幂搞了
代码:
#include <cstdio> #include <cstring> const int N = 1005; const int M = 10; int n, m; int A[N][M], B[M][N], C[M][M], CC[N][N]; int ans[M][M]; void tra() { memset(CC, 0, sizeof(CC)); for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { CC[i][j] = 0; for (int k = 0; k < m; k++) { CC[i][j] = (CC[i][j] + C[i][k] * C[k][j]) % 6; } } } for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) C[i][j] = CC[i][j]; } void mul() { for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { CC[i][j] = 0; for (int k = 0; k < m; k++) { CC[i][j] = (CC[i][j] + ans[i][k] * C[k][j]) % 6; } } } for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) ans[i][j] = CC[i][j]; } void pow_mod(int k) { memset(ans, 0, sizeof(ans)); for (int i = 0; i < m; i++) ans[i][i] = 1; while (k) { if (k&1) mul(); tra(); k >>= 1; } } void init() { for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &A[i][j]); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) scanf("%d", &B[i][j]); } int solve() { for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { C[i][j] = 0; for (int k = 0; k < n; k++) { C[i][j] = (C[i][j] + B[i][k] * A[k][j]) % 6; } } } pow_mod(n * n - 1); for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { C[i][j] = ans[i][j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { CC[i][j] = 0; for (int k = 0; k < m; k++) { CC[i][j] = (CC[i][j] + A[i][k] * C[k][j]) % 6; } } } for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) A[i][j] = CC[i][j]; int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int sum = 0; for (int k = 0; k < m; k++) { sum = (sum + A[i][k] * B[k][j]) % 6; } ans += sum; } } return ans; } int main() { while (~scanf("%d%d", &n, &m) && n || m) { init(); printf("%d\n", solve()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。