从今天开始学习矩阵快速幂.jpg

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 #define ll long long 6 using namespace std; 7 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 8 char buf[1<<21],*p1=buf,*p2=buf; 9 inline ll read(){10     #define num ch-'0'11     char ch;bool flag=0;ll res;12     while(!isdigit(ch=getc()))13     (ch=='-')&&(flag=true);14     for(res=num;isdigit(ch=getc());res=res*10+num);15     (flag)&&(res=-res);16     #undef num17     return res;18 }19 const int N=105,mod=1e9+7;20 ll n,k;21 struct Matrix{22     int n;ll g[N][N];23     Matrix(){memset(g,0,sizeof(g));}24     inline Matrix operator *(Matrix b){25         Matrix ans;26         for(int i=1;i<=n;++i)27         for(int j=1;j<=n;++j)28         for(int k=1;k<=n;++k)29         (ans.g[i][j]+=g[i][k]*b.g[k][j])%=mod;30         ans.n=n;31         return ans;32     }33 }x,res;34 inline Matrix qpow(Matrix a,ll b){35     while(b){36         if(b&1) res=res*a;37         a=a*a,b>>=1;38     }39     return res;40 }41 inline void print(Matrix x){42     int n=x.n;43     for(int i=1;i<=n;++i){44         for(int j=1;j<=n;++j) printf("%d ",x.g[i][j]);45         putchar(10);46     }47 }48 int main(){49     //freopen("testdata.in","r",stdin);50     n=read(),k=read();51     x.n=n;52     for(int i=1;i<=n;++i)53     for(int j=1;j<=n;++j)54     x.g[i][j]=read();55     for(int i=1;i<=n;++i) res.g[i][i]=1;res.n=n;56     print(qpow(x,k));57     return 0;58 }