从今天开始学习矩阵快速幂.jpg
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 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 num 17 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 }