矩阵快速幂

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int n,f;
 5 struct Matrix{
 6     long long v[105][105];
 7 }A,Ans;
 8 Matrix operator *(Matrix A,Matrix B){
 9     Matrix C;
10     memset(C.v,0,sizeof(C.v));
11     for(int i=1;i<=n;i++){
12         for(int j=1;j<=n;j++){
13             for(int k=1;k<=n;k++){
14                 C.v[i][j]+=(A.v[i][k]%1000000007)*(B.v[k][j]%1000000007);
15                 C.v[i][j]%=1000000007;
16             }
17         }
18     }
19     return C;
20 }
21 Matrix fastpower(Matrix A,long long n){
22     Matrix Mid=A;
23     while(n){
24         if(n%2)
25             Mid=A*Mid;
26         A=A*A;
27         n>>=1;
28     }
29     return Mid;
30 }
31 int main(){
32     scanf("%d%d",&n,&f);
33     for(int i=1;i<=n;i++){
34         for(int j=1;j<=n;j++){
35             scanf("%lld",&A.v[i][j]);
36         }
37     }
38     Ans=fastpower(A,f-1);
39     for(int i=1;i<=n;i++){
40         for(int j=1;j<=n;j++){
41             printf("%lld ",Ans.v[i][j]);
42         }
43         printf("
");
44     }
45     return 0;
46 }