华师一附中OI组

标题: 矩阵快速幂 [打印本页]
作者: admin    时间: 2021-7-6 16:57
标题: 矩阵快速幂

  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. }

  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. }
复制代码






欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2