定义

有$n$种物品，第$i$种质量为$m[i]$，价值为$v[i]$，数量有$1$个或无限个（前者称为$0-1$背包，后者称为无穷背包），背包容量为$T$，设最大质量为$s$。

特殊情况：

$v[i]=1$

恰好装满背包

只求是否存在一种方案恰好装满背包

求容量为$1\sim T$的所有答案

$T$远大于$s$

……

判断能否恰好装满背包

$n$个物品，第$i$种质量为$m[i]$，对于$t=1\sim T$询问是否存在方案使得质量和恰好为$t$。

$0-1$情况

无穷情况

多项式$\ln$，再$\exp$

具体：

设物品质量集合为$S$

对于$0-1$背包，$\prod\limits_{i\in S} (1+x^i)$

对于无穷背包，$\prod\limits_{i\in S} \frac{1}{1-x^i}$

但是对于这些式子并不能直接用FFT搞，因为这个多项式乘积的项数太多了，它并不是$O(1)$的多项式乘法。

那么就考虑$\ln$和$\exp$

设$0-1$背包的式子为$P(x)$，无穷背包为$Q(x)$。

然后就有$\ln \left(Q(x)\right)=\sum\limits_{i\in S} -\ln \left(1-x^i\right)$

考虑直接算它在$1$处的泰勒展开

$\ln(1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\ldots$

然后原式等于$\sum \limits_{i\in S} \sum\limits_{j\ge 1} \frac{x^{ij}}{j}$

然后这个东西直接暴力算就是$O(n\ln n)$的

因为$\sum [ij\le n]=\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+\ldots$

最后再$\exp$回去即可

复杂度$O(T\log T)$算出答案

概率算法，只能算方案数模大质数。

https://www.luogu.com.cn/problem/P4389 付公主的背包

$v[i]=1$ 硬币找零问题

$n$个物品，第$i$种质量为$m[i]$且有无穷多个，对于$t=1\sim T$询问最少选择几个物品使得质量和恰好为$t$。

只询问一个质量的最优复杂度？

二分最少需要几个+FFT优化判断

令$P(x)=1+\sum \limits_{i\in S} x^i$

选择$k$个硬币的生成函数就是$P^k(x)$，这可以$O(n\log n)$求出。然后二分也是一个$\log$，所以总复杂度$O(n\log^2 n)$

$O^{\sim}(T^{1.5})$（这个$\sim$指把$T$的$\log$因子给忽略掉，可以理解为$T^{1.5}\times \operatorname{polylog}$）？还能更优吗？

设一个阙值$B$，对于质量大于$B$的物品，最多只会使用$\frac{T}{B}$次。

用$O(\frac{T}{B})$次FFT在$O^{\sim}(\frac{T^{2}}{B})$的时间内计算使用$\frac{T}{B}$次物品的情况，再此基础上用质量小于$B$的物品每次$O(T)$更新$dp$数组，即$O(BT)$。

当$B=\sqrt{T}$时，可以达到理论复杂度最优$O^{\sim}(T^{1.5})$。

令$S$为大物品集合，然后还是刚刚那个东西为$P(x)$，已经通过FFT算出$P^{0},P^{1},\ldots ,P^{\frac{T}{B}}$

然后令$dp_S[i]$表示用$S$集合里面的硬币凑出面值为$i$最少要几个硬币。

然后用$P^0,\ldots ,P^{\frac{T}{B}}$就已经求出了$dp_S[i]$。

接下来令$S_0$表示那些小物品，假设$S_0={a_0,a_1,\ldots}$，用$dp_S[i]$更新到$dp_{S'}[i]$而$S'=S+{a_i}$，然后每次将$a_0,a_1,\ldots$分别更新上去。

考虑如何优化质量小物品的更新效率？

能否一次增加多个质量小的物品？

$0-1$情况下，如何在大$dp$数组上增加小物品？

（$1-\inf$数组和任意数组的$(+,\min)$卷积）

$(+,min)$卷积特殊情况优化

设$A$数组为任意数组，$B$数组要么为$1$要么为$\inf$，两个数组长度都为$L$。他们的$(+,\min)$卷积$C$数组为： $$ C[k]=\min_{i+j=k} A[i]+B[j] $$ 将$A$数组按照值从小到大排序，我们相当于询问能从$(i,j)$转移到$k$的最小的$A[i]$是什么

将$A$按照值域分成根号块，每块与$B$数组卷积。询问时由每块的卷积数组快速判断，可以将$A$的候选数限制在根号内，然后暴力枚举即可。总复杂度$O^{\sim}(L^{1.5})$

举个例子：

然后按照值域分块，比如$1,2$分一块，$3,4,5$分一块。

$1,2$分一块就相当于是$x+x^4$多项式与下面的$x+x^3+x^4$乘一下，然后$3,4,5$就相当于$x^2+x^3+x^5$，就是相当于把位置取出来做多项式然后乘一下看能转移到哪些位置。所以说可以将$A$的候选数限制在根号内。

考虑将质量在$[\frac{k}{2},k]$之间的物品的转移加到我们的$dp$数组上，我们依次对初始质量位于$[0,\frac{k}{2}),[\frac{k}{2},k),[k,\frac{3k}{2}),\ldots$进行$0-1$物品转移，使用上述优化可以做到$O^{\sim}(\frac{T}{K}\times K^{1.5})=O^{\sim}(T\times K^{0.5})$

为什么会有这个$[\frac{k}{2},k]$？因为如果物品太小且可以转移多次，而FFT并没有这种自己更新自己的操作。但是转移一定是这样转的：

就是说我们对于$\frac{k}{2}$这个区间的东西可以批量处理转移（就是用上面这个优化方法）。

最终算法

令$B=T^{\frac{2}{3}}$，处理质量大于$B$物品的情况。对于小于$B$的物品，分别取$k=B,\frac{B}{2},\frac{B}{4},\frac{B}{8},\ldots$

最终时间复杂度$O^{\sim}(T^{\frac{4}{3}})$。

Open problem：能否做到更优？