矩阵快速幂 51Nod - 1113 [矩阵快速幂裸题]

基准时间限制：3 秒空间限制：131072 KB 分值: 40 难度：4级算法题

给出一个N * N的矩阵，其中的元素均为正整数。求这个矩阵的M次方。由于M次方的计算结果太大，只需要输出每个元素Mod (10^9 + 7）的结果。

Input

第1行：2个数N和M，中间用空格分隔。N为矩阵的大小，M为M次方。(2 <= N <= 100, 1 <= M <= 10^9)
第2 - N + 1行：每行N个数，对应N * N矩阵中的1行。(0 <= N[i] <= 10^9)

Output

共N行，每行N个数，对应M次方Mod (10^9 + 7)的结果。

Input示例

2 3
1 1
1 1

Output示例

4 4
4 4

相关问题

矩阵快速幂裸题:

#include <stdio.h>
#include <iostream>
#include <string.h>
#pragma comment(linker, "/STACK:102400000,102400000")
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define bug cout << "bug" << endl


using namespace std;
typedef long long ll;

const int MAX_N=100+3;
int n,m;

void multi(ll a[MAX_N][MAX_N],ll b[MAX_N][MAX_N]){
    ll temp[MAX_N][MAX_N];
    memset(temp,0,sizeof(temp));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                temp[i][j]+=a[i][k]*b[k][j]%MOD;
                temp[i][j]%=MOD;
            }
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)   a[i][j]=temp[i][j];
}

void pow_matrix(ll a[MAX_N][MAX_N],int m){
    ll ans[MAX_N][MAX_N];
    memset(ans,0,sizeof(ans));
    for(int i=1;i<=n;i++)   ans[i][i]=1;
    while(m){
        if(m&1) multi(ans,a);
        multi(a,a);
        m>>=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(j==1)    printf("%lld",ans[i][j]);
            else    printf(" %lld",ans[i][j]);
        }
        printf("\n");
    }
}

int main(void){
    cin >> n >> m;
    ll a[MAX_N][MAX_N];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)   scanf("%lld",&a[i][j]);
    pow_matrix(a,m);
    return 0;
}
/*

*/