本文主要是介绍HDU 4965 Fast Matrix Calculation，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
矩阵快速幂 肯定是这个没问题了。
一上来我就贴了模板。 可是一看矩阵最大是 1000*1000的。 结构体内 数组开不开这么大啊。 明显模板不合适了。。
然后看了看上面的条件。 发现（AB）^(N*N) 如果N 为2 的话 就是ABABABAB 结合律 A（BA）（BA）（BA）B
这样就是 BA 的快速幂 结果左乘 A 右乘 B。 并且 BA 是 10*10 的， 就可以用矩阵快速幂了。
还有矩阵求和的公式。 第一层循环是 前面矩阵的行数 第二层循环是 后面矩阵的 行数 第三层循环是前面矩阵的列数。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MAXN 1000+10
#define INF 1<<30
#define mod 6
int N,M;
struct Matrix
{int n,m;int a[20][20];void clear(int x=0,int y=0){n=x;m=y;memset(a,0,sizeof(a));}
};
Matrix cc(Matrix a,Matrix b)
{Matrix tmp;tmp.clear(M,M);for(int i = 0; i < M; ++i)for(int j = 0; j < M; ++j)for(int k = 0; k < M; ++k){tmp.a[i][j]+=a.a[i][k]*b.a[k][j];tmp.a[i][j]%=mod;}return tmp;
}Matrix _Pow(Matrix mat,int n)
{Matrix res;res.n = 10,res.m = 10;for(int i = 0; i < 10 ;i++)for(int j = 0; j < 10; j++){if(i == j)res.a[i][i] = 1;elseres.a[i][j] = 0;}while(n){if(n&1) res=cc(res,mat);mat=cc(mat,mat);n=n>>1;}return res;
}
Matrix BA;
int A[MAXN][MAXN],B[MAXN][MAXN],C[MAXN][MAXN],L[MAXN][MAXN],LL[MAXN][MAXN];
int main (){while(scanf("%d%d",&N,&M) != EOF){memset(LL,0,sizeof(LL));memset(L,0,sizeof(L));memset(A,0,sizeof(A));memset(B,0,sizeof(B));memset(C,0,sizeof(C));// 1 是 前的行 2 是后的行 3是 前的列if(N == 0 && M == 0)break;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]);}}for(int i=0; i< M; ++i){for(int j=0; j < M; ++j)for(int k=0; k < N; ++k){C[i][j] += B[i][k]*A[k][j];C[i][j] %= mod;BA.a[i][j] = C[i][j];}}Matrix M_;M_ = _Pow(BA,N*N-1);for(int i = 0; i< N; ++i){for(int j = 0; j < M; ++j)for(int k = 0; k < M; ++k){L[i][j] += A[i][k]*M_.a[k][j];L[i][j] %= mod;}}for(int i = 0; i< N; ++i){for(int j = 0; j < N; ++j)for(int k = 0; k < M; ++k){LL[i][j] += L[i][k]*B[k][j];LL[i][j] %= mod;}}int sum = 0;for(int i = 0; i < N; i++){for(int j = 0; j < N; j++){sum += LL[i][j];}}printf("%d\n",sum);}return 0;
}这篇关于HDU 4965 Fast Matrix Calculation的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
