QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#714414#9566. Topologyucup-team1196TL 0ms3624kbC++232.0kb2024-11-05 23:07:042024-11-05 23:07:04

Judging History

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

  • [2024-11-05 23:07:04]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3624kb
  • [2024-11-05 23:07:04]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
const int N=2009,mod=998244353;
int fac[N],invfac[N];
int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
    }
    return ans;
}

void init(){
    fac[0]=invfac[0]=1;
    for(int i=1;i<=N-8;++i) fac[i]=fac[i-1]*i%mod;
    invfac[N-8]=qpow(fac[N-8],mod-2);
    for(int i=N-8;i;--i) invfac[i-1]=invfac[i]*i%mod;
}

int C(int x,int y){
    if(x<y) return 0;
    return fac[x]*invfac[x-y]%mod*invfac[y]%mod;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    init();
    int n;
    cin>>n;
    vector<vector<int>>e(n+1);
    for(int i=2;i<=n;++i){
        int x;
        cin>>x;
        e[x].push_back(i);
    }
    vector<int>sz(n+1),f(n+1),dep(n+1);
    vector g(n+1,vector(n+1,0ll));
    dep[1]=1;
    auto dfs=[&](auto dfs,int u)->void{
        sz[u]=1;
        f[u]=1;
        for(auto v:e[u]){
            dep[v]=dep[u]+1;
            dfs(dfs,v);
            sz[u]+=sz[v];
            f[u]=f[u]*f[v]%mod*invfac[sz[v]]%mod;
        }
        f[u]=f[u]*fac[sz[u]-1]%mod;
    };
    dfs(dfs,1);
    g[1][1]=1;
    auto dfs2=[&](auto dfs2,int u)->void{
        int sf=1,sfac=1;
        for(auto v:e[u]){
            sf=sf*f[v]%mod;
            sfac=sfac*invfac[sz[v]]%mod;
        }
        for(auto v:e[u]){
            for(int i=dep[u];i<=n-sz[u]+1;++i){
                for(int j=i+1;j<=n-sz[v]+1;++j){
                    int ans=g[u][i]*C(n-i-sz[v],sz[u]-sz[v]-1)%mod;
                    ans=ans*sf%mod*qpow(f[v],mod-2)%mod;
                    ans=ans*sfac%mod*fac[sz[v]]%mod*fac[sz[u]-1-sz[v]]%mod;
                    g[v][j]+=ans;
                    if(g[v][j]>=mod) g[v][j]-=mod;
                }
            }
            dfs2(dfs2,v);
        }
    };
    dfs2(dfs2,1);
    for(int i=1;i<=n;++i) cout<<f[i]*g[i][i]%mod*C(n-i,sz[i]-1)%mod<<" \n"[i==n];
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

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: 0ms
memory: 3584kb

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: 3516kb

input:

2
1

output:

1 1

result:

ok 2 number(s): "1 1"

Test #4:

score: -100
Time Limit Exceeded

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:


result: