星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

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

posted on 2019-02-11 21:11:00 | under 未分类 |

由于 $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$ 回去就做完了。