\(e^{f(x)}\)的组合意义：
设\(f(x)=\sum_{i=1}^{\infty}\frac{a_i}{i!} x^i\)为一个关于数列\(\{a_n\}\)的指数型生成函数，\(e^{f(x)}\)为关于数列\(\{b_n\}\)指数型生成函数，则\(b_n\)的组合意义为：将n个有标号的点无序划分为若干个点集，设每一个点集的大小分别为\(sz_1,sz_2,...\)，那么将所有划分方案中的\(\prod a_{sz_i}\)加起来就是\(b_n\)的值。
注意\(b_n=n!*e^{f(x)}[x^n]?\)，写代码时最后要乘一个\(n!?\)
求n个点的简单(无重边无自环)无向连通图数目.
\(n\leq 50\)
\(n\leq 10^5\)
?
方法1
主要思路：
设f[i]为i个点的答案，有
\[f[i]=2^{C_i^2}-\sum_{j=1}^{i-1}C_{i-1}^{j-1}f[j]*2^{C_{i-j}^{2}}\]
这就是一个\(O(n^2)\)的dp，然后考虑生成函数优化
\[\frac{f[i]}{(i-1)!}=\frac{2^{C_i^2}}{(i-1)!}-\sum_{j=1}^{i-1}\frac{f[j]}{(j-1)!}*\frac{2^{C_{i-j}^{2}}}{(i-j)!}\]
\[\sum_{j=1}^{i}\frac{f[j]}{(j-1)!}*\frac{2^{C_{i-j}^{2}}}{(i-j)!}=\frac{2^{C_i^2}}{(i-1)!}\]
设\(f(x)=\sum_{i=1}^{\infty}\frac{f[i]}{(i-1)!}\)
\[g(x)=\sum_{i=0}^{\infty}\frac{2^{C_{i}^2}}{i!}x^i\]
\[h(x)=\sum_{i=1}^{\infty}\frac{2^{C_{i}^2}}{(i-1)!}x^i\]
则有\(f(x)*g(x)=h(x)\)，所以\(f(x)=\frac{h(x)}{g(x)}\)
多项式求逆即可。
??
?
另一解法：
设无向连通图个数的EFG（指数型生成函数）为F(x)，无向图个数的EFG为G(x)
即\(F(x)=\sum_{i=1}^\infty \frac{f[i]}{i!}x^i,G(x)=\sum_{i=0}^ \inf \frac{2^{C_i^2}}{i!}x^i\)
有\[e^{F(x)}=G(x)\]
\[F(x)=lnG(x)\]
求\[\sum_{S}\prod_{i=1}^{n-|S|}(sz_i^2*K)\]
其中\(n\)为点数，\(S\)为任意一棵森林的边集，\(sz_i\)为每个连通块的大小，\(K\)为常数。
设答案的EFG为F(x)，\(G(x)=\sum_{i=1}^\infty \frac{i^2*K}{i!} x^i\)
则\(F(x)=e^{G(x)}\)
\(ans=n!*F(x)[x^n]\)
题意：定义好的二叉树为所有节点的权值都在集合\(D\)中的二叉树，一棵二叉树的权值为所有节点的权值和，先给定集合\(D\)，求对于所有\(s\in [1,m]\)，权值为s的好的二叉树有多少棵，两棵二叉树不同当且仅当它们结构不同或对应位置节点权值不同，\(|D|,m\leq 10^5\)。
?
这类问题最好用的性质就是二叉树的子树也是二叉树了。
设答案的普通型生成函数为\(f(x)\)，\(g(x)=\sum_{i\in D}x^i\)
有
\[f^2(x)*g(x)+1=f(x)\]
即枚举根节点的权值，然后计算左右两棵子树的方案数。
接下来有两种解法：
解方程，得
\[f(x)=\frac{1\pm\sqrt{1-4g(x)}}{2g(x)}=\frac{2}{1\mp\sqrt{1-4g(x)}}\]
因为分母常数项不能为零，所以
\[f(x)=\frac{2}{1+\sqrt{1-4g(x)}}\]
移项得\(f^2(x)*g(x)-f(x)+1=0\)
设\(\delta(f(x))=f^2(x)*g(x)-f(x)+1\)
就是一个求函数零点问题，具体地
\[f(x)=f_0(x)-\frac{f_0^2(x)*g(x)-f_0(x)+1}{2f_0(x)g(x)-1}\]
倍增求即可。
原文：https://www.cnblogs.com/lishuyu2003/p/12145303.html