UOJ Logo zhouziheng的博客

博客

UOJ NOI Round #5 Day1T2 的另一个思路

2021-07-20 11:04:33 By zhouziheng

我们考虑 Burnside 引理。设 $X_k$ 是所有染 $k$ 个节点的方案,$G$ 是所有树同构意义下的置换群。我们要计算的是 $G$ 意义下,$X_k$ 中所有等价类的数量。由 Burnside 引理可知,这等于 $G$ 中每个置换下 $X_k$ 中不动点数量的平均值。

考虑对于每个特定的 $G$,如何计算 $G$ 的不动点数量。设在这个置换意义下,原树上有 $i$ 个点置换之后还是自身,其余 $n-i$ 个点置换之后不再是自身。那么可以发现,染色的 $k$ 个点只能在 $i$ 个不动的点中选择,总方案数为 $A_{i}^{k}=\dfrac{i!}{(i-k)!}$。这引导我们:如果我们能对每个 $i$,计算出有多少个置换恰能使得原树上有 $i$ 个节点不动,我们就能快速求出原题答案。

同官方题解中算法 4,我们以原树重心为根(方便起见假定树只有一个重心,两个重心的情况是类似的)。可以发现,$G$ 中所有置换等于每个节点同构子树的置换的乘积。我们记 $F_u(x)=\sum_{p=0}^{\mathrm{sz}(u)}f_{u,p}x^p$,其中 ${\mathrm{sz}(u)}$ 表示节点 $u$ 子树大小,$f_{u,p}$ 表示 $u$ 为根的子树中恰有 $p$ 个不动点的方案数。方便起见,称 $F_u(x)$ 是 $u$ 子树的生成函数。我们需要考虑计算一棵出现了 $k$ 次的、生成函数为 $F$ 的子树对答案的贡献 $\mathrm{calc}(F,k)$。

我们有

$$ \mathrm{calc}(F,k)=\sum_{i=0}^kF^i\binom{k}{i}D_{k-i}\mathrm{tot}(F)^{k-i} $$

其中 $D_i$ 是错排数,$\mathrm{tot}(F)$ 表示该子树中所有置换总数(即 $F(1)$ 的值)。组合意义:枚举有多少棵子树在这个置换中没有改变,设有 $i$ 棵,那么这 $i$ 棵树的生成函数是 $F^i$。同时,我们要考虑剩下 $k-i$ 棵树的方案数,显然这 $k-i$ 棵树构成了错排,同时要把这些树里的方案数全部乘进去。

计算 $\mathrm{calc}$ 可以类似官方题解中的分治 NTT 做到 $O(k\deg{F}(\log k\deg{F})\log k)$。最终对原问题的计算也可以参考官方题解轻重链剖分的做法,做到总复杂度 $O(n\log^3 n)$ 或者 $O(n\log^2 n)$。

评论

alpha1022
orz zzh
alpha1022
听说这个做法和 ei 一样
zhltao
感觉这个做法很有精神
Harrya_Gryffindor
zzh 太强啦! srO zzh Orz

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。