P1450 [HAOI2008] 硬币购物

题目大意

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

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

• 对于 $100\%$ 的数据，保证 $1 \leq c_i, d_i, s \leq 10^5$，$1 \leq n \leq 1000$。

性质推测

时间复杂度：$O(n \times s \times \sum d_i)$，最坏情况下 $n=1000, s=10^5, \sum d_i \approx 4 \times 10^5$，显然会超时。

梯度上升

先分析每组数据的限制，有两种：硬币数和价值和。但价值和硬性要求，因此选择忽略硬币数：
转化为无限制的完全背包统计方案数（注意是组合数不是排列数）。

vec<int> dp(maxs,0);dp[0] = 1;
for(const auto x:c)for(int s=1;s<maxs;++s)if(s-x>=0)dp[s] += dp[s-x];//创建 预处理DP数组

容斥思想

但这显然与我们要求的不一致。既然“没有数量限制”版的问题已用完全背包预处理出 $dp[v]$（凑出 $v$ 元的无限制方案数），那“有数量限制”时，$dp[s]$ 里有哪些方案不该要？

显然，超出 $d_i$ 枚的都是非法方案。凡是付了 $\ge d_i+1$ 枚的方案都属于“硬币 $i$ 超量”。如果我们事先把这 $d_i+1$ 枚强制付掉，剩下的金额无论怎么付，最终都会导致硬币 $i$ 超量，这部分的方案数恰好就是 $dp[s - c_i(d_i+1)]$，这就是多出来的方案数。

考虑到要做到不重不漏，容斥定理可以很好的解决这一点。

因此我们需要枚举所有可能的情况，考虑使用一个四位掩码枚举当前有哪些种类的硬币超量。

算法流程

伪代码

预处理 dp[0..maxS] 初始化为 0
dp[0] = 1
for i from 1 to 4:
 for v from c[i] to maxS:
 dp[v] = dp[v] + dp[v - c[i]]

对于每个询问 (d[1..4], s):
 ans = 0
 for mask from 0 to 15: // 枚举四种硬币的超量状态
 sum = s
 cnt = 0 // 超量的硬币数(用于判断符号)
 for i from 0 to 3:
 if mask & (1 << i): // 第 i 个硬币强制超量
 sum = sum - (d[i] + 1) * c[i]
 cnt = cnt + 1
 if sum >= 0:
 if cnt % 2 == 0: // 偶数种超量，符号为正
 ans = ans + dp[sum]
 else: // 奇数种超量，符号为负
 ans = ans - dp[sum]
 输出 ans

Code