比赛 |
2025.6.7 |
评测结果 |
AAEEEEEEEE |
题目名称 |
矩阵幂之和 |
最终得分 |
20 |
用户昵称 |
李奇文 |
运行时间 |
2.635 s |
代码语言 |
C++ |
内存使用 |
3.60 MiB |
提交时间 |
2025-06-07 11:25:34 |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct mat{
int m[31][31];
};
int n,k,mod;
mat mul(mat a,mat b){
mat c;
memset(c.m,0,sizeof(c.m));
for(int i=0;i<2*n;i++){
for(int j=0;j<2*n;j++){
for(int k=0;k<2*n;k++){
c.m[i][j]=(c.m[i][j]+(a.m[i][k]*b.m[k][j])%mod)%mod;
}
}
}
return c;
}
mat ksm(mat a,int k){
mat res;
memset(res.m,0,sizeof(res.m));
for(int i=0;i<2*n;i++){
res.m[i][i]=1;
}
while(k){
if(k&1) res=mul(res,a);
k>>=1;
a=mul(a,a);
}
return res;
}
signed main(){
freopen("matrix_sum.in","r",stdin);
freopen("matrix_sum.out","w",stdout);
mat a;
memset(a.m,0,sizeof(a.m));
scanf("%lld%lld%lld",&n,&k,&mod);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%lld",&a.m[i][j]);
a.m[i][j]=a.m[i][j]%mod;
}
}
mat b;
memset(b.m,0,sizeof(b.m));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
b.m[i][j]=a.m[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=n;j<2*n;j++){
b.m[i][j]=0;
}
}
for(int i=n;i<2*n;i++){
for(int j=0;j<n;j++){
b.m[i][j]=a.m[i-n][j];
}
}
for(int i=n;i<2*n;i++) b.m[i][i]=1;
for(int i=0;i<2*n;i++) a.m[i][i+n]=1;
b=ksm(b,k-1);
mat ans=mul(a,b);
for(int i=0;i<n;i++){
printf("%lld ",ans.m[i][0]);
for(int j=1;j<n;j++){
printf("%lld ",ans.m[i][j]);
}
printf("\n");
}
return 0;
}