QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#766391#9566. TopologyStelorWA 27ms223020kbC++202.8kb2024-11-20 17:10:562024-11-20 17:11:05

Judging History

This is the latest submission verdict.

  • [2024-11-20 17:11:05]
  • Judged
  • Verdict: WA
  • Time: 27ms
  • Memory: 223020kb
  • [2024-11-20 17:10:56]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=998244353;
const int N=5010;
int n,sz[N];
ll C[N][N],dp[N][N],pre[N][N],fac[N],f[N],prod[N];
vector<int> v[N];
bool vis[N];
ll qui(ll a,ll b, ll c){
    ll ret=1;
    while(b){
        if(b&1) ret=ret*a%c;
        a=a*a%c;
        b>>=1;
    }
    return ret;
}
ll inv(ll a){
    return qui(a,mod-2,mod);
}
void init()
{
    fac[0]=1;
    for(int i=1;i<N;++i) fac[i]=fac[i-1]*i%mod;
    C[0][0]=1;
    for(int i=1;i<N;++i)
    {
        for(int j=0;j<N;++j)
        {
            if(!j) C[i][0]=1;
            if(j>i) break;
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
}
void initDfs(int u,int fa){
    sz[u]=1;
    for(auto j:v[u]){
        if(j==fa) continue;
        initDfs(j,u);
        sz[u]+=sz[j];
    }
}
void initDfs2(int u,int fa){
    ll tmp=1;
    f[u]=1;
    for(auto j:v[u]){
        if(j==fa) continue;
        tmp=tmp*fac[sz[j]]%mod;
    }
    f[u]=f[u]*fac[sz[u]-1]%mod*inv(tmp)%mod;
    for(auto j:v[u]){
        if(j==fa) continue;
        initDfs2(j,u);
        f[u]=f[u]*f[j]%mod;
    }
}
void initDfs3(int u,int fa){
    prod[u]=sz[u];
    for(auto j:v[u]){
        if(j==fa) continue;
        initDfs3(j,u);
    }
    for(auto j:v[u]){
    	if(j==fa) continue;
    	prod[u]=prod[u]*prod[j]%mod;
    }
}
void dfs(int fa,int lll){
    vis[fa]=true;
    for(auto u:v[fa]){
        if(vis[u]) continue;
        vector<ll> pre(n+1);
        for(int i=1;i<=n;++i){
            if(n-i-sz[u]>=0&&sz[fa]-sz[u]-1>=0)
            pre[i]=dp[fa][i]*C[n-i-sz[u]][sz[fa]-sz[u]-1]%mod;
        }
        for(int i=1;i<=n;++i){
            pre[i]=pre[i-1]+pre[i];
            pre[i]%=mod;
        }
        ll now=prod[fa]*inv(prod[u])%mod*inv(sz[fa])%mod;
        now=fac[sz[fa]-sz[u]-1]*inv(now);

        for(int i=1;i<=n;++i){
            assert(sz[fa]-sz[u]-1>=0);
            dp[u][i]=pre[i-1]*now%mod;
        }

        /*
        for(int i=1;i<=n;++i){
            if(n-i-sz[u]>=0&&sz[fa]-sz[u]-1>=0&&sz[fa]-sz[u]-1>=0){
                pre[i]=(pre[i-1]+dp[fa][i]*C[n-i-sz[u]][sz[fa]-sz[u]-1]%mod*
                fac[sz[fa]-sz[u]-1]%mod*inv(tmp*inv(sz[u])%mod))%mod;
            }
        }
        for(int j=1;j<=n;++j){
            dp[u][j]=pre[j-1];
        }
        */
        dfs(u,fa);
    }
}
void solve(){
    cin >> n;
    for(int i=2;i<=n;++i){
        int x;
        cin >> x;
        v[x].push_back(i);
    }
    init();
    initDfs(1,0);
    initDfs2(1,0);
    initDfs3(1,0);
    dp[1][1]=1;
    dfs(1,0);
    for(int i=1;i<=n;++i){
        ll ans=dp[i][i]*f[i]%mod*C[n-i][sz[i]-1]%mod;
        cout<<ans<<" ";
    }

}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 21ms
memory: 203812kb

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: 15ms
memory: 205396kb

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: 12ms
memory: 203648kb

input:

2
1

output:

1 1 

result:

ok 2 number(s): "1 1"

Test #4:

score: -100
Wrong Answer
time: 27ms
memory: 223020kb

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 926937757 763859541 479464589 89314705 -19540330 -863328180 336017568 -228635202 210631424 687959472 215678190 494977892 -461520140 -247378664 46696642 406280762 -192556584 -764812552 -634168158 -877811963 -978899990 956938623 -750748733 -711309548 593729292 -...

result:

wrong answer 5th numbers differ - expected: '579367731', found: '926937757'