题目背景
矩阵快速幂
题目描述
给定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 1 1 1 1 1
输出样例#1:
1 1 1 1
说明
n<=100, k<=10^12, |矩阵元素|<=1000 算法:矩阵快速幂
rt模板
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> typedef long long LL; using namespace std; const int mod = 1e9+7; LL n,m,k; struct Matrix{ int a[105][105]; Matrix operator * (const Matrix &b) { Matrix ret; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { ret.a[i][j]=0; for (int k=1;k<=n;k++) ret.a[i][j]=((LL)a[i][k]*b.a[k][j]%mod+ret.a[i][j]%mod)%mod; } return ret; } }a; Matrix ksm(Matrix a,LL x) { Matrix ret,k;k=a; ret=a;x--; while(x) { if (x&1) ret=ret*k; k=k*k; x>>=1; } return ret; } int main() { scanf("%lld%lld",&n,&k); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&a.a[i][j]); a=ksm(a,k); for (int i=1;i<=n;i++) { for (int j=1;j<n;j++) printf("%d ",a.a[i][j]); printf("%d ",a.a[i][n]); } return 0; }