Statement: 在 $1,2,\dots,N$ 是它的拓扑序的所有有标号外向树中，等概率两两独立随机得到 $K$ 个外向树，求它们互相同构的概率。

$1 \le N \le 2000,\;1 \le K \le 10^9$

你直接枚举 $N$ 个点无标号外向树，对应的有标号等价类的大小是其拓扑序 $\frac{N!}{\prod_{u=1}^N \operatorname{Size}(u)}$

除以每个结点的每个子树同构等价类的大小的阶乘（这些点之间在拓扑序里的出现顺序无所谓）。

答案是每个等价类大小的 $K$ 次幂之和再除以 $((N-1)!)^K$。

你定义一个无标号外向树的权是所有子树大小与每个结点的每个子树同构等价类的大小的阶乘的积的 $-K$ 次幂。记 $S_i$ 表示大小为 $i$ 的所有无标号外向树的权值构成的可重集，并记 $\sigma_k(S)=\sum_{c\in S}c^k$，你所求即为 $N^K\sigma_1(S_N)$。

列一下方程

$$ \begin{aligned} \sigma_k(S_n) &=n^{-Kk}[x^{n-1}]\prod_{i=1}^{\infty}\prod_{c\in S_i}\sum_{j=0}^{\infty}\frac{c^{jk}x^{ij}}{(j!)^{Kk}}\\ &=n^{-Kk}[x^{n-1}]\exp\left(\sum_{i=1}^{\infty}\sum_{c\in S_i}\sum_{j=1}^{\infty}h_{k,j}c^{jk}x^{ij}\right)\\ &=n^{-Kk}[x^{n-1}]\exp\left(\sum_{j=1}^{\infty}h_{k,j}\sum_{i=1}^{\infty}\sigma_{jk}(S_i)x^{ij}\right)\\ &=n^{-Kk}[x^{n-1}]\exp\left(\sum_{1\le ij

其中 $\sum_{i=1}^{\infty}h_{k,i}x^i=\ln\left(\sum_{i=0}^{\infty}\frac{x^i}{(i!)^{kK}}\right).$

不难发现我们只会用到 $1\le kn\le N$ 的 $\sigma_k(S_n)$，暴力做在线 $\exp$ 就是 $\mathcal O(N\log K+N^2)$ 的，当然我们也肯定可以做到 $\mathcal O\left(\frac{N}{\log N}\log K+N\log^2 N+M'(N)\log N\right)$，其中 $M'(n)$ 是在线卷积的最优复杂度。

前面的叙述隐藏了本题的思考过程，看起来做的很顺但实际过程中我遇到了很多困难，在此展开一下：面对无标号计数我们当然会考虑类欧拉变换，但是写出来才发现实际难点在于，对于同大小的无标号外向树我们还区分它的权值，因为实际在欧拉变换上用的是这个大小的所有无标号外向树权值的幂和。此处我曾错误认为这个信息量和记录可重集是一样的，均为关于 $N$ 超指数级的，当你用到的幂次是无穷大时确实如此，但此处经过分析发现不会用到超过 $N/n$ 次，因此这样就降下来了状态数，得到了如今的做法。