P4389 付公主的背包 做题记录

这个背包最多可以装 $10^5$ 大小的东西

付公主有 $n$ 种商品，她要准备出摊了

每种商品体积为 $v_i$，都有无限件

给定 $m$，对于 $s\in [1,m]$，请你回答用这些商品恰好装 $s$ 体积的方案数。

朴素的做法是 $n$ 个长度为 $m$ 的多项式相乘，时间复杂度为 $O(nm\log m)$，显然会 TLE

考虑一个物品的生成函数：

$f(x)=\sum\limits_{i=0}^{\inf}[i\equiv 0\pmod v]x^i$

$=\sum\limits_{i=0}^{\inf}x^{iv}$

显然这个式子当且仅当 $-1<x<1$ 时收敛，所以我们考虑令 $0<x<1$：

$\sum\limits_{i=0}^{\inf}x^{iv}=\lim\limits_{n\to\inf}\dfrac{x^{nv}-1}{x^v-1}$

由于当 $n$ 无限大时 $x^{nv}$ 无限趋近于 $0$，所以：

$\lim\limits_{n\to\inf}\dfrac{x^{nv}-1}{x^v-1}=\dfrac{-1}{x^v-1}=\dfrac{1}{1-x^v}$

也就是说 $f(x)=\dfrac{1}{1-x^v}$

我们要求很多个 $f$ 的乘积，那么考虑化乘为加，给 $f(x)$ 取个 $\ln$，求：

$\ln f(x)=\ln(\dfrac{1}{1-x^v})$

$=-\ln(1-x^v)$

这个东西不太好求，考虑求导：

$-\ln'(1-x^v)=-\dfrac{(1-x^v)'}{1-x^v}$

$=-\dfrac{1'-(x^v)'}{1-x^v}$

$=-\dfrac{-vx^{v-1}}{1-x^v}$

$=vx^{v-1}\dfrac{1}{1-x^v}$

注意到 $\dfrac{1}{1-x^v}=\sum\limits_{i=0}^{\inf}x^{iv}$，所以：

$=vx^{v-1}\sum\limits_{i=0}^{\inf}x^{iv}$

$=\sum\limits_{i=0}^{\inf}vx^{(i+1)v-1}$

$=\sum\limits_{i=1}^{\inf}vx^{iv-1}$

积分回来：

$\ln f(x)=\sum\limits_{i=1}^{\inf}\int vx^{iv-1}dx$

$=\sum\limits_{i=1}^{\inf}\int \dfrac{1}{i}ivx^{iv-1} dx$

$=\sum\limits_{i=1}^{\inf}\dfrac{1}{i}x^{iv}$

好了，我们终于求得了 $f(x)=\sum\limits_{i=1}^{\inf}\dfrac{1}{i}x^{iv}$。

接下来把它们相加，求 $\exp$ 即可。

具体的做法是，开一个桶 $t_i$ 存 $v=i$ 的多项式有多少个，然后调和级数搞即可。