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;  
}