背包 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
1#include <bits/stdc++.h>
2
3using namespace std;
4const int S = 1e5 + 5;
5int c[5], d[5], n, s;
6long long f[S];
7
8int main() {
9
10 cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
11 f[0] = 1;
12 for (int j = 1; j <= 4; j++)
13 for (int i = 1; i < S; i++)
14 if (i >= c[j]) f[i] += f[i - c[j]];
15 for (int i = 1; i <= n; i++) {
16 cin >> d[1] >> d[2] >> d[3] >> d[4] >> s;
17 long long ans = 0;
18 for (int j = 1; j < 16; j++) {
19 int m = s, bit = 0;
20 for (int k = 1; k <= 4; k++)
21 if ((j >> (k - 1)) & 1) m -= (d[k] + 1) * c[k], bit++;
22 if (m >= 0) ans += (bit % 2 * 2 - 1) * f[m];
23 }
24 cout << f[s] - ans << endl;
25 }
26 return 0;
27}
Code 2
1#include <bits/stdc++.h>
2
3using namespace std;
4const int MAXM = 1e5;
5
6int main() {
7 int c[5], n;
8// ofstream cout; cout.open("out");
9 cin >> c[1] >> c[2] >> c[3] >> c[4] >> n;
10 static long long f[5][MAXM + 1];
11 f[0][0] = 1;
12 for (int i = 1; i <= 4; ++i) { // Total number of programs
13 for (int j = 0; j <= MAXM; ++j) {
14 if (j < c[i]) f[i][j] = f[i - 1][j];
15 else f[i][j] = f[i - 1][j] + f[i][j - c[i]];
16 }
17 }
18 /*
19 cout << "COIN #" << setw(2) << c[0] << " ";
20 for(int j = 0; j <= 50; ++j) cout << setw(5) << left << j; cout << endl;
21 for(int i = 0; i <= 4; ++i){
22 cout << "COIN #" << setw(2) << c[i] << " ";
23 for(int j = 0; j <= 50; ++j){
24 cout << setw(5) << left << f[i][j];
25 }cout << endl;
26 }
27 */
28
29 while (n--) {
30 int d[5], m;
31 cin >> d[1] >> d[2] >> d[3] >> d[4] >> m;
32
33 long long ans = f[4][m]; // Total number of programs in m
34
35 // 每一枚硬币超过限制 -A-B-C-D
36 for (int i = 1; i <= 4; ++i) {
37 if (m - (d[i] + 1) * c[i] >= 0) ans -= f[4][m - (d[i] + 1) * c[i]];
38 }
39
40 // 每二枚硬币超过限制 +AB+AC+AD+BC+BD+CD
41 for (int i = 1; i <= 4; ++i) {
42 for (int j = i + 1; j <= 4; ++j) {
43 if (m - (d[i] + 1) * c[i] - (d[j] + 1) * c[j] >= 0)
44 ans += f[4][m - (d[i] + 1) * c[i] - (d[j] + 1) * c[j]];
45 }
46 }
47
48 // 每三枚硬币全部超过限制 -ABC-ABD-ACD-BCD
49 for (int i = 1; i <= 4; ++i) {
50 for (int j = i + 1; j <= 4; ++j) {
51 for (int k = j + 1; k <= 4; ++k) {
52 if (m - (d[i] + 1) * c[i] - (d[j] + 1) * c[j] - (d[k] + 1) * c[k] >= 0)
53 ans -= f[4][m - (d[i] + 1) * c[i] - (d[j] + 1) * c[j] - (d[k] + 1) * c[k]];
54 }
55 }
56 }
57
58 // 每四枚硬币全部超过限制 +ABCD
59 if (m - ((d[1] + 1) * c[1]) - ((d[2] + 1) * c[2]) - ((d[3] + 1) * c[3]) - ((d[4] + 1) * c[4]) >= 0)
60 ans += f[4][m - (d[1] + 1) * c[1] - (d[2] + 1) * c[2] - (d[3] + 1) * c[3] - (d[4] + 1) * c[4]];
61
62 cout << ans << endl;
63 }
64}
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。