P14016 [ICPC 2024 Nanjing R] 拓扑

首先有结论：\(u\) 的子树内拓扑序的数量为 \(\frac{sz_u!}{\prod_{v\in subtree(u)}sz_v}\)。
设 \(f_{u,i}\) 表示暂时把 \(u\) 子树内的点都删掉，\(u\) 在拓扑序中排第 \(i\) 的方案数。转移：

\[\begin{array}{lr} v\in son(u),f_{v,j}=\sum_{i=1}^{j-1}C_{n-i-sz_v}^{sz_u-sz_v-1}\times f_{u,i}\times \frac{(sz_u-sz_v-1)!}{\prod_{v\in(subtree(u)-sumtree(v)-{u})}} \end{array} \]

最后 \(i\) 号点的答案为

\[\begin{array}{lr} f_{i,i}\times C_{n-i}^{sz_i-1}\times\frac{sz_i!}{\prod_{u\in subtree(i)}sz_u} \end{array} \]

时间复杂度 \(\mathcal O(n^2)\)。

代码

/*
Luogu P14016 [ICPC 2024 Nanjing R] 拓扑
2026-03-20
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
template<int mod>struct Modint{
    int z;
    Modint(){z=0;}
    Modint(int x){x%=mod;z=x<0?x+mod:x;}
    Modint(long long x){x%=mod;z=x<0?x+mod:x;}
    Modint(short x){x%=mod;z=x<0?x+mod:x;}
    Modint(char x){x%=mod;z=x<0?x+mod:x;}
    Modint(bool x){x%=mod;z=x<0?x+mod:x;}
    friend Modint operator+(Modint t,Modint t2){Modint ans;ans.z=(t.z+t2.z)%mod;return ans;}
    friend Modint operator*(Modint t,Modint t2){Modint ans;ans.z=1ll*t.z*t2.z%mod;return ans;}
    friend Modint operator-(Modint t,Modint t2){Modint ans;ans.z=(t.z-t2.z)%mod;return ans;}
    Modint operator<<(const int t)const{Modint ans;ans.z=(z<<t)%mod;return ans;}
    Modint operator>>(const int t)const{Modint ans;ans.z=(z>>t)%mod;return ans;}
    Modint&operator+=(const Modint t){z=(z+t.z)%mod;return *this;}
    Modint&operator*=(const Modint t){z=1ll*z*t.z%mod;return *this;}
    Modint&operator-=(const Modint t){z=(z-t.z)%mod;return *this;}
    Modint&operator<<=(const int t){z=(z<<t)%mod;return *this;}
    Modint&operator>>=(const int t){z=(z>>t)%mod;return *this;}
    friend Modint ksm(Modint a,int b){
        Modint ans=1;
        while(b){if(b&1) ans=ans*a;a=a*a,b>>=1;}
        return ans;
    }
    friend void read(Modint&z){
        int x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=(x*10ll+c-'0')%mod,c=getchar();
        f?x=-x:0;
        z.z=x;
    }
    friend void write(Modint x){x.z<0?x.z+=mod:0;write(x.z);}
};
const int mod=998244353,maxn=5010;
#define M Modint<mod>
int n,sz[maxn];
vector<int>e[maxn];
M f[maxn][maxn],jc[maxn],mul[maxn],inv[maxn];
M C(int n,int m){
    if(n<m) return 0;
    return jc[n]*inv[m]*inv[n-m];
}
void dfs(int u){
    for(int v:e[u]){
        M z=mul[u]*ksm(mul[v],mod-2)*ksm(M(sz[u]),mod-2);
        z=ksm(z,mod-2);
        for(int i=2;i<=n-sz[v]+1;i++)
            f[v][i]=f[v][i-1]+f[u][i-1]*C(n-i+1-sz[v],sz[u]-sz[v]-1)*jc[sz[u]-sz[v]-1]*z;
        dfs(v);
    }
}
void get_size(int u){
    sz[u]=1,mul[u]=1;
    for(int v:e[u]) get_size(v),sz[u]+=sz[v],mul[u]*=mul[v];
    mul[u]*=sz[u];
}
signed main(){
    jc[0]=1;
    for(int i=1;i<=5000;i++) jc[i]=jc[i-1]*i;
    for(int i=0;i<=5000;i++) inv[i]=ksm(jc[i],mod-2);
    read(n);
    for(int i=2;i<=n;i++){
        int fa;read(fa);
        e[fa].push_back(i);
    }
    get_size(1);
    f[1][1]=1;
    dfs(1);
    for(int i=1;i<=n;i++){
        M z=ksm(M(mul[i]),mod-2)*jc[sz[i]];
        write(f[i][i]*C(n-i,sz[i]-1)*z);write(" ");
    }
    return 0;
}