洛谷P3390 【模板】矩阵快速幂-白红宇

洛谷P3390 【模板】矩阵快速幂

阅读量：7110 次

发布时间：2019-06-28

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

给定n*n的矩阵A，求A^k

行列都是n

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N=105,MOD=1000000007;typedef long long ll;inline ll read(){    char c=getchar();ll x=0,f=1;    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}ll n,k;struct mat{    ll mt[N][N];    mat(){memset(mt,0,sizeof(mt));}}a,im,ans;void init(){    for(int i=1;i<=n;i++) im.mt[i][i]=1;}mat mul(mat &a,mat &b){    mat c;    for(int i=1;i<=n;i++)        for(int k=1;k<=n;k++) if(a.mt[i][k])            for(int j=1;j<=n;j++)                c.mt[i][j]=(c.mt[i][j]+a.mt[i][k]*b.mt[k][j])%MOD;    return c;}void pow(mat &a,ll b){    ans=im;    for(;b;b>>=1,a=mul(a,a))        if(b&1) ans=mul(ans,a);}int main(){    n=read();k=read();    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++) a.mt[i][j]=read();    init();    pow(a,k);    for(int i=1;i<=n;i++){        for(int j=1;j<=n;j++) printf("%lld ",ans.mt[i][j]);        putchar('\n');    }}