首页 > 代码库 > luoguP3390 【模板】矩阵快速幂

luoguP3390 【模板】矩阵快速幂

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


 

行列都是n

 


 

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>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);    }}

 

luoguP3390 【模板】矩阵快速幂