「题解」硬币购物

一道有意思的容斥题 + 对于背包求方案数的总结……

一 题目

原题链接

描述

硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西，去了tot次。每次带di枚ci硬币，买si的价值的东西。请问每次有多少种付款方法。

输入

第一行 c1,c2,c3,c4,tot 下面tot行 d1,d2,d3,d4,s。

输出

每次的方法数。

---

二 题解

直接拆分物品多重背包肯定是要T掉的。

先考虑没有硬币限制的情况，那么就是完全背包求方案数。这里有点东西可说。

完全背包求方案数
实际上就是一个完全背包的变形，不过有两种写法：不去重 和 去重，代码如下：

/* 不去重 */
for(int j=1;j<=m;j++)
    for(int i=1;i<=n;i++) 
        if(j - c[i] == 0) f[j] += 1;
        else if(j - c[i] > 0) f[j] += f[ j - c[i] ];
/* 去重 */
for(int i=1;i<=n;i++){
    f[ c[i] ] += 1;
    for(int j=c[i];j<=m;j++) f[j] += f[ j - c[i] ];
}

这两份代码的本质区别就是循环的顺序：先枚举物品 还是 先枚举空间。但是为什么对呢。

实际上，先枚举物品可以理解做人为地制定了一个取物品的“顺序”，一个物品在转移的时候，前面的物品就已经不可能再次被用来转移状态，因此不会出现重复；先枚举空间则反之。

然后是考虑容斥。

答案的容斥
首先，对于给定的 s ，在不考虑限制的情况下，答案一定为 f[s] 。

现在来考虑限制。
什么样的状态是不合法的？不妨我们先假定取了 (di+1) 枚硬币 i ，这肯定是不行的。考虑这部分硬币对答案的贡献：取过它们之后，还剩下 (s-ci(di+1)) 的面值没有被凑出，这一部分一共有 f[s-ci(di+1)] 种选取方案，那么一定包含 (di+1) 枚硬币 i 的方案的数量就是 1×f[s-ci(di+1)] = f[s-ci(di+1)] 。这部分是不合法的，因此减掉，答案变成 f[s] - f[s-ci(di+1)] 。

然后就是简单的容斥了：把减了两遍的部分加回来，再把加了两遍的部分减回去，再加，再减 …… 直到最后的区间两两无交（或只剩一个区间）。

然后就做完了，代码太丑就不放了，核心部分是这样的：

int k1 = (d[1]+1)*c[1],k2 = (d[2]+1)*c[2],k3 = (d[3]+1)*c[3],k4 = (d[4]+1)*c[4];
if(s-k1 >= 0) ans -= f[s-k1];
if(s-k2 >= 0) ans -= f[s-k2];
if(s-k3 >= 0) ans -= f[s-k3];
if(s-k4 >= 0) ans -= f[s-k4];
if(s-k1-k2 >= 0) ans += f[s-k1-k2];
if(s-k1-k3 >= 0) ans += f[s-k1-k3];
if(s-k1-k4 >= 0) ans += f[s-k1-k4];
if(s-k2-k3 >= 0) ans += f[s-k2-k3];
if(s-k2-k4 >= 0) ans += f[s-k2-k4];
if(s-k3-k4 >= 0) ans += f[s-k3-k4];
if(s-k1-k2-k3 >= 0) ans -= f[s-k1-k2-k3];
if(s-k1-k2-k4 >= 0) ans -= f[s-k1-k2-k4];
if(s-k1-k3-k4 >= 0) ans -= f[s-k1-k3-k4];
if(s-k2-k3-k4 >= 0) ans -= f[s-k2-k3-k4];
if(s-k1-k2-k3-k4 >= 0) ans += f[s-k1-k2-k3-k4];