QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#715853#9566. TopologyOIer_kzcWA 2ms22608kbC++172.1kb2024-11-06 13:35:002024-11-06 13:35:00

Judging History

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

  • [2024-11-06 13:35:00]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:22608kb
  • [2024-11-06 13:35:00]
  • 提交

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'