Luogu P1450 [HAOI2008]硬币购物 解题报告

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;