P14016 [ICPC 2024 Nanjing R] 拓扑 题解 / 树的拓扑序个数的定理学习笔记

· · 题解

:::::info[题目基本信息] 考察：动态规划 DP，逆元，拓扑排序，组合数学，数学（省选/NOI-）。
题目简介：
给定一棵有 n 个点的数，它以 1 为根，设 f_i 为 i 点的父亲（特别地，定义 f_1=0），定义拓扑序为：一个排列 \{p_n\}，满足：

对于每个 i\in[1,n]，求有多少拓扑序满足 p_i=i（对 998244353 取模）。
数据范围：

时间限制：2s。
空间限制：1G。
::::: 结论：设 g_u 为只考虑 u 子树内时拓扑序个数，则 \displaystyle g_u=\frac{siz_u!}{\prod_{v\in\text{sub}_u}siz_v}，其中 \text{sub}_u 表示 u 子树内的结点构成的集合，siz_u 表示 u 的子树大小。
:::::success[证明]{open} 考虑数学归纳法。
当 siz_u=1 时，\displaystyle g_u=\frac{siz_u!}{\prod_{v\in\text{sub}_u}siz_v}=1，显然成立。
当 siz_u\ne 1 时，假设 \forall v\in\text{son}_u 都满足条件，其中 \text{son}_u 表示 u 点的儿子构成的集合。
那么根据定义，我们可以得到 g_u 的转移方程式为：

g_u=\frac{(siz_u-1)!}{\prod_{v\in\text{son}_u}siz_v!}\cdot\prod_{v\in\text{son}_u}g_v

我们将 \displaystyle g_v=\frac{siz_v!}{\prod_{w\in\text{sub}_v}siz_w} 代入推导：

\begin{aligned}g_u&=\frac{(siz_u-1)!}{\prod_{v\in\text{son}_u}siz_v!}\cdot\prod_{v\in\text{son}_u}g_v\\&=\frac{(siz_u-1)!}{\prod_{v\in\text{son}_u}siz_v!}\cdot\prod_{v\in\text{son}_u}\frac{siz_v!}{\prod_{w\in\text{sub}_v}siz_w}\\&=\frac{(siz_u-1)!}{\prod_{v\in\text{son}_u}\prod_{w\in\text{sub}_v}siz_w}\\&=\frac{(siz_u-1)!}{\prod_{v\in\complement{\text{sub}_u}\{u\}}siz_v}\\&=\frac{siz_u!}{\prod_{v\in\text{sub}_u}siz_v}\end{aligned}

证毕。
::::: 证明完了上面的结论，我们直接考虑 DP，设 f_{u,i} 为不考虑 u 子树（除 u 外）内的情况下，p_u=i 的方案数，显然可以得到 f_{1,1}=1，考虑从根到叶子进行 DFS，同时进行 DP。
考虑从 f_{u,i} 转移到 f_{v,j}（i<j），这时我们需要考虑 \complement_{\text{sub}_u}\text{sub}_v\cup\{u\} 这部分的贡献，注意到这部分变成了一个子树，我们就可以套用上面的结论，同时也要乘上 \displaystyle\binom{n-i-siz_v}{siz_u-siz_v-1} 表示在未填的位置上选出一些位置填上，我们就得到了转移方程式：

f_{v,j}=\sum_{i=1}^{j-1}f_{u,i}\binom{n-i-siz_v}{siz_u-siz_v-1}\cdot\frac{(siz_u-siz_v-1)!}{\prod_{v\in\complement{\text{sub}_u}\text{sub}_v\cup\{u\}}siz_v}

但是这个转移方程式实现出来是 \Theta(n^3)，注意到这个转移方程式跟 j 半毛钱关系都没有，我们考虑差分。
具体地，令 j\leftarrow j-1，我们得到：

f_{v,j-1}=\sum_{i=1}^{j-2}f_{u,i}\binom{n-i-siz_v}{siz_u-siz_v-1}\cdot\frac{(siz_u-siz_v-1)!}{\prod_{v\in\complement{\text{sub}_u}\text{sub}_v\cup\{u\}}siz_v}

两式相减，得到：

f_{v,j}-f_{v,j-1}=f_{u,j-1}\binom{n-j-siz_v+1}{siz_u-siz_v-1}\cdot\frac{(siz_u-siz_v-1)!}{\prod_{v\in\complement{\text{sub}_u}\text{sub}_v\cup\{u\}}siz_v}

自然得到：

f_{v,j}=f_{v,j-1}+f_{u,j-1}\binom{n-j-siz_v+1}{siz_u-siz_v-1}\cdot\frac{(siz_u-siz_v-1)!}{\prod_{v\in\complement{\text{sub}_u}\text{sub}_v\cup\{u\}}siz_v}

我们设 cnt_u=\prod_{v\in\text{sub}_u}siz_v，上式就变为：

f_{v,j}=f_{v,j-1}+f_{u,j-1}\binom{n-j-siz_v+1}{siz_u-siz_v-1}\cdot\frac{(siz_u-siz_v-1)!}{cnt_u\div siz_u\div cnt_v}

这个东西预处理阶乘和逆元就可以达到可接受的复杂度了，最后的答案 ans_u 就为：

ans_u=f_{u,u}\binom{n-u}{siz_u-1}\cdot \frac{siz_u!}{cnt_u}

时间复杂度为 \Theta(n^2)（实现较劣会变为 \Theta(n^2\log p)，其中 p 是模数，不知道能不能过），空间复杂度为 \Theta(n^2)。

code