背包计数问题的多项式优化

此优化针对以下计数问题：

n 件物品，背包容量为 m，第 i 件物品体积为 \(a_i\)，求装满的方案数。（01背包）

n 种物品，背包容量为 m，第 i 件物品体积为 \(a_i\)，数量无限，求装满的方案数。（完全背包）

n 种物品，背包容量为 m，第 i 件物品体积为 \(a_i\)，数量为 \(b_i\)，求装满的方案数。（多重背包）

\((1\le n\le1e5, 1\le m\le1e5, 1\le a_i,b_i \le 1e5)\)

不止求装满的方案数，用多项式优化后求装任意体积都是 \(O(mlogm)\)。

01背包计数

首先来看计数01背包的生成函数：

第 i 个物品：\(G_i(x) = 1+x^{a_i}\)

\(x^0\) 项表示不选，\(x^{a_i}\) 表示选，占体积为 \(a_i\)。

那么刚好装满容量为 k 的背包的方案数为：\(G(x)[x^k]=\prod\limits_{i=1}^nG_i(x)[x^k]=(1+x^{a_1})(1+x^{a_2})...(1+x^{a_n})[x^k]\)

这个式子看起来很好求，和我们之前遇到的另一个式子很像：\((x+a_1)(x+a_2)...(x+{a_n})\)，这个式子就可以用分治NTT来求。

但是上面的式子次数太高了，如果用分治NTT来做，分治的最底层就已经爆炸了。

我们用一个小技巧，这种连乘的算式先取个对数 \(ln\)，就可以变成相加的形式，求和之后再 \(exp\) 回去就是原式：

\(G(x)=exp(ln(1+x^{a_1})+ln(1+x^{a_2})+...+ln(1+x^{a_n}))\)

每个物品的式子都求一遍 \(ln\) 再挨个相加，这个复杂度仍然是平方的。

但是我们发现 \(G(x)\) 的每一个因式都只有两项，这个式子可以直接套用麦克劳林公式手算：\(ln(1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+...+(-1)^n\frac{x^{n+1}}{n+1}\)

把 \(x\) 换成 \(x^a\) ：\(ln(1+x^a)=x^a-\frac{x^{2a}}{2}+\frac{x^{3a}}{3}-\frac{x^{4a}}{4}+...+(-1)^n\frac{x^{(n+1)a}}{n+1}\)

我们发现在总容量为 m 的限制下，一个体积为 a 的物品式子中有用的项只有 \(\frac ma\) 个，其余项为0。

我们记录每种体积的物品有几个，那么每一个不同的 a 只会算一次，\(\sum\frac m a\) 的复杂度是调和级数的 \(mlogm\)。于是我们就解决了这个问题。

完全背包计数

洛谷有个板子题：P4389 付公主的背包，想要代码的可以看这题的题解。

和01背包原理一样，将生成函数先取对数，相加后再 \(exp\) 回去。

只是现在每种物品有无限个，因此生成函数式子稍有不同：

\(G_i(x)=1+x^{a_i}+x^{2a_i}+...+x^{na_i}+...\)

\(G_i(x)=\sum\limits_{j=0}^{\infty}x^{j·a_i}\)

\(G_i(x)=\frac{1}{1-x^{a_i}}\)

至于这个式子怎么转化的，那就是生成函数的基础了。

我们将这些式子取对数再相加：

\(ln(G_i(x))=ln(\frac{1}{1-x^{a_i}})=-ln(1-x^{a_i})=x^{a_i}+\frac{x^{2{a_i}}}{2}+\frac{x^{3{a_i}}}{3}+\frac{x^{4{a_i}}}{4}+...+\frac{x^{(n+1)a}}{n+1}\)

所以几乎和01背包的式子一样。

多重背包计数

和前者一样，也是只有生成函数式子有不同。

第 i 种物品有 \(b_i\) 个，因此生成函数有 \(b_i+1\) 项：

\(G_i(x)=1+x^{a_i}+x^{2a_i}+...+x^{b_ia_i}\)

\(G_i(x)=\frac{1-x^{b_ia_i}}{1-x^{a_i}}\)

取对数后分母取负，就和完全背包的式子形式一样了，注意分子在调和级数去重时要按照 a*b 的值。