矩阵快速幂-白红宇

矩阵快速幂

阅读量：6113 次

发布时间：2019-06-21

本文共 1740 字，大约阅读时间需要 5 分钟。

#include
      
        #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #define maxint (2147483647)#define l(a) ((a)<<1)#define r(a) ((a)<<1|1)#define b(a) (2<<(a))#define rep(i,a,b) for(int i=a;i<=(b);i++)#define clr(a) memset(a,0,sizeof(a))typedef long long ll;using namespace std;int readint(){ int t=0,f=1;char c=getchar(); while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); } while(isdigit(c)){ t=(t<<3)+(t<<1)+c-'0'; c=getchar(); } return t*f;}ll readll(){ ll t=0ll,f=1ll;char c=getchar(); while(!isdigit(c)){ if(c=='-') f=-1ll; c=getchar(); } while(isdigit(c)){ t=(t<<3ll)+(t<<1ll)+ll(c-'0'); c=getchar(); } return t*f;}const int maxn=109;const ll mod=1e9+7;int n;ll k;struct matrix{ int a,b; ll x[maxn][maxn]; inline matrix operator*(const matrix A)const{ matrix B;B.clear();B.a=a;B.b=A.b; rep(i,1,a){ rep(j,1,A.b){ rep(k,1,b) B.x[i][j]=(B.x[i][j]+x[i][k]*A.x[k][j])%mod; } } return B; } inline matrix operator^(const ll k)const{ ll t=k;matrix A,B; A.a=B.a=a;A.b=B.b=b; rep(i,1,a) rep(j,1,b) A.x[i][j]=x[i][j]; B.clear(); rep(i,1,a) B.x[i][i]=1; while(t){ if(t&1) B=B*A; A=A*A;t>>=1ll; } return B; } inline void clear(){ rep(i,1,a) rep(j,1,b) x[i][j]=0; } inline void in(int _a,int _b){ a=_a;b=_b; rep(i,1,_a) rep(j,1,_b) x[i][j]=readint(); } inline void out(){ rep(i,1,a){ rep(j,1,b){ printf("%lld",x[i][j]); putchar(j==b?'\n':' '); } } }}X;int main(){ //freopen("#intput.txt","r",stdin); //freopen("#output.txt","w",stdout); n=readint();k=readll();X.in(n,n); matrix Ans=X^k; Ans.out(); //fclose(stdin); //fclose(stdout); return 0;}