前言
基础部分：多项式的高级运算
多项式与形式幂级数
多项式
多项式的定义见小学课本。
多项式的相关内容见 多项式的高级运算
形式幂级数
去除多项式“只有有限项”的限制。
[A(x)=sum_{ige0}a_ix^i
]
(x) 通常只是一个“形式”，不关心实际数值，“不用考虑与幂级数敛散性有关的问题”（不是很懂)，相当于用一个 (x) 的多项式挂起来一个数列。
组合计数问题
组合对象
满足某一性质（比如联通）的树、图、串等组成的集合。集合内每个元素都定义了“大小”，我们通常把“大小”作为下边，用 (A_n) 来表示大小为 (n) 的元素的数量。
普通生成函数（OGF）
序列 ({ a_0,a_1,a_2,...,a_i}) 的 OGF 为：
[A(x)=sum_{i ge 0} a_ix^i
]
也是比较常见的生成函数。常用于无标号的问题中。
常见数列的OGF(见《具体数学》）
[{1,1,1,...,1,...} :dfrac{1}{1-x}
]
[{1,0,0,1,0,0,...} : dfrac{1}{1-x^3}
]
[{1,2,3,...,n,...} : dfrac{1}{(1-x)^2}
]
[{{k-1 choose k-1},{k choose k - 1},..., {n + k - 1 choose k - 1},... } : dfrac{1}{(1-x)^k}
]
[{ 1,3,6,10,15,...} : dfrac{1}{(1-x)^3}
]
[{1,k,k^2,...,k^n,...} :dfrac{1}{1-kx}
]
[{{k choose 0},{k choose 1},...,{k choose n} } : (x+1)^k
]
指数生成函数（EGF）
序列 ({ a_i}) 的 EGF 为:
[A(x)=sum_{i ge 0} dfrac{a_i}{i!}x^i
]
EGF 善于处理有标号计数问题，能够解决运算时的“分配标号”问题。
常见数列的EGF（见珍珠)：
[{1,1,1,...}:e^x
]
[{ 1, -1, 1, -1, ..., (-1)^n}:e^{-x}
]
[{ 1,0,1,0,...,[2 mid n]}:dfrac{e^x + e^{-x}}{2}
]
[{ 0,1,0,1,...,[2
mid n] }:dfrac{e^x - e^{-x}}{2}
]
[{1,k,k^2,...,k^n}:e^{kx}
]
集合计数
有标号集合计数
因为有标号，我们应该使用EGF。但是，当我们打算算出由 (k) 个 (A(x))“拼接”而成的那个生成函数，就不能简单地 (A^k(x)) 了，因为我们不希望选择有顺序，因此答案是 (dfrac{A^k(x)}{k!})。
有意思的是，如果我们想要算出由任意个 (A(x))“拼接”而成的那个生成函数，它是：
[dfrac{A^0(x)}{0!} + dfrac{A^1(x)}{1!} + dfrac{A^2(x)}{2!} + ...
]
[large =sum_{i ge 0}dfrac{A^i(x)}{i!} = e^{A(x)}
]
即对 (A(x)) 做exp。
注意，这里除 (i!) 并不与处理标号时用的 (n!) 冲突。
到底为什么要除 (n!) 呢？这和 有标号 有关系吗？实际上是没关系的，除 (n!) 主要还是因为生成函数的乘法乘出来的东西是有序的多元组。就比如果三个多项式相乘，乘出来的结果可以看作一个个三元组((A,B,C))，表示从第一个多项式中揪出来一个元素 (A)，从第二个多项式中揪出来一个元素 (B)，从第三个多项式中揪出来一个元素 (C)，组成的三元组。其中(A + B + C = n) 的三元组数量记为 (f_n)，作为最终的三元组序列的第 (n) 个元素。即我们乘完以后的结果是一堆形如 ((A, B, C)) 的三元组。
然而我们真的要这样的结果吗？我们其实只要包含 (ABC) 三个元素即可，并不关心它是 ((A,B,C)) 还是 ((B,C,A))，即我们会在 ((A,B,C),(B,C,A)) 等排列中都把方案算一遍（都是有编号的），而我们只需要一个，那么就除个 (n!) 即可。
至于 (ABB) 这样的三元素是否一定会被算 (n!) 遍，即有序变无序为什么能直接除 (n!)，我也感觉很疑惑，可能是我小学没学好吧。（不懂不懂不懂不懂）
背包计数
有若干种物品，每种物品有无限件，体积为 (i) 的物品有 (a_i) 种。问装满 (j) 体积的背包的方案数。
直接搞出每种物品的OGF为 ({1,0,0,...,1,0,0,...} : dfrac{1}{1-x^i})，然后直接卷积即为答案。
正确性：刚才不是还要除 (i!)，现在怎么不除了？因为我们这里可以把 ((A,B,C)) 看作第一个物品为 (A)，第二个物品为 (B)，第三个物品为 (C)，这恰好符合我们的意图。即我们把集合问题转化成了序列问题。
现在我们继续化简式子：
[prod_{i=1}^n (dfrac{1}{1-x^i})^{a_i}
]
[=exp(ln (prod_{i=1}^n (dfrac{1}{1-x^i})^{a_i} ))
]
[= exp(sum_{i=1}^na_i * ln(dfrac{1}{1-x^i}))
]
[=exp(sum_{i=1}^n a_i sum_{j ge 1} 1/j * x^{ij})
]
[=exp(sum_{j ge 1} 1/j * sum_{i=1}^na_ix^{ji})
]
[=exp(sum_{j ge 1} 1/j * A(x^j))
]
对于 (exp) 里面的那个式子，对于每个 (j) 暴力算出所有小于等于 (n) 次的项的贡献即可。复杂度 (O(nlnn))。最后再 (exp) 一下就好。总复杂度为 (O(nlogn))。
其中第三行推到第四行需要一个式子：
[large lndfrac{1}{1-A} = sum_{j ge 1}1/j * A^j
]
这个式子比较重要，建议背过。下面不加说明地（并且不规范地）给出两种证明：
证明一：
[lndfrac{1}{1-A} = int(ln dfrac{1}{1-A})'
]
[=int ((1-A) * (dfrac{1}{1-A})')
]
[=int ((1-A) * (sum_{i}A^i)')
]
[=int ((1-A) * sum_{i ge 1} iA^{i-1})
]
[=int (sum_{i ge 1}iA^{i-1}-sum_{i ge 1}iA^i)
]
[=int (1 + sum_{i ge 2}iA^{i-1} - sum_{i ge 2} (i-1)A^{i-1})
]
[=int(1 + sum_{i ge 2}A^{i-1})
]
[=int(1 + sum_{i ge 1}A^{i})
]
[=int(sum_{i}A^i)
]
[=sum_{i ge 1}1 / i * A^i
]
证明二：
[lndfrac{1}{1-A} = int(ln dfrac{1}{1-A})'
]
[=int((1-A)(dfrac{1}{1-A})')
]
[=int((1-A)(-(1-A)^{-2})(-1))
]
[=int(dfrac{1}{1-A})
]
[=sum_{i ge 1}1 / i * A^i
]
练习：01背包计数：
[prod_{i}(1+x^i)^{a_i}
]
[=exp(sum_{i}a_iln(1+x^i))
]
[=exp(sum_{i}a_i * (-sum_{j ge 1}1 / j * (-x^i)^j)
]
[=exp(-sum_{j ge 1}1/j * (-1)^j sum_{i}a_ix^{ji})
]
[=exp(-sum_{j ge 1} 1/ j * (-1)^jA(x^j))
]
例题：P4389 付公主的背包
环的计数
有标号环计数
与有标号集合计数类似，(n) 个环拼接的结果是 (n) 元组而不是环，最后要除 (n)，因为同一种方案我们算了 (n) 次。
由 (n) 种大小不同的元素各取任意多个组成环的EGF是：
[sum_{i}A^i(x)/i=ln(dfrac{1}{1-A(x)})=-ln(1-A(x))
]
例题：基环树计数
(n) 个点的基环树有多少？点有编号，无重边自环。
首先要知道一个常识：由 (n) 个点（有编号）组成的有根树数量为 (n^{n-1}) 个， 无根树为 (n^{n-2}) 个。
有根树EGF为：
[T(x)=sum_{i ge 1}dfrac{i^{i-1}}{i!}x^i
]
基环树可以看作由大于等于 3 棵有根树组成的环，并且可以翻转。因此答案为：
[1/2 * sum_{i ge 3}T^i(x)/i
]
[=1/2 * (-ln(1-T(x)) - T(x) - T^2(x)/2)
]
[=-ln(1-T(x))/2 - T(x)/2 - T^2(x)/4)
]
项链计数
现有 (n) 种重量不同的珠子，第 (i) 种珠子的重量为 (i)，有 (a_i) 种颜色。问串成的总重为 (k) 的项链的方案数。项链可旋转，不可翻转。
现在我们也不知道多算了几倍，不好直接除一个数作为答案。
项链？旋转？Polya定理！
众所周知，(n) 个珠子，(c) 种颜色的本质不同项链数为：
[1/nsum_{i=0}^{n-1}c^{(n,i)}
]
不过现在 (c) 由重量决定，与 (x^i) 前的系数有关。那么 (n) 个珠子组成的项链的OGF为：
[1/n * sum_{i=0}^{n-1}(A(x^{frac{n}{g}}))^{g},g=(n,i)
]
其中 (n/g) 是“环”的大小，(A(x^{n/g})) 表示将 (A(x)) 的所有元素重量翻了 (n/g) 倍的 OGF（毕竟我们要求一个“环”的颜色都相同，可以看作一个重量为原来的 (n/g) 倍的元素）
注意，这是个 OGF，第 (i) 项系数表示总重为 (i) 的 (n) 个珠子的方案数。（这里不懂，为什么 (g) 次方以后不用除阶乘，这不是集合吗？好像真不是...Polya定理里面的这些“环”可以看作“序列”，应该是有顺序的）
好，我们继续推式子：
[1/n * sum_{i=0}^{n-1}(A(x^{frac{n}{g}}))^{g}
]
[=1/n * sum_{d mid n}A(x^{n/d})^d sum_{i=0}^{n-1}[(i,n)=d]
]
[=1/n * sum_{d mid n} A(x^{n/d})^d varphi(n/d)
]
[=1/n * sum_{d mid n} A(x^d)^{n/d} varphi(d)
]
这是 (n) 个珠子的 OGF。但是我们不限制珠子数，那么我们把所有的 (n) 的 OGF 加起来就好了。
[F(x)=sum_{n ge 1}1/n * sum_{d mid n} A(x^d)^{n/d} varphi(d)
]
[=sum_{d ge 1} varphi(d) sum_{n ge 1} frac{1}{nd} * A(x^d)^n
]
[=sum_{d ge 1} frac{varphi(d)}{d} sum_{n ge 1}1/n * A(x^d)^n
]
[=sum_{d ge 1} frac{varphi(d)}{d} * (-ln(1-A(x^d)))
]
同样，(A(x^d)) 的有用的项并不多，因此算出 (ln(1-A(x))) 后依次代入 (x^d)，暴力求和即可。
复杂度：(O(nlogn))
参考文献