首页 > 代码库 > 洛谷 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 <ctype.h>#include <cstdio>typedef long long LL;#define Mod 1000000007void read(LL &x){ x=0; char ch=getchar(); for(;!isdigit(ch);ch=getchar()); for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘;}LL k,n;struct node{ LL a[150][150]; inline node operator*(const node &b)const { node c; for(LL i=1;i<=n;i++) { for(LL j=1;j<=n;j++) { c.a[i][j]=0; for(LL k=1;k<=n;k++) c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j])%Mod; } } return c; }}A,ans;int main(int argc,char *argv[]){ read(n); read(k); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) read(A.a[i][j]); ans=A;k--; for(;k;k>>=1LL,A=A*A) if(k&1) ans=ans*A; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) printf("%d ",ans.a[i][j]); printf("\n"); } return 0;}
洛谷 P3390 【模板】矩阵快速幂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。