P7364 题解
wlzhouzhuan
·
·
题解
设有标号二分连通图的 \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) 。