QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#715853 | #9566. Topology | OIer_kzc | WA | 2ms | 22608kb | C++17 | 2.1kb | 2024-11-06 13:35:00 | 2024-11-06 13:35:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define p 998244353
#define ll long long
#define lx edge[x][i]
ll ksm(int x,int y){
if(!x)return 1;
ll u=ksm(x/2,y);
u=u*u%p;
if(x&1)u=u*y%p;
return u;
}
int n;
int fa[5011];
vector<int>edge[5011];
ll sz[5011],jc[5011],ny[5011],g[5011],f[5011];
ll sz2[5011],bz[5011];
ll w[5011][5011],h[5011];
ll C(int x,int y){
return (ll)jc[x]*ny[y]%p*ny[x-y]%p;
}
void dfs(int x){
bz[x]=1;
fo(i,0,(int)edge[x].size()-1){
dfs(lx);
}
}
ll Ny(int x){
return (ll)ny[x]*jc[x-1]%p;
}
int main(){
scanf("%d",&n);
fo(i,2,n)scanf("%d",&fa[i]);
fo(i,2,n)edge[fa[i]].push_back(i);
jc[0]=ny[0]=1;
fo(i,1,n){
jc[i]=(ll)jc[i-1]*i%p;
ny[i]=ksm(p-2,jc[i]);
}
fo(i,1,n){
f[i]=1;
}
fod(i,n,1){
++sz[i];
f[i]=(ll)f[i]*Ny(sz[i])%p;
if(i>1)sz[fa[i]]+=sz[i],f[fa[i]]=(ll)f[fa[i]]*f[i]%p;
}
fo(i,1,n){
g[i]=1;
fo(j,1,n)sz2[j]=bz[j]=0;
dfs(i);
fod(j,n,1){
sz2[j]++;
if(bz[j])sz2[j]=0;
if(j>1)sz2[fa[j]]+=sz2[j];
if(sz2[j]){
g[i]=g[i]*Ny(sz2[j])%p;
}
}
}
fo(x,2,n){
h[x]=(ll)f[fa[x]]*ksm(p-2,f[x])%p*sz[fa[x]]%p;
}
fo(x,2,n){
int y=fa[x];
w[x][y]=(ll)Ny(sz[y]-sz[x])%p*Ny(sz[y])%p;
while(y!=1){
y=fa[y];
w[x][y]=(ll)w[fa[x]][y]*sz[x]%p*Ny(sz[y]-sz[x])%p*Ny(sz[y])%p;
}
}
// cout<<w[4][2]<<" "<<w[4][2]*jc[5]%p*ny[3]<<endl;
fo(x,1,n){
ll ans=(ll)f[x]*g[x]%p*C(n-x,sz[x]-1)%p*jc[sz[x]]%p*jc[n-sz[x]]%p;
int y=x;
ll u=f[x]*sz[x]%p;
while(y!=1){
u=u*h[y]%p*(-1);
y=fa[y];
if(sz[y]-1>n-x)break;
ans+=(ll)u*w[x][y]%p*g[y]%p*C(n-x,sz[y]-1)%p*jc[sz[y]]%p*jc[n-sz[y]]%p;
}
ans%=p;
if(ans<0)ans+=p;
printf("%lld ",ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4052kb
input:
4 1 1 2
output:
3 2 1 2
result:
ok 4 number(s): "3 2 1 2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 6136kb
input:
9 1 1 2 2 3 3 4 5
output:
672 420 180 160 152 108 120 170 210
result:
ok 9 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
2 1
output:
1 1
result:
ok 2 number(s): "1 1"
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 22608kb
input:
500 1 2 3 4 5 6 7 7 8 10 8 10 11 4 11 12 12 17 15 13 21 21 22 5 16 9 24 28 28 19 29 27 17 33 23 3 33 27 30 9 25 34 16 26 30 34 46 45 41 14 43 49 43 35 39 37 26 48 52 58 51 56 51 55 19 48 63 36 67 69 54 60 71 61 29 40 32 77 73 55 66 42 77 72 71 69 62 83 46 64 88 39 83 36 89 94 47 98 57 61 38 80 78 88...
output:
331058271 331058271 107893248 201481008 579367731 589986578 369419132 724515587 790699925 186527490 533263065 321112231 404160945 850729553 271511598 226187733 782814994 369623 439250018 734952162 33221138 966998924 885431451 881916157 372921049 626084261 786553764 89364165 203982809 29020472 877414...
result:
wrong answer 6th numbers differ - expected: '934007150', found: '589986578'