组合数学与 DP 优化：硬币购物 (容斥原理经典模型)
题目简述：共有 4 种硬币，面值分别为 c_1, c_2, c_3, c_4。进行 T 次询问，每次询问给出这 4 种硬币的数量限制 d_1, d_2, d_3, d_4，问凑出总价值 s 的方案数有多少种？
数据范围：T \leq 1000，s \leq 10^5。
一、陷阱：为什么不能直接跑多重背包？
面对硬币和数量限制，第一直觉是多重背包问题。对于单次询问，如果用多重背包（甚至加上二进制优化），复杂度大约是 O(s \cdot \sum \log d_i)。但注意，本题有 T 次询问！如果每次都跑一遍背包，总复杂度高达 O(T \cdot s \cdot \sum \log d_i)。在 1 秒的时限内，这个数量级极易 TLE（超时）。
破局关键：提取不变量。 我们发现，4 种硬币的面值是永远不变的，改变的仅仅是每次的限制数量 d_i 和目标值 s。能否把面值带来的组合数先预处理出来？
二、降维打击：完全背包 + 容斥原理
1. 预处理：无拘无束的完全背包
既然每次数量限制不同，我们干脆先彻底不管数量限制，假设每种硬币都有无限个。设 f[x] 表示用无限个这 4 种硬币，凑出价值 x 的方案数。这只需在程序开头跑一次极其简单的 O(4s) 的完全背包即可。预处理耗时微乎其微。
2. 状态转化：什么是“不合法”方案？
对于某次询问（目标是 s，第 i 种硬币最多用 d_i 个）。从所有方案 f[s] 中，我们需要剔除掉那些“不合法”的方案。
什么叫“第 i 种硬币超发（不合法）”？ 意味着在这个方案中，我们使用了至少 d_i + 1 个 第 i 种硬币。那么，满足“第 i 种硬币超发”的方案总数到底是多少呢？
神来之笔：强行塞入法
我们先强行拿走 d_i + 1 个第 i 种硬币，这必然会占据 (d_i + 1) \cdot c_i 的价值。剩下的价值是：s - (d_i + 1) \cdot c_i。用剩下的价值，在无限硬币的条件下随便怎么凑，得到的任何一种方案，再加上我们刚才强行塞入的那 d_i + 1 个硬币，必定是一种第 i 种硬币超发的非法方案！ 因此，仅仅违背第 i 个限制的不合法方案数为：
（若括号内为负数，则视为 0）
3. 终极组装：容斥原理
我们有 4 个限制。按照上面的思路，我们减去违背限制 1、2、3、4 的方案。但是，如果有某种方案同时超发了硬币 1 和硬币 2，它就在减去限制 1 时被减了一次，减去限制 2 时又被减了一次，多减了！需要加回来。
这正是标准的容斥原理 (Inclusion-Exclusion Principle)：
真实合法方案数 = 总方案数
- \sum f(s - (d_i+1)c_i)
+ \sum f(s - (d_i+1)c_i - (d_j+1)c_j)
- \sum f(s - (d_i+1)c_i - (d_j+1)c_j - (d_k+1)c_k)
+ f(s - \sum_{i=1}^4 (d_i+1)c_i)
由于只有 4 种硬币，违背限制的组合只有 2^4 = 16 种情况。我们可以用一个 0 到 15 的二进制数完美枚举！
三、C++ 极简最优代码实现
相比于书上的晦涩宏定义，这份代码利用位运算将容斥原理写得如诗一般清晰。
#include <iostream>
#include <vector>
using namespace std;
const int MAXS = 100005;
long long f[MAXS]; // f[i] 表示无限制时凑出价值 i 的方案数
long long c[4]; // 4种硬币的面值
int main() {
// 优化输入输出
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// 读入 4 种硬币的面值
for (int i = 0; i < 4; ++i) {
cin >> c[i];
}
// --- 预处理：完全背包 ---
f[0] = 1; // 凑出价值为 0 的方案数为 1 (什么都不拿)
for (int i = 0; i < 4; ++i) {
for (int j = c[i]; j < MAXS; ++j) {
f[j] += f[j - c[i]];
}
}
int n;
if (!(cin >> n)) return 0;
// --- 处理每次询问：容斥原理 ---
while (n--) {
long long d[4];
long long s;
for (int i = 0; i < 4; ++i) cin >> d[i];
cin >> s;
long long ans = 0;
// 枚举 16 种超发状态 (0 ~ 15)
// 二进制位为 1 表示假设对应硬币超发（使用了至少 d[i] + 1 个）
for (int state = 0; state < 16; ++state) {
long long current_s = s; // 当前状态下，强行拿走超发硬币后剩余的目标价值
int bits = 0; // 记录当前状态违背了几个限制 (即 1 的个数)
for (int i = 0; i < 4; ++i) {
if ((state >> i) & 1) { // 如果第 i 位为 1，说明强行让第 i 种硬币超发
// 扣除被迫拿走的 d[i] + 1 个硬币的总面值
current_s -= c[i] * (d[i] + 1);
bits++;
}
}
// 如果剩余的价值不足 0，说明这种超发情况在当前总价值 s 下不可能发生，直接忽略
if (current_s >= 0) {
// 根据容斥原理：
// 违背了奇数个限制，符号为负 (-)
// 违背了偶数个限制 (包括 0 个，即无超发)，符号为正 (+)
if (bits % 2 == 1) {
ans -= f[current_s];
} else {
ans += f[current_s];
}
}
}
cout << ans << "\n";
}
return 0;
}