组合数学 - 浪店

169 words

1 minute

组合数学

2026-03-26

Math

组合数学

/

数学

P5900 无标号无根树计数无根树计数比较困难，我们考虑 $f_i$ 表示 $i$ 个点的有根树的个数
$F(x)=\sum_{i=1}f_ix^i$
那么，根据 $Euler$ 变换
$F(x)=x\varepsilon(F(x))$

\begin{align} F(x)&=x\varepsilon(F(x))\\ F'(x)&=(x\exp(\sum_{j=1}\frac{F(x^j)}{j}))'\\ &=\exp(\sum_{j=1}\frac{F(x^j)}{j})+x\exp(\sum_{j=1}\frac{F(x^j)}{j})\sum_{j=1}F'(x^{j})x^{j-1}\\ xF'(x)&=F(x)+F(x)\sum_{j=1}F'(x^{j})x^{j}\\ G(x)&=\sum_{j=1}F'(x^{j})x^{j}=\sum_{i=1}g_ix^i\\ F'(x)&=\sum_{i=1}if_ix^{i-1}\\ F'(x^j)x^j&=\sum_{i=1}if_ix^{j(i-1)}x^j=\sum_{i=1}if_ix^{ij}\\ \sum_{i=1}g_ix^i&=\sum_{i=1}if_ix^{ij}\\ g_n&=\sum_{d\mid n}df_d\\ xF'(x)&=F(x)+F(x)G(x)\\ xF'(x)&=\sum_{i=1}if_ix^{i}\\ nf_{n}&=f_n+\sum_{k=1}^{n-1}f_kg_{n-k}\\ f_n&=\frac{1}{n-1}\sum_{i=1}^{n-1}f_ig_{n-i}\\ \end{align}

可以分治 $FFT$ 解决求出 $f_i$
考虑如何计算无根树的个数
对于奇数的 $n$ ，每颗树只有一个重心，那么把根当做重心，即为所有的无根树
$f_{n}-\sum_{i=\frac{n+1}{2}}f_if_{n-i}$
对于偶数的 $n$ ，可能存在两个重心，还需减掉 $\binom{f_{\frac{n}{2}}}{2}$
如果两个大小为 $\frac{n}{2}$ ，同构，则只会被计算一次，如果不同构，则会被计算两次
P3784 [SDOI2017] 遗忘的集合

工科数学分析-3.26

test03