形式幂级数与集合幂级数的补充内容

由于$slide.tex$的笔记本不带在身边，所以在这里临时记录。 ## 形式幂级数 ### 背包问题的生成函数 众所周知，背包问题的生成函数是一堆$\sum\times$起来，譬如$\prod\sum_{i=0}^\infty x^{vi}$就是无限背包的生成函数。 但是我们显然不可能做$O(n)$遍$NTT$，于是我们得把它取$\ln$然后再加起来再$\exp$回去来加速运算，而且这个$\ln$后的多项式得足够优秀。恰好它的确足够优秀。 设$f(x)=\sum_{i=0}^\infty x^{vi}=\frac1{1-x^v}$，即是某个物品的生成函数。 $$\begin{aligned}\ln f(x)&=\int (\ln f(x))'\mathrm dx\\&=\int \frac{f'(x)}{f(x)}\mathrm dx\\&=\int (1-x^v)\sum_{i=1}^\infty vix^{vi-1}\mathrm dx\\&=\int \sum_{i=1}^\infty vix^{vi-1}-x^v\sum_{i=1}^\infty vix^{vi-1}\mathrm dx\\&=\int \sum_{i=1}^\infty vix^{vi-1}-x^v\sum_{i=1}^\infty v(i-1)x^{v(i-1)-1}\mathrm dx\\&=\int \sum_{i=0}^\infty vix^{vi-1}-\sum_{i=1}^\infty v(i-1)x^{vi-1}\mathrm dx\\&=\int \sum_{i=1}^\infty vx^{vi-1}\mathrm dx\\&=v\sum_{i=1}^\infty \frac{x^{vi}}i\end{aligned}$$ 然后求和，求和就枚举每个体积的物品个数，然后用调和级数的复杂度去给$v,2v,3v,\cdots$加系数$\frac{cnt_v}i$就可以了（因为$0$项在$\ln$前是$1\ln$后是$0$所以不用管了）。求和后$\rm exp$回去就做完了。