P14016 [ICPC 2024 Nanjing R] 拓扑 题解

· · 题解

题目传送门

解析

前置：大小为 n 的树的拓扑序数量为 \large\frac{n!}{\prod_{u} sz_u}，sz_u 表示以 u 为根的子树大小。

由于拓扑序是从上往下逐渐生成的，考虑自顶向下 DP。

那么，记 f_{u,i} 表示已经考虑了 u 子树外的点和 u 节点，u 在拓扑序中的位置为 i 的方案数。

考虑如何从 f_{u,i} 转移到子节点 v 的 f_{v,j}。

先分析一下 f_{u,i} 和 f_{v,j}。在 f_{v,j} 里，新加入了 v 节点和 u 的其他子树，由于 u 子树内的点不会排到 u 之前，所以这些点只会在 i 往后，同时也限制了 j 的范围。

考虑先把其他子树加入。那么，先计算 u 子树除 v 子树以外部分的拓扑序，在合并到已有序列中。记 val_u=\prod_{v\in subtree(u)}sz_v，根据公式，结果为 \frac{(sz_u-sz_v)!}{val_u} val_v \frac{sz_u}{sz_u-sz_v}，val_v 是为了去掉 v 子树内 sz 的连乘，\frac{sz_u}{sz_u-sz_v} 是因为 u 的 sz 发生了改变。

再考虑把得出的拓扑序放入原序列。原来 u 前面有 i-1 个点，则后面有 n-sz_u-(i-1) 个点，和该拓扑序的 sz_u-sz_v-1 个点合并。有 \binom{n-sz_u-(i-1)+sz_u-sz_v-1}{sz_u-sz_u-1}=\binom{n-sz_v-i}{sz_u-sz_v-1} 种方案。

至于加入 v 点，只能在 j 位置放了，方案唯一。

有：

f_{v,j}=\sum_{i=1}^{\min(n-sz_u+1,j-1)} f_{u,i}\times\frac{(sz_u-sz_v)!}{val_u}\times\frac{val_v sz_u}{sz_u-sz_v}\times \binom{n-sz_v-i}{sz_u-sz_v-1}

注意到式子右边与 j 无关，容易前缀和优化。

边界 f_{1,1}=1。

最后，从 f_{u,u} 到 ans_u，也是先生成 u 子树的拓扑序数量，再和 n-sz_u+1-u 个点合并。

时间复杂度 $O(n^2)$。 :::info[Code] ```cpp line-numbers #include <bits/stdc++.h> using namespace std; #define SIZIO (1<<22) #define gc() (rp1==rp2&&(rp2=(rp1=buf)+fread(buf,1,SIZIO,stdin))==rp1?EOF:*rp1++) #define pc(c) ((wrp==wbuf+SIZIO)&&(fwrite(wbuf,1,SIZIO,stdout),wrp=wbuf),(*wrp++)=c) char buf[SIZIO+1],*rp1,*rp2; char wbuf[SIZIO+1],*wrp=wbuf; inline int read(){ int d=0,f=0;char ch=gc(); while (!isdigit(ch)) f|=(ch=='-'),ch=gc(); while (isdigit(ch)) d=(d<<1)+(d<<3)+ch-'0',ch=gc(); return f?-d:d; } inline void write(int n){ if (n<0) n=-n,pc('-'); int stk[35],tp=0; do{stk[++tp]=n%10,n/=10;}while (n); while (tp) pc(stk[tp--]+'0'); } const int N=5005,mod=998244353; int n,h[N],idx=1,e[N],ne[N]; int sz[N],val[N],ival[N],f[N][N],fac[N],ifac[N],inv[N]; inline void add_e(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;} inline void add(int &x,int y) {x+=y;(x>=mod)&&(x-=mod);} inline void init(){ fac[0]=ifac[0]=inv[0]=fac[1]=ifac[1]=inv[1]=1; for (int i=2;i<=n;i++) { fac[i]=1ll*fac[i-1]*i%mod; inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod; ifac[i]=1ll*ifac[i-1]*inv[i]%mod; } } inline int C(int n,int m) { if (n<m||m<0) return 0; return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod; } void dfs1(int u){//自下而上收集信息 sz[u]=val[u]=ival[u]=1; for (int i=h[u];i;i=ne[i]){ int v=e[i]; dfs1(v),sz[u]+=sz[v]; val[u]=1ll*val[u]*val[v]%mod; ival[u]=1ll*ival[u]*ival[v]%mod; } val[u]=1ll*val[u]*sz[u]%mod; ival[u]=1ll*ival[u]*inv[sz[u]]%mod; } int sum[N]; void dfs2(int u){//自顶向下计算 int S1=1ll*ival[u]*sz[u]%mod; for (int ii=h[u];ii;ii=ne[ii]){ int v=e[ii]; int S2=1ll*S1*val[v]%mod*fac[sz[u]-sz[v]]%mod*inv[sz[u]-sz[v]]%mod; for (int i=1;i<=n-sz[u]+1;i++) { sum[i]=sum[i-1]; if (!f[u][i]) continue; add(sum[i],1ll*S2*C(n-sz[v]-i,sz[u]-sz[v]-1)%mod*f[u][i]%mod); } for (int j=1;j<=n-sz[v]+1;j++) f[v][j]=sum[min(n-sz[u]+1,j-1)]; dfs2(v); } } int main(){ n=read(),init(); for (int i=2;i<=n;i++) add_e(read(),i); dfs1(1);f[1][1]=1;dfs2(1); for (int i=1;i<=n;i++) write(1ll*f[i][i]*fac[sz[i]]%mod*ival[i]%mod*C(n-i,sz[i]-1)%mod),pc(' '); fwrite(wbuf,1,wrp-wbuf,stdout); return 0; } ``` :::