poj 3323 Matrix Power Series (矩阵乘法 非递归形式)
为了搞自动机+矩阵的题目,特来学习矩阵快速幂..........非递归形式的求Sum(A+A^2+...+A^k)不是很懂,继续弄懂................不过代码简洁明了很多,亮神很给力#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; }
补充:软件开发 , C++ ,