首页 > 代码库 > HDU 4965 Fast Matrix Calculation 矩阵快速幂
HDU 4965 Fast Matrix Calculation 矩阵快速幂
乘法分配率
A^(N*N) * B^(N*N) = A*B*A*B*A*B*A··· = A*(B*A)*(B*A)···
然后里面的结果就是6*6的格子,然后快速幂一下。
#include <cstdio> #include <cstring> #include <vector> using namespace std; typedef long long ll; typedef vector<ll> vec; typedef vector<vec> mat; const int MAX_N = 1007; const int MAX_K = 7; const int MOD = 6; mat mul(mat &A, mat &B) { mat C(A.size(), vec(B[0].size())); for (int i = 0; i < A.size(); ++i) { for (int k = 0; k < B.size(); ++k) { for (int j = 0; j < B[0].size(); ++j) { C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD; } } } return C; } mat Pow(mat A, ll n) { mat B(A.size(), vec(A.size())); for (int i = 0; i < A.size(); ++i) { B[i][i] = 1; } while (n > 0) { if (n & 1) B = mul(B, A); A = mul(A, A); n >>= 1; } return B; } inline bool rd(ll &n){ ll x = 0, tmp = 1; char c = getchar(); while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar(); if(c == EOF) return false; if(c == '-') c = getchar(), tmp = -1; while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar(); n = x*tmp; return true; } int main() { int n, k; while (2 == scanf("%d%d", &n, &k)) { if (0 == n && k == 0) break; mat A(n, vec(k)), B(k, vec(n)); for (int i = 0; i < n; ++i) { for (int j = 0; j < k; ++j) { rd(A[i][j]); } } for (int i = 0; i < k; ++i) { for (int j = 0; j < n; ++j) { rd(B[i][j]); } } long long nn = n * n; if (nn == 1) { int ans = 0; for (int i = 0; i < k; ++i) { ans = (ans + A[0][i] * B[i][0]) % MOD; } printf("%d\n", ans); } else { mat C(k, vec(k)); for (int i = 0; i < k; ++i) { for (int j = 0; j < k; ++j) { for (int l = 0; l < n; ++l) { C[i][j] = C[i][j] + B[i][l] * A[l][j]; } } } C = Pow(C, nn - 1); mat D(n, vec(n)); for (int i = 0; i < n; ++i) { for (int j = 0; j < k; ++j) { for (int l = 0; l < k; ++l) { D[i][j] = (D[i][j] + A[i][l] * C[l][j]) % MOD; } } } mat E(n, vec(n)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int l = 0; l < k; ++l) { E[i][j] = (E[i][j] + D[i][l] * B[l][j]) % MOD; } } } long long sum = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { sum += E[i][j]; } } printf("%I64d\n", sum); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。