ZJOI2018 树

给定 (n,k)，按照如下规则生成随机树：

对于 (ige 2)，(i) 的父亲 ([1,i)) 中随机。

求生成 (k) 棵树全部同构的概率。

(nle 2000,kle 10^9)

Solution

首先我们将所有大小为 (n) 的等价类进行标号，设分别有 (1sim m) 个，设其大小为 (a_1sim a_m)，则可知题意需要求的为：

[frac{1}{((n-1)!)^k}sum_{i=1}^m a_i^k ]

我们不妨设 (dp_n) 表示 (sum_{i=1}^m a_i^k)

考虑计算 (dp_n)，事实上他存在另一个组合解释，即所有树生成概率相同，随机 D (k) 次，D 出来的树均相同的概率。

我们考虑将根节点拿去，转为考虑森林的情况，区别于传统计数问题，我们无法轻易的计算答案，因为此处的森林是无序的。

我们考虑按照此规则生成森林：

每次将最大的一批树拿去，然后转为 sub-problem

不妨设 (tmp_{i,j}) 表示当前所有树的大小均不超过 (i)，所有树的大小之和为 (j) 的情况下的贡献。

那么 (dp_{i}=tmp_{i-1,i-1})

我们枚举大小为 (i) 的树的数量（显然因为同构内部需要相同）由于是无标号同构判定，我们给其任意的分配标号（注意有 (k) 轮)：

[tmp_{i,j}=sum_{i imes u+v=j}tmp_{i-1,v} imes f_{i,u}inom{j}{i imes u}^k ]

只需要计算 (f_{i,u}) 表示仅由 (u) 棵大小为 (i) 的树组成的森林对答案的贡献之和。

这里需要注意的一点是，答案是无标号的，我们先来形式化的描述一下这个问题：

考虑这 (u) 棵树可以描述为 (u) 个元素构成的序列，设大小为 (i) 的树有 (m) 个等价类，大小分别为 (a_1sim a_m)，我们考虑答案可以描述为：

长度为 (u) 的序列，每个元素在 ([1,m]) 中穷举，统计本质不同的序列的贡献之和，其中序列的贡献分成两个 Part，其一为标号的分配，其二为 (a_i) 的乘积。

我们先考虑标号的分配：我们现在有 (i imes u) 个标号，考虑分配标号的时候，看起来答案似乎就是：(inom{i imes u}{i,i,i,...i})

然而并不是，我们需要注意到假设两棵树同构，在此标号分配意义下会被判定为不同构。

换而言之同构的树，或者说相同的颜色，彼此之间的排布顺序应当是无序的，于是设第 (i) 种等价类出现了 (c_i) 次，答案应当为 (inom{i imes u}{i,i,i...,i}frac{1}{(c_j)!})

于是外部的贡献为 (frac{(iu)!}{(i!)^u})，此时需要注意到这类贡献会产生 (k) 次，于是标号分配处的贡献为 (frac{(iu)!^{k}}{i^{uk}})

我们将一个长度为 (u) 的序列设为元素 (x)，并考虑通过群论的语言来描述答案，设 (x) 的轨道为 (orbit(x))，并为每个 (x) 设 (omega(x)=frac{1}{prod c_i!})，则答案为：

[frac{(iu)^k}{i^{uk}}sum_{xin m^u}prod a_i^k omega(x)frac{1}{orbit(x)} ]

由于每个元素附带了额外的权值，我们无法通过传统的 Polya/Burnside 定理来计算答案，我们考虑拓展 Burnside 定理：

考虑为每个置换赋予权值 (w(p))，并基于如下构造，设 (fix(p)) 表示置换 (p) 意义下的不动点集，我们使得：

[sum_{xin fix(p)}frac{w(p)}{G}=frac{omega(x)}{orbit(x)} ]

成立，则答案可以描述为：（其中 (G) 为群的大小即 (u!)（不过在不确定的情况下可以设））

[frac{(iu)^k}{i^{uk}}sum_{xin m^u}prod a_i^k sum_{xin fix(p)}w(p) ]

忽略前面的部分，答案转为：

[sum_{pin u!}w(p)sum_{xin fix(p)}prod a_i^k ]

显然，我们有观察，每个轮换的贡献是独立可乘的。那么对于每个轮换，设其大小为 ( ho_j)，答案可以描述为：

[frac{1}{G}sum_{pin u!}w(p)prod_{ ho_1+ ho_2+...=p} igg(sum a_i^{ ho_jk}igg) ]

事实是，第二个 Part 的式子我们从来没有计算过，此时我们需要扩充我们预处理的信息量，令：

(dp_{i,o}) 表示所有大小为 (i) 的树的等价类的 (sum a_i^{jk}) 之和，则此时我们需要预先修正我们所有的计算式：

我们引入 (tmp_{i,j,o}) 并为此有：

[tmp_{i,j,o}=sum_{iu+v=j}tmp_{i-1,v,o} imes f_{i,u,o}inom{j}{iu}^{ok} ]

我们修正 (f_{i,u,o}) 的计算式：

[f_{i,u,o}=frac{(iu)^{ok}}{i^{ouk}}sum_{xin m^u}prod a_i^{ok} omega(x)frac{1}{orbit(x)} ]

其中 (omega(x)=frac{1}{prod (c_j)!^{o}})，类似的，我们可以为每个 (o) 构造 (w(p))

考虑计算式：

[f_{i,u,o}=frac{(iu)^{ok}}{i^{ouk}} imes frac{1}{G}sum_{pin u!}w(p)prod_{ ho_1+ ho_2+...=p} igg(sum a_i^{ ho_jok}igg) ]

[f_{i,u,o}=frac{(iu)^{ok}}{i^{ouk}} imes frac{1}{G}sum_{pin u!}w(p)prod_{ ho_1+ ho_2+...=p} dp_{i, ho_jo} ]

注意 (dp_{i,o}=tmp_{i-1,i-1,o})

不失一般性，我们考虑到 (p) 可以拆分为若干个轮换的和，我们不妨将 (w(p)) 定义为 (prod w( ho_i))

则此时有：

[sum_{xin fix(p)}frac{w(p)}{G}=frac{omega(x)}{orbit(x)} ]

考虑什么情况下 (p) 为 (x) 的不动点，显然可以将每个颜色拆开考虑，设第 (i) 种颜色数量为 (c_i)，我们设 (F_{x}) 表示某种颜色有 (x) 个时的贡献，则此时有：

[frac{1}{G}prod_{i=1}^mF_{c_i}=frac{1}{u!} imes frac{1}{prod (c_j!)^{ok-1}} ]

于是有：（(G=u!)）

[F_{c_i}=frac{1}{c_j!^{ok-1}} ]

考虑到对置换的处理通常是枚举轮换，设大小为 (i) 的轮换有 (t_i) 个，则其对答案的贡献为 (frac{1}{t_i!i^{t_i}})（后面的贡献来自 (frac{(i-1)!}{i!})）：

[F_{x}=x!sum_{i imes t_i=x}frac{w(i)^{t_i}}{i^{t_i}(t_i)!}=frac{1}{x!^{ok-1}} ]

故

[sum_{i imes t_i=x}frac{w(i)^{t_i}}{i^{t_i}(t_i)!}=frac{1}{x!^{ok}} ]

我们设 (F_i(x)=sum frac{w(i)^jx^{ij}}{i^jj!})，设 (G_i(x)=frac{w(i)x^i}{i})，则 (F_i(x)=e^{G_i(x)})

方便起见将之前的 (x) 统一改为 (n) 并用 (x) 代表形式幂级数，故有：

[prod F_i(x)[x^n]=frac{1}{n!^{ok}} ]

设 (G(x)=sum G_i(x)) 即：

[exp(G(x))[x^n]=frac{1}{n!^{ok}} ]

设 (H(x)=sum frac{x^i}{i^{ok}})，则 (G(x)=ln H(x))

此时，我们得到了每个轮换的 (w( ho))

接下来我们考虑计算 (f_{i,u,o})，根据转移有：

[f_{i,u,o}=frac{(iu!)^{ok}}{i!^{ouk}} imes frac{1}{u!}sum_{pin u!}w(p)prod_{ ho_1+ ho_2+...=p} dp_{i, ho_jo} ]

我们考虑拆分后式，平凡的，我们枚举每个置换的大小并考虑大小为 (i) 的置换被使用了 (t_i) 次，则有:

[f_{i,u,o}=frac{(iu!)^{ok}}{i!^{ouk}} imes frac{u!}{u!}prod_{j imes t_j=u}frac{w_o(j)dp_{i,jo}^{t_j}}{t_j!j^{t_j}} ]

类似的，设 (G_i(x)=frac{w_o(j)dp_{i,jo}x^j}{j})，则 (e^{G_i}) 可以表达单个后式，后式即 (prod e^{G_i(x)}=e^{G(x)})，其中 (G(x)=sum frac{w_o(j)dp_{i,j}x^j}{j})

我们有边界 (tmp_{1,?,?}=1)，且有转移：

(dp_{i,o}=tmp_{i-1,i-1,o})
需要求得 (dp_{n,1})
计算 (tmp_{i,j,o})

[tmp_{i,j,o}=sum_{iu+v=j}tmp_{i-1,v,o} imes f_{i,u,o}inom{j}{iu}^{ok} ]

计算 (f_{i,u,o})：
对于某个 (o) 预处理 (w_o(i)) 依此：

设 (H(x)=sum frac{x^i}{i!^{ok}})，则 (G(x)=ln H(x))，其中 (G(x)[x^i]=frac{w_o(i)}{i})

转移 (f_{i,u,o})

设 (G_{i,o}(x)=sum_j frac{w_o(j)dp_{i,jo}x^j}{j})，则 (f_{i,u,o}=frac{(iu!)^{ok}}{i!^{ouk}} imes exp(G_{i,o}(x))[x^u])

最后，我们需要知道那些状态是有效的：

考虑到 (f_{i,u,o}) 满足 (iule n)，同时计算其需要知道 (dp_{i,uo}) 对应着需要知道 (f_{i-1,frac{n}{i-1},uo})

对于 (f(i,u,o)) 会计算 (dp(i,osim uo))

对于 (dp(i,o)) 会计算 (f(i',j',o)) 且有 (i'j'le i)

显然三个维度的乘积始终小于 (n)

至此，我们计算 (tmp) 的复杂度为：

[sum frac{n^2}{i}=n^2log n ]

我们计算 (f) 数组的复杂度为：

[sum_{i,j}frac{n^2}{(ij)^2}=n^2 ]

我们计算 (w_o(i)) 的复杂度为：

[sum frac{n^2}{i^2}=n^2 ]

总体复杂度 (mathcal O(n^2log n))

tips：

暴力 (ln)

[B_n=A_n-frac{1}{n}sum_{i=1}^{n-1} B_i imes i imes A_{n-i} ]

暴力 (exp)

[[z^{n}]B(z)=frac{1}{n}sum_{k=1} k[z^{k}]A(z) imes B(z)[z^{n-k}] ]