QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#715794#9566. TopologyOIer_kzcWA 0ms4072kbC++172.1kb2024-11-06 13:26:032024-11-06 13:26:04

Judging History

你现在查看的是最新测评结果

  • [2024-11-06 13:26:04]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4072kb
  • [2024-11-06 13:26:03]
  • 提交

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'