学习笔记·多项式专题(四)

这篇文章是数数题推柿子指不着北。

例题$1$

Luogu P4841(有标号无向连通图计数)

这里先给大家讲一个普遍的结论:

假设对于某符合条件的点有标号的图的个数$\texttt{EGF}$为$F(x)$,联通的符合条件的点有标号的图的个数的$\texttt{EGF}$为$G(x)$,则

证明如下

枚举连通块。考虑到$f_i$已经消除了标号的影响,而$G(x)^k$却由于乘法没有消除标号的影响,所以有

至于为什么是$G(x)^k$的话,背包计数的原理。每个连通图看作是一个花费节点数的容量的物品就好了。

这对于后面的一个叫做有标号荒漠计数的题有用。

所以在这个题里面$F(x)$很好求,有

然后,$G(x)=\ln F(x)$,于是就求完了qwq。