P10002 [集训队互测 2023] 树哈希

· · 题解

/bx/bx/bx zky！！！

题意

给定常数 q，定义一棵以 1 为根的有根树 T 的 s(T) 为 T 中本质不同的子树数量，定义其权值为 q^{s(T)}。给定 n，对于 i = 1, \dots, n 求所有大小为 i 的有标号有根树的权值之和对 P 取模的结果。

## 分析 首先不妨考虑去掉以 $1$ 为根的限制，改为任意根，最后在将方案数除以 $n$。 ### 算法一 考虑爆搜出所有无标号有根树，在乘上对应的设置标号的方案数。具体的考虑维护大小为 $i$ 的本质不同**森林集合**以及**树集合**，那么在大小为 $i - 1$ 的一种森林中加入一个根即可推出大小为 $i$ 的所有本质不同树，递推维护森林集合就可以了。 复杂度 $\mathcal O(n^{n - 1})$。不知道能多少分？ ### 算法二 我会容斥！ 定义点同构，当且仅当对应的子树同构。 考虑按子树大小从小到大确定等价关系，可以将原树划分为若干个等价类集合。如果将每个等价类缩为一个大点的话，那么显然这些大点形成了一个**有根 DAG**，可以直接计数。 但是如果随意钦定集合然后连边的话，势必会出现重复（等价的两个集合没有合并），所以考虑先**钦定**若干个集合实际上是相同的，这样**不同的新集合之间**就没有限制了！ 现在考虑计算连边的方案数： 记 $cnt_i$ 为第 $i$ 个等价类的大小，$f_i$ 为 $cnt = i$ 的等价类数量。考虑到每个集合内的点是无序的，所以可以将定标的方案数写成 $\dfrac{n!}{\prod\limits_{i}cnt_i!}$，注意到要除掉定根的 $n$，于是变成 $\dfrac{(n - 1)!}{\prod\limits_{i} cnt_i!}$。 对于除了根以外的任意集合，都要满足入边的 $cnt$ 之和等于 $cnt_i$。接下来按照 $cnt$ 从小到大，依次确定入边。 假设当前考虑到 $cnt = i$，分讨： - $i = 1$，必须形成一棵有根树，贡献 $q^{f_1} f_1^{f_1 - 1}$； - $i > 1$，按入边类型分类： - 由一个 $cnt = i$ 的点连边，这种情况相当于形成了一个森林； - 由若干个 $cnt < i$ 的点连边，相当于是森林中的若干个根，需进一步讨论。 我们考虑枚举向它连边的 $cnt = p$，以及等价类中的每个点向当前等价类连 $j$ 条边，由于儿子之间无序，所以方案数乘上 $\dfrac{1}{j!}$。考虑写成 EGF 的形式就是：$A(x) = \displaystyle{\prod_{p < i} (\sum_{j} (\dfrac{x^{j}}{j!})^p})^{f_p}$，组成一个等价类集合的方案数就是 $[\dfrac{x^i}{i!}]A(x)$。要求 $i > 1$，所以要去掉常数项。考虑带上 $q$ 的贡献，写成 $B(x) = q(A(x) - 1)$。 注意到 $[\dfrac{x^i}{i!}]$ 中的 $i!$ 与初始的方案数重复了，所以考虑简化成最后方案数乘以 $(n - 1)!$，转而提取 $[x^i]$ 项系数。 注意要乘上确定 $k$ 个根的方案数，使用扩展卡莱公式即可。 然后我们容斥了若干个集合实际相同，设计一个容斥系数。划分为 $t$ 个集合的容斥系数的一个今典套路是转换成一张**无向图**：**有连边**表示两个点**相同**，想要求**每个点独立**的方案数，于是一个划分为 $t$ 个小集合的大集合容斥系数就是大小为 $t$ 的无向**连通图**的 $-1$ 的边数次方之和。 这个问题可以先考虑**不要求联通**的情况，则方案数为 $\sum\limits_{e} (-1)^{|e|} = \sum\limits_{i} \dbinom{\frac{t(t - 1)}{2}}{i}(-1)^i$，这个方案数在 $t(t - 1) / 2 > 1$ 时为 $0$，所以不要求联通的组合类可以写成 $\mathcal F(x) = 1 + x$，所以**联通图**的 EGF 就是 $\mathcal T(x) = \ln(\mathcal F)$，提取 $[\dfrac{x^i}{i!}]$ 项系数就是 $(-1)^{t - 1} (t - 1)!$。 所以有实际的（带容斥系数）OGF 是 $G(x) = \sum\limits_{i \ge 1} \frac{(-1)^{i - 1}(i - 1)!}{i!} B^i(x)$。除以 $i!$ 是因为 $B^i$ 和容斥系数的标号重复了。发现 $G(x) = \ln(1 + B(x))$。 最后，由于同 $cnt$ 的集合之间无序，所以乘上 $\prod\limits_{i} \dfrac{1}{f_i!}$。 记 $\pi(n)$ 为 $\sum\limits_{i} if_i \le n$ 的不同 $\{f\}$ 数量，则复杂度是 $\mathcal O(\pi(n)\text{poly}(n))$ 的，这个 $\text{poly}(n)$ 大概是 $\mathcal O(n^2 \ln n)$ 级别的，实际要更低，笔者实现可以通过 $n = 58$ 。 ### 算法三 我会 DP！ 考虑按 $cnt$ 从小到大加入，记录在**接下来过程中**还会向后连至少一条边的点的 $cnt$ 集合以及总点数。 但是直接连边可能会导致一些点始终都没连边，于是考虑再进行容斥，容斥一个集合的点在接下来的过程中实际没有出现，容斥系数 $(-1)^{|S|}$。 于是我们现在的过程是，先容斥一个集合不出现，然后新加入一种 $cnt$ 并计算连边方案，最后去除不再连边的点集。 注意到 DP 的好处在于，由于集合中的每一个点都**还要再连边**，所以 $\sum\limits_{i} cnt_i \le \dfrac{n}{2}$。 复杂度 $\mathcal O(\pi(\dfrac{n}{2}) \text{poly}(n))$，这里面的 $\text{poly}(n)$ 大概是 $\mathcal O(n^3) \sim \mathcal O(n^4)$ 的，由于指数级 $\pi(\dfrac{n}{2})$ 的优势，笔者实现可以通过 $n = 59$！ ### 算法四 我会更牛的 DP！ 发现有一些特殊的情况继续进行高复杂度的集合划分容斥就显得愚蠢了，比如说**叶子**！ 我们考虑修改状态为接下来过程中至少还要**连一个非叶节点**的集合，这样子就将复杂度降低至 $\pi(\dfrac{n}{3})$。 进一步的，我们可以类比的设置一个阈值 $B$，爆搜出所有大小 $\le B$ 的树集合，将状态修改为至少还要连一个子树大小 $> B$ 的点，这样子状态数降为 $\pi(\dfrac{n}{B + 2})$。 注意到此时的一些限制：要求每个点要么继续连边，要么 $\le B$ 的子树集合之和 $> B$；计算 $< B$ 的 $q$ 的贡献。这引申出两个问题： 1. 我们在第二步，考虑 $cnt = i$ 的连边时，可能会将子树和大小 $< B$ 的集合钦定不再向后连边； 2. 我们如果枚举用到的子树集合可能会不足。 于是我们分别考虑容斥： 1. 对于第一个问题：相当于钦定一个点集的点子树和小于 $B$ 且弃置，注意到这个集合一定是形成的森林的**叶子集合**的子集，所以方案任然不难用 Prüfer 序列计算； 2. 对于第二个问题：考虑转化成钦定只能出现一个集合的树，预处理出这个集合即可。 于是最终复杂度为 $\mathcal O(\pi(\dfrac{n}{3}) 2^{F(B)} \text{poly}(n) + H(B))$，其中 $F(B)$ 是大小小于 $B$ 的有根树集合的大小，$H(B)$ 是搜索的复杂度，沿用 zky 标算选取 $B = 3$，可以秒杀 $n = 100$！！！ ## Code ### 算法一 ~~懒狗自己实现去！~~ ### 算法二 提交记录：<https://qoj.ac/submission/448090>。 ### 算法三 提交记录：<https://qoj.ac/submission/449911>。 ### 算法四 提交记录：<https://qoj.ac/submission/450601>。 ## 致谢 /bx/bx/bx [@CharlieV](https://www.luogu.com.cn/user/340903)！ /bx/bx/bx [@AFewSuns](https://www.luogu.com.cn/user/224336)！