自动搬运

查看原文

来自洛谷，原作者为

	wlzhouzhuan 一直在路上。

搬运于2025-08-24 22:29:10，当前版本为作者最后更新于2021-02-18 11:50:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

设有标号二分连通图的 $\text{EGF}$ 为 $F(x)$ ，有标号二分图的 $\text{EGF}$ 为 $G(x)$ ，则：

$$G(x)=\sum\limits_{i}\frac{F^i(x)}{i!}=e^{F(x)}$$

发现 $F(x)$ 并不好求。令二分染色图的 $\text{EGF}$ 为 $H(x)$ ，则 $h_n=\sum\limits_{i=0}^{n} \binom{n}{i} 2^{i(n-i)}$ 。

给每个连通图的一个点钦定一个颜色，则该连通图所有点颜色确定，于是：

$$H(x)=\sum\limits_{i}\frac{2^iF^i(x)}{i!}=e^{2F(x)} $$

发现 $G(x)=\sqrt{H(x)}$ ，而

$$h_n=n!2^{\binom{n}{2}}\sum\limits_{i=0}^{n}\frac{1}{i!2^{\binom{i}{2}}}\frac{1}{(n-i)!2^{\binom{n-i}{2}}} $$

不难通过卷积得到 $H(x)$ 。

时间复杂度 $O(nlogn)$ 。