生成函数小结
看了jcvb的WC2015交流课件。虽然没懂后面的复合逆部分，但生成函数感觉受益良多。
指数生成函数
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。集合中大小为 i 的对象的权值是 \( a_i \) ，该集合的生成函数是 \( \sum\limits_{i>=0} \frac{a_i}{i!} x^i \)
一个重要式子： \( \sum\limits_{i=0}^{\infty} \frac{A^i}{i!} = e^A \) 。其中 A 可以是一个多项式。
对于有标号对象的计数。可以“拼接”，即 “大小为 i 的集合的带标号方案” 与 “大小为 j 的集合的带标号方案” ，想要维持相对大小地拼在一起变成 “大小为 i+j 的集合的带标号方案”。
“拼接” 的方法就是直接把两个 EGF 乘在一起。
一般来说，要取出 “有 n 个元素” 的方案，就是把 \( x^n \) 系数拿出来，乘上 n! 。这样就表示了组合数（因为集合的相对顺序无关，所以是组合数）。
但在 “拼接” 的过程中，不用担心 n! 的部分，直接把只有 \( \frac{1}{i!} \) 和 \( \frac{1}{j!} \) 的部分乘起来，就是正确的。
比如课件中举的例子：
\( 2^{\binom{n}{2}} \) 是 n 个点的简单无向图的方案数。直接乘了一个 \( \frac{1}{n!} \) ，只看系数的话，是莫名其妙的东西。但是把 \( c_n \) 也乘上 \( \frac{1}{n!} \) 作为 EGF 的系数，两者就可以直接 “拼接” 。最后的答案就是 \( C(x) \) 的 \( x^n \) 项系数再乘一个 \( n! \) 。
多项式 ln 相关
一个重要式子： \( \sum\limits_{i>=1} \frac{x^i}{i} = -ln(1-x) \)
更普遍的形式其实是： \( ln(1+x) = \sum\limits_{i>=1}\frac{(-1)^{i-1}}{i} x^i \)
与之相关的应用，这里举出课件上涉及的两个：
1.置换计数
轮换组成置换，适合用 EGF 的角度来看。
最后那步就是 \( exp(-ln(1-x)) = exp(ln(\frac{1}{1-x})) = \frac{1}{1-x} = \sum\limits_{i=0}^{\infty}x^i = \sum\limits_{i=0}^{\infty}\frac{i!}{i!}x^i \)
2.背包计数（无标号集合计数）
课件给出了三个版本的问题，并给出了第一个版本的解答。第二个版本就是自己写的，可能有错误，欢迎指正。第三个版本不太会……
不同种类算多种方案。
写出生成函数：\( \prod\limits_{i=1}^{n} ( \sum\limits({j>=0} x^{i*j} )^{a_i} \)
\(=\prod\limits_{i=1}^{n} ( \frac{1}{1-x^i} )^{a_i} \)
\(=exp( \sum\limits_{i=1}^{n} -a_i * ln( 1-x^i ) ) \)
\(=exp( \sum\limits_{i=1}^{n}a_i \sum\limits_{j>=1}\frac{x^{i*j}}{j} ) \) （这里用了那个式子）
\(=exp( \sum\limits_{j>=1} \frac{1}{j} \sum\limits_{i=1}^{n} a_i * x^{i*j} ) \)
\(=exp( \sum\limits_{j>=1} \frac{1}{j} A(x^j) ) \)
对于每个 j ， A(x) 只有 j 的倍数次项的系数需要关注。复杂度可以做到调和级数 nlogn 。
写出生成函数：\( \prod\limits_{i=1}^{n} ( 1+x^i )^{a_i} \)
\(=exp( \sum\limits_{i=1}^{n} a_i * ln(1+x^i) ) \)
\(=exp( \sum\limits_{i=1}^{n} a_i \sum\limits_{j>=1} \frac{(-1)^{j-1}}{j} x^{i*j} ) \)
\(=exp( \sum\limits_{j>=1} \frac{(-1)^{j-1}}{j} A(x^j) ) \)
写出生成函数：\( \prod\limits_{i=1}^{n} \sum\limits_{j=0}^{a_i} x^{i*j} \)
\(=exp( \sum\limits_{i=1}^{n} ln( \frac{1-x^{j*(a_i+1)}}{1-x^i} ) ) \)
然后就不会了……
这种背包计数的题，遇见两道，把自己的博客链接粘过来：
https://www.cnblogs.com/Narh/p/10396644.html
https://www.cnblogs.com/Narh/p/10405656.html
当初做这两个题的时候，用的是另一个式子来推导的：\( ( ln( f(x) ) )' = \frac{f'(x)}{f(x)} \)
写成那样，分子就用多项式的样子写求导，即把指数搬下来；分母就是正常的式子，和分子乘一下，整个就变成一个好看的多项式的样子了。
然后积分也是用多项式的样子写，把系数搬到指数上，推出来的结果就是一样的。
不过不管是这个式子，还是这回介绍的那个式子，都不太明白为什么能这样等于过去……
