本文主要是介绍HDU - 4965 - Fast Matrix Calculation（矩阵快速幂），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://cn.vjudge.net/problem/HDU-4965
思路：正常的矩阵之后得到
的矩阵，在之后的矩阵乘法中就会爆掉，所以根据矩阵乘法结合律改变下形式：
。
是一个
的矩阵，这样就可以愉快的矩阵快速幂了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
const int MAXN = 6;
const int MOD = 6;
int n, k;
struct Matrix
{ll m[MAXN][MAXN];void init(int x){memset(m, 0, sizeof(m));for(int i = 0; i < MAXN; i++){m[i][i] = x;}}Matrix operator * (const Matrix &a) const{Matrix res;res.init(0);for(int i = 0; i < MAXN; i++)for(int j = 0; j < MAXN; j++)for(int k = 0; k < MAXN; k++)res.m[i][j] = (res.m[i][j] + (m[i][k] * a.m[k][j]) % MOD) % MOD;return res;}
};Matrix quickPow(Matrix x, ll p)
{Matrix res;res.init(1);x = x * res;while(p){if(p & 1) res = res * x;p >>= 1;x = x * x;}return res;
}
ll a[N][N], b[N][N], p[N][N], d[N][N];
Matrix c, x;
void init()
{c.init(0);memset(p, 0, sizeof(p));memset(d, 0, sizeof(d));for(int i = 0; i < n; i++)for(int j = 0; j < k; j++)scanf("%lld",&a[i][j]);for(int i = 0; i < k; i++)for(int j = 0; j < n; j++)scanf("%lld",&b[i][j]);for(int i = 0; i < k; i++)for(int j = 0; j < k; j++)for(int g = 0; g < n; g++)c.m[i][j] = c.m[i][j] + b[i][g] * a[g][j];x = quickPow(c, n * n - 1);for(int i = 0; i < n; i++)for(int j = 0; j < k; j++)for(int g = 0; g < k; g++)p[i][j] = p[i][j] + a[i][g] * x.m[g][j];for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)for(int g = 0; g < k; g++)d[i][j] = d[i][j] + p[i][g] * b[g][j];
}int main()
{while(~scanf("%d%d",&n,&k) && n+k){init();ll ans = 0;for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)ans += d[i][j] % MOD;printf("%lld\n",ans);}return 0;
}
这篇关于HDU - 4965 - Fast Matrix Calculation（矩阵快速幂）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
