QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#387213 | #59. Determinant of A+Bz | Hanghang | 0 | 700ms | 9532kb | C++14 | 1.8kb | 2024-04-12 09:46:41 | 2024-04-12 09:46:43 |
Judging History
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]);
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++)for(ll k=1,d=b[i][j]*Ksm(b[j][j],H-2);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;
}
for(ll j=1,ivi=Ksm(b[i][i],H-2);j<=n;j++)if(j!=i)for(ll k=1,d=b[j][i]*ivi%H;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()
{
f[0][0]=w;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;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<=i;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])<<" ";
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 7808kb
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:
0 562160817 175535903 443284469 223039496 939899989 587204040 942943536 397840744 842731377 415872342 520505487 352386530 945001753 485943331 858810352 914586784 453357017 464494428 598270861 144143987 473246236 938746522 906380732 401839366 164729860 170911469 365645719 939655150 483037434 82556429...
result:
wrong answer 2nd numbers differ - expected: '436083536', found: '562160817'
Subtask #2:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 700ms
memory: 9532kb
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:
197564738 221906216 450758758 912143361 615937344 439080439 131406243 596624366 648971457 84873458 305548921 604958391 915689006 392822469 878026660 423815308 573319599 633753244 147359659 721178504 558700076 392507268 416281513 294228377 726983797 792811621 98536178 184387414 885823882 819054346 66...
result:
wrong answer 2nd numbers differ - expected: '776338137', found: '221906216'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%