QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104580 | #59. Determinant of A+Bz | iee | Judging | / | / | C++14 | 2.1kb | 2023-05-11 09:19:20 | 2024-03-04 04:40:49 |
Judging History
你现在查看的是测评时间为 2024-03-04 04:40:49 的历史记录
- [2024-05-05 11:54:08]
- hack成功,自动添加数据
- (/hack/617)
- [2024-05-05 11:38:15]
- hack成功,自动添加数据
- (/hack/616)
- [2024-03-04 04:35:40]
- hack成功,自动添加数据
- (/hack/552)
- [2023-08-10 23:21:45]
- System Update: QOJ starts to keep a history of the judgings of all the submissions.
- [2023-05-11 09:19:20]
- 提交
answer
//https://qoj.ac/submission/69597
//https://www.cnblogs.com/Y25t/p/15808634.html
#include<cstdio>
#include<iostream>
using namespace std;
const int o=510,MOD=998244353;
inline int qp(int b,int f){int res=1;for(;f;f>>=1,b=b*1ll*b%MOD) if(f&1) res=res*1ll*b%MOD;return res;}
int n,a[o][o],b[o][o],f[o][o],delt,coef=1;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&a[i][j]);
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&b[i][j]);
for(int i=1,j;i<=n;++i){
for(j=i;j<=n;++j) if(b[j][i]) break;
if(j<=n&&j>i){coef=MOD-coef;for(int k=1;k<=n;++k) swap(a[i][k],a[j][k]),swap(b[i][k],b[j][k]);}
// for(j=i;j<=n;++j) if(b[i][j]) break;
// if(j<=n&&j>i){coef=MOD-coef;for(int k=1;k<=n;++k) swap(a[k][i],a[k][j]),swap(b[k][i],b[k][j]);}
for(;delt<=n&&!b[i][i];++delt){
for(j=1;j<=n;++j) b[i][j]=a[i][j],a[i][j]=0;
for(j=1;j<i;++j) for(int k=1,v=b[i][j]*1ll*qp(b[j][j],MOD-2)%MOD;k<=n;++k)
a[i][k]=(a[i][k]+(MOD-v)*1ll*a[j][k])%MOD,b[i][k]=(b[i][k]+(MOD-v)*1ll*b[j][k])%MOD;
}
if(b[i][i]) for(j=1;j<=n;++j) if(j^i) for(int k=1,v=b[j][i]*1ll*qp(b[i][i],MOD-2)%MOD;k<=n;++k)
a[j][k]=(a[j][k]+(MOD-v)*1ll*a[i][k])%MOD,b[j][k]=(b[j][k]+(MOD-v)*1ll*b[i][k])%MOD;
}
for(int i=1;i<=n;++i){
coef=coef*1ll*b[i][i]%MOD;
for(int j=1,v=qp(b[i][i],MOD-2);j<=n;++j) a[i][j]=a[i][j]*1ll*v%MOD;
}
for(int i=1,j,v;i<n;++i){
for(j=i+1;j<=n;++j) if(a[j][i]) break;
if(j>n) continue;
if(j>i+1){
for(int k=1;k<=n;++k) swap(a[i+1][k],a[j][k]);
for(int k=1;k<=n;++k) swap(a[k][i+1],a[k][j]);
}
for(j=i+2;j<=n;++j){
v=a[j][i]*1ll*qp(a[i+1][i],MOD-2)%MOD;
for(int k=1;k<=n;++k) a[j][k]=(a[j][k]+(MOD-v)*1ll*a[i+1][k])%MOD;
for(int k=1;k<=n;++k) a[k][i+1]=(a[k][i+1]+v*1ll*a[k][j])%MOD;
}
}
f[0][0]=coef;
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j) f[i][j]=f[i-1][j-1];
for(int j=i,v=1;j;v=MOD-a[j][j-1]*1ll*v%MOD,--j) for(int k=0;k<=n;++k) f[i][k]=(f[i][k]+a[j][i]*1ll*v%MOD*f[j-1][k])%MOD;
}
for(int i=0;i<=n;++i) printf("%d ",((i+delt)>n)?0:f[n][i+delt]);
return 0;
}