矩阵乘法+快速幂
title: 矩阵乘法+快速幂
categories:
- ICPC
tags:
- null
abbrlink: f4d30541
date: 2023-11-04 00:00:00
给定 n×n 的矩阵 A,求 A^k。
typedef long long LL;
const int mod=1000000007;
struct matrix{
LL c[101][101];
matrix(){memset(c, 0, sizeof c);}
} A, res;
LL n, k;
matrix operator*(matrix &x, matrix &y){ //矩阵乘法
matrix t; //临时矩阵
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
for(int k=1; k<=n; k++)
t.c[i][j]=(t.c[i][j]+x.c[i][k]*y.c[k][j])%mod;
return t;
}
void quickpow(LL k){ //快速幂
for(int i=1; i<=n; i++) res.c[i][i]=1; //单位矩阵
while(k){
if(k & 1) res = res*A;
A = A*A;
k >>= 1;
}
}
int main(){
scanf("%d%lld",&n,&k);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
scanf("%d",&A.c[i][j]);
quickpow(k);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++)
printf("%d ",res.c[i][j]);
puts("");
}
return 0;
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!