背包 DP + 容斥原理
如果用背包做的话复杂度是 $math_inline$O(4nS)$math_inline$ ，无法承受。这道题最明显的特点就是硬币一共只有四种。抽象模型，其实就是让我们求方程 $math_inline$\sum_{i=1}^4C_ix_i=S,x_i\leq D_i$math_inline$ 的非负整数解的个数。
采用同样的容斥方式， $math_inline$x_i$math_inline$ 的属性为 $math_inline$x_i\leq D_i$math_inline$ . 套用容斥原理的公式，最后我们要求解
$math_inline$ \sum_{i=1}^4C_ix_i=S-\sum_{i=1}^kC_{a_i}(D_{a_i}+1) $math_inline$也就是无限背包问题。这个问题可以预处理，算上询问，总复杂度 $math_inline$O(4S+2^4n)$math_inline$ .
首先，求出不限制使用次数，购买价值为 $math_inline$c$math_inline$ 时的方案数，设它为 $math_inline$f(c)$math_inline$ 。
对于每次询问，我们可以不限制使用次数，购买价值 $math_inline$s_i$math_inline$ 的方案数，减去任意一种硬币超过限制的方案数。
任意一种硬币超过限制的方案数可以用容斥原理求出，即：每一种硬币超过限制的方案数之和-每两种硬币超过限制的方案数之和+每三种硬币超过限制的方案数之和-四种硬币全部超过限制的方案数。
考虑如何求出第 $math_inline$i$math_inline$ 种硬币超过限制的方案数：我们至少要使用 $math_inline$d_i+1$math_inline$ 个第 $math_inline$i$math_inline$ 种硬币，剩余的 $math_inline$s-(d_i+1)\times c_i$math_inline$ 元可以任意选择，即 $math_inline$f(s-(d_i+1)\times c_i)$math_inline$
Code 1
#include <bits/stdc++.h>
using namespace std;
const int S = 1e5 + 5;
int c[5], d[5], n, s;
long long f[S];
int main() {
cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
f[0] = 1;
for (int j = 1; j <= 4; j++)
for (int i = 1; i < S; i++)
if (i >= c[j]) f[i] += f[i - c[j]];
for (int i = 1; i <= n; i++) {
cin >> d[1] >> d[2] >> d[3] >> d[4] >> s;
long long ans = 0;
for (int j = 1; j < 16; j++) {
int m = s, bit = 0;
for (int k = 1; k <= 4; k++)
if ((j >> (k - 1)) & 1) m -= (d[k] + 1) * c[k], bit++;
if (m >= 0) ans += (bit % 2 * 2 - 1) * f[m];
}
cout << f[s] - ans << endl;
}
return 0;
}
Code 2
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 1e5;
int main() {
int c[5], n;
// ofstream cout; cout.open("out");
cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
static long long f[5][MAXM + 1];
f[0][0] = 1;
for (int i = 1; i <= 4; ++i) { // Total number of programs
for (int j = 0; j <= MAXM; ++j) {
if (j < c[i]) f[i][j] = f[i - 1][j];
else f[i][j] = f[i - 1][j] + f[i][j - c[i]];
}
}
/*
cout << "COIN #" << setw(2) << c[0] << " ";
for(int j = 0; j <= 50; ++j) cout << setw(5) << left << j; cout << endl;
for(int i = 0; i <= 4; ++i){
cout << "COIN #" << setw(2) << c[i] << " ";
for(int j = 0; j <= 50; ++j){
cout << setw(5) << left << f[i][j];
}cout << endl;
}
*/
while (n--) {
int d[5], m;
cin >> d[1] >> d[2] >> d[3] >> d[4] >> m;
long long ans = f[4][m]; // Total number of programs in m
// 每一枚硬币超过限制 -A-B-C-D
for (int i = 1; i <= 4; ++i) {
if (m - (d[i] + 1) * c[i] >= 0) ans -= f[4][m - (d[i] + 1) * c[i]];
}
// 每二枚硬币超过限制 +AB+AC+AD+BC+BD+CD
for (int i = 1; i <= 4; ++i) {
for (int j = i + 1; j <= 4; ++j) {
if (m - (d[i] + 1) * c[i] - (d[j] + 1) * c[j] >= 0)
ans += f[4][m - (d[i] + 1) * c[i] - (d[j] + 1) * c[j]];
}
}
// 每三枚硬币全部超过限制 -ABC-ABD-ACD-BCD
for (int i = 1; i <= 4; ++i) {
for (int j = i + 1; j <= 4; ++j) {
for (int k = j + 1; k <= 4; ++k) {
if (m - (d[i] + 1) * c[i] - (d[j] + 1) * c[j] - (d[k] + 1) * c[k] >= 0)
ans -= f[4][m - (d[i] + 1) * c[i] - (d[j] + 1) * c[j] - (d[k] + 1) * c[k]];
}
}
}
// 每四枚硬币全部超过限制 +ABCD
if (m - ((d[1] + 1) * c[1]) - ((d[2] + 1) * c[2]) - ((d[3] + 1) * c[3]) - ((d[4] + 1) * c[4]) >= 0)
ans += f[4][m - (d[1] + 1) * c[1] - (d[2] + 1) * c[2] - (d[3] + 1) * c[3] - (d[4] + 1) * c[4]];
cout << ans << endl;
}
}