矩阵快速幂

admin

1. 
   
2. #include<iostream>
   
3. #include<cstring>
   
4. #define mod 1000000007
   
5. #define ll long long
   
6. using namespace std;
   
7. struct Mat{
   
8.     ll m[101][101];
   
9. };
   
10. Mat a,e;//a是输入的矩阵，e是单位矩阵
    
11. ll n,p;
    
12. Mat Mul(Mat x,Mat y) //矩阵乘
    
13. {
    
14.     Mat c;
    
15.     for(int i=1;i<=n;i++)
    
16.       for(int j=1;j<=n;j++)
    
17.         c.m[i][j]=0;
    
18.     for(int i=1;i<=n;i++)
    
19.       for(int j=1;j<=n;j++)
    
20.         for(int k=1;k<=n;k++)
    
21.           c.m[i][j]=c.m[i][j]%mod+x.m[i][k]*y.m[k][j]%mod;
    
22.     return c;
    
23. }
    
24. Mat pow(Mat x,ll y) //矩阵快速幂
    
25. {
    
26.     Mat ans=e;
    
27.     while(y)
    
28.     {
    
29.         if(y&1)
    
30.          ans=Mul(ans,x);  
    
31.         x=Mul(x,x);
    
32.         y>>=1;
    
33.     }
    
34.     return ans;
    
35. }
    
36. 
    
37. int main()
    
38. {
    
39.    
    
40.     cin>>n>>p;
    
41.     for(int i=1;i<=n;i++)
    
42.       for(int j=1;j<=n;j++)
    
43.         cin>>a.m[i][j];
    
44.         
    
45.     for(int i=1;i<=n;i++)
    
46.         e.m[i][i]=1;   
    
47.     Mat ans=pow(a,p);
    
48.    
    
49.     for(int i=1;i<=n;i++)
    
50.     {
    
51.         for(int j=1;j<=n;j++)
    
52.           cout<<ans.m[i][j]%mod<<" ";
    
53.         cout<<endl;
    
54.     }  
    
55.     return 0;
    
56. }

复制代码