Journey with Knapsack
题意
有一个容量为2n的背包，n种食物，每种食物的体积为i，最多有$a_i$个，除了食物，还有m件装备，每件装备的体积是$b_i$，必须带一件装备，问2n的背包能够装下的所有情况种数？
1<=n<=5e4 , 0<=ai<=2n , 1<=m<=2n，0<=bi<=2n。
思路
背包全部装食物的方案数：
$$
\prod_{i=1}^n(1+x^i+x^{2i}+…+x^{a_ii})=\prod_{i=1}^n\frac{1-x^{i(a_i+1)}}{1-x^i}
$$
$$
=\prod_{i=1}^n(1-x^{i(a_i+1)}) \prod_{i=1}^n(\frac{1}{1-x^i})
$$
对于左边的累乘进行分析：
- 假设右边部分已经求得，是一个2n项（后面会求到）多项式：$\sum_{i=1}^{2n}dp[i]*x^i$(dp[i]的i指的是体积，dp的值是种数)
- 那么原式子就变成，左边的n个两项式与右边的的2n项式相乘，有：
$$
(1-x^{i(a_i+1)})(\sum_{j=1}^{2n}dp[j]x^j)
$$
$$
=\sum_{j=1}^{2n}dp[j]x^j-\sum_{j=1}^{2n}dp[j]x^{i(a_i+1)+j}
$$
我们将j向右移$i*(a_i+1)$位，则：
$$
=\sum_{j=1}^{2n}dp[j]x^j-\sum_{j=i(a_i+1)}^{2n+i(a_i+1)}dp[j-i(a_i+1)]x^j
$$
$$
=\sum_{j=1}^{i(a_i+1)}dp[j]x^j+\sum_{j=i(a_i+1)}^{2n}(dp[j]-dp[j-i(a_i+1)])x^j
$$
（由于2n以后的项都没有意义，所以可以减少到2n）- 由于前面的假设1，dp[j]已经求得，因此我们只要再求得对所有$i*(a_i+1)\le{j}\le2n$，再求：
$$
dp[j]=dp[j]-dp[j-i*(a_i+1)]
$$
对于右边的累乘：
$$
\prod_{i=1}^n(\frac{1}{1-x^i}) = \prod_{i=1}^{2n}(\frac{1}{1-x^i}) \prod_{i=n+1}^{2n}({1-x^i})（不满2n所以补上）
$$
- 对于左边的式子，根据五边形定理：
$$
Q(x)=\sum_{i\ge1}(1-x^i)=\sum_{i\ge1}(-1)^i(x^{\frac{3i^2-i}{2}}+x^{\frac{3i^2+i}{2}})=(1-x)(1-x^2)…=1-x-x^2+x^5+x^7+……
$$
整数拆分的式子是这样的：
$$
P(x)=(1+x+x^2+…)（1+x^2+x^4+…）(1+x^3+x^6+…)
$$
$$
=\prod_{i\ge1}(1+x^i+x^{2i}+…)=\prod_{i\ge1}\frac{1}{1-x^i} （x<1无穷等比数列求级数）
$$
因此我们可以看到：Q(x)P(x)=1，也就是说：
$$
(1-x-x^2+x^5+x^7+……)(1+p(1)x+p(2)x^2+p(3)x^3+…)=1
$$
因此我们考虑，对于每项x^n前面的系数，必定有：
$$
p(n)-p(n-1)-p(n-1)+p(n-5)+p(n-7)……=0
$$
因此得递推式：
$$
p(n)=p(n-1)+p(n-1)-p(n-5)-p(n-7)……
$$
可以求出dp[i]=p[i]。（i<=2n）
对于右边的式子$\prod_{i=n+1}^{2n}({1-x^i})$，由于累乘$x^a*x^b=x^{(a+b)}$，故对于a+b>2n的都可以舍去。
就化为了：
$$
1-\sum_{i=n+1}^{2n}x^i
$$
- 整个式子就变成：
$$
P(x)(1-\sum_{i=n+1}^{2n}x^i),P(x)=\sum_{i=1}^{2n}dp[i]x^i
$$
$$
=\sum_{i=1}^{2n}dp[i]x^i -\sum_{i=n+1}^{2n}dp[i-n-1]x^i-\sum_{i=n+2}^{2n}dp[i-n-2]x^i-……
$$
$$
=\sum_{i=1}^{n}dp[i]x^i+x^{n+1}(dp[n+1]-dp[0])+x^{n+2}(dp[n+2]-dp[1]-dp[0])+……
$$
$$
+x^{2n}(dp[2n]-dp[n-1]-dp[n-2]-…-dp[0])
$$
也就是说对于所有dp[i]，i>=n+1,<=2n的，都进行减去sum[i-n-1] (前缀和)的操作。即：
$$
dp[i]=dp[i]-\sum_{j=1}^{i-n-1}dp[j]
$$
那么所有的部分就都算完啦！！！！！！
啊啊啊啊啊啊啊啊啊啊啊啊啊
看！代码
1 |
|