首页 > 代码库 > P3390矩阵快速幂
P3390矩阵快速幂
题目背景
矩阵快速幂
题目描述
给定n*n的矩阵A，求A^k
输入输出格式
输入格式：
第一行，n,k
第2至n+1行，每行n个数，第i+1行第j个数表示矩阵第i行第j列的元素
输出格式：
输出A^k
共n行，每行n个数，第i行第j个数表示矩阵第i行第j列的元素，每个元素模10^9+7
输入输出样例
输入样例#1：
2 11 11 1
输出样例#1：
1 11 1
说明
n<=100, k<=10^12, |矩阵元素|<=1000
//上板子！#include<iostream>#include<cstdio>#define ll long long#define mod 1000000007using namespace std;ll n,m;struct node{ ll a[101][101];}ans,base;ll init(){ ll x=0,f=1;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}node mul(node a,node b){ node res; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { res.a[i][j]=0; for(int k=1;k<=n;k++) res.a[i][j]=(res.a[i][j]+a.a[i][k]*b.a[k][j])%mod; } return res;}node qw(node a,ll k){ node res=a; while(k) { if(k&1) a=mul(a,res); res=mul(res,res);k>>=1; } return a;}int main(){ n=init();m=init(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { ans.a[i][j]=init(); } m--; ans=qw(ans,m); for (int i=1;i<=n;i++) { for (int j=1;j<n;j++) printf("%d ",ans.a[i][j]); printf("%d\n",ans.a[i][n]); }}
算法：矩阵快速幂
P3390矩阵快速幂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。