P1450 [HAOI2008]硬币购物

共有 4 种硬币。面值分别为 c_1,c_2,c_3,c_4。

某人去商店买东西，去了 n 次，对于每次购买，他带了 d_i 枚 i 种硬币，想购买 s 的价值的东西。请问每次有多少种付款方法。

解题思路：

容斥 + DP

挺牛逼的一道题，做了一天学到很多。

首先看到这个问题，根据经验发现可以通过多重背包解决，但是时间复杂度为 O(ns^2)，非常离谱。

我们先把问题分割成小问题

共有 1 种硬币。面值为c ，不限制使用次数。

那么这就是裸的无限背包，O(n) 即可解决。

加上限制怎么做？直接背包肯定是不行的，我们考虑用总数减去反面。

即 满足条件的方案总数 = 方案总数 - 不满足条件的方案总数

那么问题就转化为了如何求不满足条件的方案总数。我们观察题目性质可以发现，如果我们取了 d_i + 1 个硬币，那么接下来不论怎么取硬币都是非法方案。

所以我们可以想到，强制令体积为 s - c_i * (d_i + 1) 那么所有方案都是非法的，转化为方程也就是

ans = f_s - f{ s - c_i * (d_i + 1) }

试图扩大下这个问题，发现如果我们直接去掉 c_i * (d_i + 1) 还会把其他部分的合法方案给去掉。这里设第 i 种硬币的不合法方案集合为 A_i，那么我们就是要求

|A_1 \cup A_2 \cup A_3 \cup A_4|

这就是一个很明显的容斥问题了。

根据容斥原理，我们可以得出

\begin{aligned} &|A_1 \cup A_2 \cup A_3 \cup A_4| \\ &= (|A_1| + |A_2| + |A_3| + |A_4|) \\ &- (|A_1 \cap A_2| + |A_1 \cap A_3| +|A_1 \cap A_4| + |A_2 \cap A_3|+ |A_2 \cap A_4|+ |A_3 \cap A_4|)\\ &+ (|A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + |A_2 \cap A_3 \cap A_4|)\\ &- |A_1 \cap A_2 \cap A_3 \cap A_4| \end{aligned}

现在还有一个问题，如何求 |A_1 \cap A_2| ?

还是类似刚才的做法，如果要让这种方案成立，我们就强制把两个硬币全部扣去，即 s - (c_i \times (d_i + 1)) - (c_j \times (d_j + 1)))

同样可以拓展到 n 个的情况。

对于这个问题，我们在问题最开始时先预处理一遍没有限制的选择方案 f，然后每次求并集直接算 f_{s - (c_i \times (d_i + 1)) - (c_j \times (d_j + 1))}

所以这里我们可以通过枚举子集来快速求解，比如说 5 对应的 4 位二进制表示为 0110 ，我们就认为这里是要求 |A_2 \cap A_3|

代码实现

for (int i = 0;i < 16;++i) {
    ll siz = 0,k = 0,tmp = 0,tot = 1;
    ll p = i;
    while (p) {
        if (p & 1) {
            tmp += c[tot] * (d[tot] + 1);
            //计算c_i * (d_i + 1)
            ++siz;
            //统计当前有多少个
        }
        ++tot,p >>= 1;
    }
    if (siz % 2) k = -1;
    else k = 1;
    //奇加偶减
    if (s - tmp < 0) continue;
    //排除非法方案
    ans += k * f[s-tmp];
}

于是这题就做完了。

总结：

  1. 如果正面思考不通，尝试用整体去掉反面来计算答案
  2. 统计方案时出现重复部分，用容斥原理来处理
  3. 所谓“奇加偶减”，其实是第 i 项的运算和第 i-1 项运算符相反，主要确定第 1 项是啥
  4. 进行第 1 步时，如果发现哪里 RE 了，考虑排查边界问题。

代码：

    read(c[1],c[2],c[3],c[4],n);
    f[0] = 1;
    for (int i = 1;i <= 4;++i) {
        for (int j = c[i];j <= N;++j) {
            f[j] += f[j - c[i]];
        }
    }
    while (n--) {
        ll ans = 0;
        read(d[1],d[2],d[3],d[4],s);
        for (int i = 0;i < 16;++i) {
            ll siz = 0,k = 0,tmp = 0,tot = 1;
            ll p = i;
            while (p) {
                if (p & 1) tmp += c[tot] * (d[tot] + 1),++siz;
                ++tot,p >>= 1;
            }
            if (siz % 2) k = -1;
            else k = 1;
            //printf("%lld\n",tmp);
            if (s - tmp < 0) continue;
            ans += k * f[s-tmp];
        }
        printf("%lld\n",ans);
    }
    return 0;