QOJ.ac
QOJ
ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|
#616 | #405092 | #59. Determinant of A+Bz | Hanghang | Hanghang | Success! | 2024-05-05 11:38:00 | 2024-05-05 11:38:02 |
詳細信息
Extra Test:
Wrong Answer
time: 1ms
memory: 7744kb
input:
3 1 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0
output:
1 0 0 0
result:
wrong answer 1st numbers differ - expected: '0', found: '1'
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#405092 | #59. Determinant of A+Bz | Hanghang | 97 | 826ms | 9588kb | C++14 | 2.0kb | 2024-05-05 11:00:53 | 2024-05-05 11:52:06 |
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=503,H=998244353;
ll n,w=1,dt,a[N][N],b[N][N],f[N][N];
ll Ksm(ll x,ll y)
{
ll s=1;
for(ll i=1;i<=y;i<<=1,x=x*x%H)if(i&y)s=s*x%H;
return s;
}
void GuassB()
{
for(int i=1;i<=n;++i)
{
int z=i;
while(z<=n&&!b[z][i])z++;
if(z<=n&&z>i)w=H-w,swap(a[z],a[i]),swap(b[z],b[i]);
z=i;
while(z<=n&&!b[i][z])z++;
if(z<=n&&z>i){w=H-w;for(int j=1;j<=n;j++)swap(a[j][i],a[z][i]),swap(b[j][i],b[z][i]);}
for(;dt<=n&&!b[i][i];dt++)
{
for(int j=1;j<=n;j++)b[i][j]=a[i][j],a[i][j]=0;
for(int j=1;j<i;j++)
{
ll d=b[i][j]*Ksm(b[j][j],H-2)%H;
for(ll k=1;k<=n;k++)a[i][k]=(a[i][k]+(H-d)*a[j][k])%H,b[i][k]=(b[i][k]+(H-d)*b[j][k])%H;
}
}
ll ivi=Ksm(b[i][i],H-2);
for(ll j=1;j<=n;j++)if(j!=i)
{
ll d=b[j][i]*ivi%H;
for(ll k=1;k<=n;k++)a[j][k]=(a[j][k]+(H-d)*a[i][k])%H,b[j][k]=(b[j][k]+(H-d)*b[i][k])%H;
}
}
for(int i=1;i<=n;i++)
{
w=w*b[i][i]%H;ll ivi=Ksm(b[i][i],H-2);
for(int j=1;j<=n;j++)a[i][j]=a[i][j]*ivi%H;
}
}
void GuassA()
{
for(int i=2;i<=n;i++)
{
int z=i;
while(z<=n&&!a[z][i-1])z++;
if(z>n)continue;
swap(a[i],a[z]);
for(int j=1;j<=n;j++)swap(a[j][i],a[j][z]);
ll ivi=Ksm(a[i][i-1],H-2);
for(int j=i+1;j<=n;j++)
{
ll kk=a[j][i-1]*ivi%H;
for(int k=i-1;k<=n;k++)a[j][k]=(a[j][k]-kk*a[i][k]%H+H)%H;
for(int k=1;k<=n;k++)a[k][i]=(a[k][i]+kk*a[k][j])%H;
}
}
}
void Heisenberg()
{
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=(H-a[i][j])%H;
f[0][0]=w;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)f[i][j]=f[i-1][j-1];
for(int k=1;k<=i;k++)
{
ll s=1;
for(int j=k+1;j<=i;j++)s=s*a[j][j-1]%H;
for(int j=0;j<=n;j++)f[i][j]=(f[i][j]-a[k][i]*f[k-1][j]%H*s%H+H)%H;
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>b[i][j];
GuassB();GuassA();Heisenberg();
for(int i=0;i<=n;i++)cout<<(i+dt>n?0:f[n][i+dt])<<" ";
}