QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#18012 | #59. Determinant of A+Bz | Y25t# | 0 | 0ms | 0kb | C++20 | 2.3kb | 2022-01-15 18:09:59 | 2024-03-04 04:41:37 |
Judging History
answer
#include<bits/stdc++.h>
#define P 998244353
#define N 505
inline int fmo(int x){
return x+((x>>31)&P);
}
inline int fp(int x,int k=P-2){
int res=1;
for(;k;k>>=1,x=1ll*x*x%P)
if(k&1)
res=1ll*res*x%P;
return res;
}
int n,a[N][N],b[N][N];
int f[N][N];
int main(){
freopen(".in","r",stdin);
freopen(".out","w",stdout);
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]);
int flg=1,t=0;
for(int i=1;i<=n;i++){
if(!b[i][i])
for(int j=i+1;j<=n;j++)
if(b[j][i]){
flg=fmo(-flg);
std::swap(a[i],a[j]),std::swap(b[i],b[j]);
break;
}
if(!b[i][i])
for(int j=i+1;j<=n;j++)
if(b[i][j]){
flg=fmo(-flg);
for(int k=1;k<=n;k++)
std::swap(a[k][i],a[k][j]),std::swap(b[k][i],b[k][j]);
break;
}
for(;!b[i][i]&&t<n;t++){
for(int j=1;j<=n;j++)
b[i][j]=a[i][j],a[i][j]=0;
for(int j=1;j<i;j++){
int tmp=1ll*b[i][j]*fp(b[j][j])%P;
for(int k=1;k<=n;k++){
a[i][k]=fmo(a[i][k]-1ll*tmp*a[j][k]%P);
b[i][k]=fmo(b[i][k]-1ll*tmp*b[j][k]%P);
}
}
}
int inv=fp(b[i][i]);
for(int j=1;j<=n;j++) if(j!=i){
int tmp=1ll*b[j][i]*inv%P;
for(int k=1;k<=n;k++){
a[j][k]=fmo(a[j][k]-1ll*tmp*a[i][k]%P);
b[j][k]=fmo(b[j][k]-1ll*tmp*b[i][k]%P);
}
}
}
for(int i=1;i<=n;i++){
flg=1ll*flg*b[i][i]%P;
int inv=fp(b[i][i]);
for(int j=1;j<=n;j++)
a[i][j]=1ll*a[i][j]*inv%P;
}
for(int i=1;i<n;i++){
if(!a[i+1][i])
for(int j=i+2;j<=n;j++)
if(a[j][i]){
std::swap(a[i+1],a[j]);
for(int k=1;k<=n;k++)
std::swap(a[k][i+1],a[k][j]);
break;
}
int inv=fp(a[i+1][i]);
for(int j=i+2;j<=n;j++){
int tmp=1ll*a[j][i]*inv%P;
for(int k=1;k<=n;k++)
a[j][k]=fmo(a[j][k]-1ll*tmp*a[i+1][k]%P);
for(int k=1;k<=n;k++)
a[k][i+1]=fmo(a[k][i+1]+1ll*tmp*a[k][j]%P-P);
}
}
f[0][0]=1;
for(int i=1;i<=n;i++){
int tmp=1;
for(int j=i;j;j--){
for(int k=0;k<=n;k++)
f[i][k]=fmo(f[i][k]+1ll*((i-j)&1?fmo(-1):1)*f[j-1][k]%P*a[j][i]%P*tmp%P-P);
tmp=1ll*tmp*a[j][j-1]%P;
}
for(int k=0;k<n;k++)
f[i][k+1]=fmo(f[i][k+1]+f[i-1][k]-P);
}
for(int i=0;i<=n;i++)
printf("%d ",i+t>n?0:int(1ll*flg*f[n][i+t]%P));
puts("");
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
input:
50 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 179093706 0 0 0 0 0 873235003 0 873022990 0 0 0 0 150372208 0 0 0 0 0 0 0 0 540031202 441544333 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30490606 0 23238599 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
result:
Subtask #2:
score: 0
Dangerous Syscalls
Test #51:
score: 0
Dangerous Syscalls
input:
500 0 0 0 0 0 482890969 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1077401 0 0 210804413 0 508044994 0 0 0 398405351 0 0 0 0 0 0 0 171917316 0 0 0 0 0 0 0 0 0 0 0 429230725 0 0 0 0 0 45665526 0 0 0 925078893 0 0 396149045 0 0 0 595858405 0 0 0 0 0 57208...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #1:
0%