洛谷P3390 【模板】矩阵快速幂

 1 /*by SilverN*/
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 #define LL long long
 8 using namespace std;
 9 const int mod=1e9+7;
10 const int mxn=105;
11 int read(){
12     int x=0,f=1;char ch=getchar();
13     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
14     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
15     return x*f;
16 }
17 int n;
18 struct matrix{
19     int s[mxn][mxn];
20     matrix(){memset(s,0,sizeof s);}
21 };
22 matrix operator * (const matrix a,const matrix b){
23     matrix c;
24     for(int i=1;i<=n;i++)
25      for(int j=1;j<=n;j++)
26       for(int k=1;k<=n;k++)
27           c.s[i][j]=((LL)c.s[i][j]+(LL)a.s[i][k]*b.s[k][j])%mod;
28     return c;
29 }
30 LL k;
31 matrix a;
32 int main(){
33     int i,j;
34     scanf("%d%lld",&n,&k);
35     for(i=1;i<=n;i++)
36      for(j=1;j<=n;j++)
37       a.s[i][j]=read();
38     matrix ans=a;
39     k--;
40     while(k){
41         if(k&1)ans=ans*a;
42         k>>=1;
43         a=a*a;
44     }
45     for(i=1;i<=n;i++){
46         for(j=1;j<=n;j++){
47             printf("%d ",ans.s[i][j]);
48         }
49         printf("
");
50     }
51     return 0;
52 }