QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#715794 | #9566. Topology | OIer_kzc | WA | 0ms | 4072kb | C++17 | 2.1kb | 2024-11-06 13:26:03 | 2024-11-06 13:26:04 |
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)sz[x]*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: 4072kb
input:
4 1 1 2
output:
3 2 1 2
result:
ok 4 number(s): "3 2 1 2"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 4004kb
input:
9 1 1 2 2 3 3 4 5
output:
672 420 180 120 144 108 120 170 210
result:
wrong answer 4th numbers differ - expected: '160', found: '120'