P3390 【模板】矩阵快速幂

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const long long mod=1000000007;
 7 int n;
 8 long long k;
 9 struct matrix{
10     long long a[110][110];
11     matrix operator*(const matrix &b)const{
12         matrix ret;
13         for(int i=1;i<=n;i++)
14             for(int j=1;j<=n;j++){
15                 ret.a[i][j]=0;
16                 for(int k=1;k<=n;k++) ret.a[i][j]=(ret.a[i][j]+a[i][k]*b.a[k][j])%mod;
17             }
18         return ret;
19     }
20 }a;
21 matrix matrix_pow(matrix a,long long b){
22     matrix ret=a,tmp=a;
23     b--;
24     for(;b;b>>=1,tmp=tmp*tmp)//!!!
25         if(b&1) ret=ret*tmp;
26     return ret;
27 }
28 int main(){
29     scanf("%d%lld",&n,&k);
30     for(int i=1;i<=n;i++)
31         for(int j=1;j<=n;j++) scanf("%d",&a.a[i][j]);
32     a=matrix_pow(a,k);
33     for(int i=1;i<=n;i++){
34         for(int j=1;j<n;j++) printf("%d ",a.a[i][j]);
35         printf("%d\n",a.a[i][n]);
36     }
37     return 0;
38 }