poj 3323 Matrix Power Series (矩阵乘法 非递归形式)

为了搞自动机+矩阵的题目,特来学习矩阵快速幂..........非递归形式的求Sum(A+A^2+...+A^k)不是很懂,继续弄懂................不过代码简洁明了很多,poj 3323 Matrix Power Series (矩阵乘法 非递归形式)poj 3323 Matrix Power Series (矩阵乘法 非递归形式)亮神很给力

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 100005
#define INF 0x7FFFFFFF
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define LL long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define L(x) x << 1
#define R(x) x << 1 | 1
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std;
int n,k,m;
__int64 a[33][33];
__int64 x[66][66],y[66][66]; void multi(__int64 x[66][66],__int64 y[66][66]) { // A * B
__int64 p[66][66];
memset(p,0,sizeof(p));
int N = n * 2;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
for(int k=0; k<N; k++) {
p[i][j] = (p[i][j] + (x[i][k] * y[k][j]) % m) % m;
}
}
}
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
x[i][j] = p[i][j];
}
}
} void quickmul(int p) { //将矩阵扩大成2n * 2n
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
y[i+n][j+n] = a[i][j];
x[i][j+n] = a[i][j];
}
}
for(int i=0; i<n; i++) y[i][i] = 1;
for(int i=0; i<n; i++) y[i+n][i] = 1;
while(p) { //A ^ p
if(p & 1) {
multi(x,y);
}
multi(y,y);
p = p >> 1;
}
} int main() {
scanf("%d%d%d",&n,&k,&m);
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
scanf("%d",&a[i][j]);
a[i][j] %= m;
}
}
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
quickmul(k);
for(int i=0; i<n; i++) {
printf("%d",x[i][0]);
for(int j=1; j<n; j++) printf(" %d",x[i][j]);
puts("");
}
return 0;
}
上一篇:全功能Python测试框架:pytest


下一篇:【转】Mapreduce部署与第三方依赖包管理