首页 > 代码库 > HDU 4965 Fast Matrix Calculation 矩阵乘法 乘法结合律

HDU 4965 Fast Matrix Calculation 矩阵乘法 乘法结合律

一种奇葩的写法,纪念一下当时的RE。

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cstdlib>  5 #include <cmath>  6 #include <algorithm>  7 #include <string>  8 #include <queue>  9 #include <stack> 10 #include <vector> 11 #include <map> 12 #include <set> 13 #include <functional> 14 #include <cctype> 15 #include <time.h> 16  17 using namespace std; 18  19 const int INF = 1<<30; 20 const int MAXN = 1005; 21  22 struct Matrix { 23     int a[MAXN][MAXN]; 24     int col, row; 25 }; 26  27 Matrix tMu; 28  29 void multiplication(const Matrix &x, const Matrix &y) { 30     tMu.row= x.row; tMu.col = y.col; 31     for (int i = 0; i < tMu.row; i++) 32         for (int j = 0; j < tMu.row; j++) { 33             tMu.a[i][j] = 0; 34             for (int k = 0; k < x.col; k++) 35                 tMu.a[i][j] = (tMu.a[i][j]+x.a[i][k]*y.a[k][j])%6; 36         } 37 } 38  39 Matrix a, b, ONE; 40 Matrix t; 41 Matrix tmp, res; 42  43 int n, k; 44  45 void pow(const Matrix &x, int d) { 46     res = ONE; res.col = res.row = x.col; 47     tmp = x; 48     while (d>0) { 49         if (d&1) { 50             multiplication(res, tmp); 51             res = tMu; 52         } 53         multiplication(tmp, tmp); 54         tmp = tMu; 55         d >>= 1; 56     } 57 } 58  59 void solve() { 60     multiplication(b, a); 61     t = tMu; 62     pow(t, n*n-1); 63     t = res; 64     multiplication(a, t); 65     t = tMu; 66     multiplication(t, b); 67     t = tMu; 68     int ans = 0; 69     for (int i = 0; i < n; i++) { 70         for (int j = 0; j < n; j++) 71             ans += t.a[i][j]; 72     } 73     printf("%d\n", ans); 74 } 75  76 int main() { 77     #ifdef Phantom01 78         freopen("HDU4965.txt", "r", stdin); 79     #endif //Phantom01 80  81     for (int i = 0; i < MAXN; i++) { 82         for (int j = 0; j < MAXN; j++) 83             ONE.a[i][j] = 0; 84         ONE.a[i][i] = 1; 85     } 86  87     while (scanf("%d%d", &n, &k)!=EOF && !(n==0&&k==0)) { 88         a.row = b.col = n; 89         a.col = b.row = k; 90         for (int i = 0; i < n; i++) 91             for (int j = 0; j < k; j++) 92                 scanf("%d", &a.a[i][j]); 93         for (int i = 0; i < k; i++) 94             for (int j = 0; j < n; j++) 95                 scanf("%d", &b.a[i][j]); 96         solve(); 97     } 98  99     return 0;100 }
View Code

 

HDU 4965 Fast Matrix Calculation 矩阵乘法 乘法结合律