1113 矩阵快速幂

1113 矩阵快速幂

给出一个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<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
int n,m;
struct prog
{
    ll  a[102][102];
};
prog s,B;
prog matrixmul(prog a,prog b)
{
   prog c;
     for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
   {
       c.a[i][j]=0;
       for(int k=1;k<=n;k++)
            c.a[i][j]+=(a.a[i][k]*b.a[k][j])%mod;
         c.a[i][j]%=mod;
   }
      return c;
}
prog mul(prog s,int k)
{
     prog ans;
     for(int i=1;i<=n;++i)for(int j=1;j<=n;++j) ans.a[i][j]=(i==j)?1:0;
     while(k){
        if(k&1)
            ans=matrixmul(ans,s);
        k>>=1;
        s=matrixmul(s,s);
    }
      return ans;
}

int main(){
    scanf("%d%d",&n,&m);
    prog s;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            scanf("%I64d",&s.a[i][j]);
    }
    s=mul(s,m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            printf("%I64d",(s.a[i][j]+mod)%mod);
            if(j!=n) printf(" ");
        }
        printf("
");
    }
}