题解：P14016 [ICPC 2024 Nanjing R] 拓扑

· · 题解

设 f(i,j) 表示除去 i 的子树（不包括 i） i 在第 j 位的方案数。

然后考虑 f(i,j) 如何向 f(u,k) 转移（其中 u\in son_i,j<k），设 M 表示 i 的子树除去 u 的子树以及 i 自己的节点集合，m=|M|，然后我们首先考虑 M 集合的方案数，因为 M 只要放在 i 后面，然后在 k 位置插入 u 即可，是独立的，但是 M 的方案数有相当于是几个 i 的子结点的子树的方案数，这个如果之前做过套路的题可以直接用结论：

g(u)=\frac{siz_u!}{\prod_{v\in \text{subtree(u)}} siz_v}

现在我们来考虑证明一下，首先根据题意 u 应该放在第一位，然后先不管各个子结点子树的方案数，单纯考虑把子结点的子树交错评在一起的方案数也就是（下式 sum_k=\sum_{i=1}^k siz_{v_i}）：

{sum_2\choose siz_{v_2}}{sum_3\choose siz_{v_3}}\dots{sum_k\choose siz_{v_k}}

然后手动把组合数展开并且约分，可以得到：

\frac{(siz_u-1)!}{\prod_{i=1}^k siz_{v_i}!}

然后再乘上各个子结点子树的方案数（由于子结点的子树并没有祖先后代关系，因此互不影响），得到：

g(u)=\frac{(siz_u-1)!}{\prod_i siz_{v_i}!}\times \prod_i g(v_i)

通过展开后面的 g(v_i) 你会发现，分母正好只会剩下 siz_{v_i} 项，然后整理一下可以得到：

g(u)=\frac{siz_u!}{\prod_{v\in subtree(u)} siz_v}

类似地，可以算出对于 M 的式子（用 P 来表示）：

P(M)=\frac{m!}{\prod_{v\in M} siz_v}

整理一下：

P(M)=\frac{g(u)\times siz_v!\times m!\times siz_u}{g(v)\times siz_u!}

算出 P(M) 之后考虑和 f(i,j) 合并，既然是 i 的子树中的点，显然应该放在 i 后面，然后除了 i 子树中的点都已经被放完了，因此：

f(i,j){n-siz_v-i\choose siz_u-siz_v-1}P(M)\rightarrow f(u,k)

然后这个转移显然是 O(n^3) 换成填表法之后就可以随便优化成 O(n^2) 了。

统计答案时，由于只有 u 子树没有选了，因此带个组合数选上即可

ans_u=f(u,u)\times g(u)\times{n-u\choose siz_u-1} 

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5005;
const int mod=998244353;
int n,fa[N],sz[N],H[N],invH[N];
int fac[N],ifac[N];
unsigned dp[N][N];
vector<int> ed[N];
int qpow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int C(int n,int m)
{
    if(n<0 or m<0 or n<m) return 0;
    return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
signed main()
{
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        cin>>fa[i];
        ed[fa[i]].push_back(i);
    }
    for(int i=1;i<=n;i++)
        sz[i]=1,H[i]=1;
    for(int i=n;i>=2;i--)
        sz[fa[i]]+=sz[i];
    for(int i=1;i<=n;i++)
        H[i]=sz[i];
    for(int i=n;i>=2;i--)
        H[fa[i]]=H[fa[i]]*H[i]%mod;
    for(int i=1;i<=n;i++)
        invH[i]=qpow(H[i],mod-2);
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for(int i=n;i>=1;i--)
        ifac[i-1]=ifac[i]*i%mod;
    dp[1][1]=1;
    for(int i=1;i<=n;i++)
        for(auto u:ed[i])
        {
            int m=sz[i]-sz[u]-1;
            int P=fac[m]*sz[i]%mod*H[u]%mod*invH[i]%mod;
            for(int k=1;k<=n-sz[u]+1;k++)
            {
                dp[u][k]=dp[u][k-1];
                if(k>=2)
                {
                    int val=dp[i][k-1]*C(n-k+1-sz[u],m)%mod;
                    val=val*P%mod;
                    dp[u][k]=(dp[u][k]+val)%mod;
                }
            }
        }
    for(int i=1;i<=n;i++)
    {
        int g=fac[sz[i]]*invH[i]%mod;
        int ans=dp[i][i]*g%mod*C(n-i,sz[i]-1)%mod;
        cout<<ans;
        if(i<n) cout<<' ';
    }
    cout<<'\n';
    return 0;
}