首页 > 代码库 > 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 【模板】矩阵快速幂
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。