可撤销背包

考虑一般的\(01\)背包。就是体积\(w_i\)，\(f_{j}\)表示体积为\(j\)的方案数。不撤销就是\(f_{j}+=f_{j-w_i}\)了，当然倒序。接下来考虑撤销，\(g_{j}\)表示去掉\(i\)后体积和为\(j\)的方案数。那我们使用\(w_i\)时，其他的体积和一定为\(j-w_i\)，所以使用\(w_i\)的方案数就是\(g_{j-w_i}\)，所以\(f_j-g_{j-w_i}\)就是\(g_j\)了。我们考虑从多项式的角度来思考，每个物品有选和不选状态，对应一个多项式\((1+x^{w_i})\),\(x\)表示一个占位符，说是叫形式幂级数，我不会，但是对理解这个没影响。那对于所有的\(i\)，\(\prod (1+x^{w_i})\)，然后\(x_j\)前面的系数就是\(f_j\)。撤销\(i\)就是除以\((1+x^{w_i})\)。但是考虑\(g_j=f_j-g_{j-w_i}\)这个操作对应多项式的什么操作。由上面的推导可知，这个操作其实是在把选择\(w_i\)的贡献删掉了，也就是把选择\(w_i\)这个选项给删掉了，也就是把\((1+x_{w_i})\to (1)\)这样了。但是我们期望把\((1+x_{w_i})\)都删掉而不是剩下\(1\)，只不过是剩下\(1\)，这样的值刚好不变就是了。那么理解了这个是什么以后，我们思考一下其他问题，例如，\(i\)不是选或不选，而是有几个选项，选择体积为\(w_1,w_2,w_3,\dots,w_k\)这样的选项，也就是变成了\(\prod (x_{w_1}+x_{w_2}+,\dots,+x_{w_k})\)，此时我们考虑是否能够令\(g_j=f_j-\sum_{j-w_{i,k}}\)。这样最后就变成了\(()\to (0)\)了所以\(g_j\)就是\(0\)了，问题就是出现在没有\(x_{0}=1\)兜底了，所以此时我们选择选择一个\(w_{i}\)，把其他的都减去，最后剩下\((x_{w_i})\)，那么我们给这个多项式除以\(x_{w_i}\)就行了，那么我们已经知道了\(g_{i,j}\)就是\(x_{j}\)的系数了，那除以\(x_{w_i}\)其实就是给多项式左移\(w_i\)了。例题：P15649