[HAOI2008] 硬币购物

题意

有 4 种硬币，面值分别是 c1..c4。

一共有 n 次询问。
每次询问给出：

4 种硬币各自最多能用多少枚 d1..d4
目标金额 s

要求统计有多少种付款方法，正好凑出 s。

思路

先看一个直接按定义枚举的小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int coin[5];
int query_count;
int limit_cnt[5];
int target_sum;
i64 ans;

void dfs(int idx, int sum_now) {
    if (idx == 5) {
        if (sum_now == target_sum) {
            ans++;
        }
        return;
    }

    for (int take = 0; take <= limit_cnt[idx]; take++) {
        int ns = sum_now + take * coin[idx];
        if (ns > target_sum) {
            break;
        }
        dfs(idx + 1, ns);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> coin[1] >> coin[2] >> coin[3] >> coin[4] >> query_count;

    while (query_count--) {
        cin >> limit_cnt[1] >> limit_cnt[2] >> limit_cnt[3] >> limit_cnt[4] >> target_sum;
        ans = 0;
        dfs(1, 0);
        cout << ans << '\n';
    }

    return 0;
}

暴力版就是直接枚举四种硬币各取几枚，再检查总和是不是 s。

第一步：先忘掉上界

如果暂时不考虑 d1..d4 这些上界，只问：

4 种硬币都可以无限用
凑出金额 x
有多少种方案

这就是一个非常标准的完全背包方案数。

设：

dp[x] 表示无限硬币时，凑出 x 的方案数

因为只有 4 种硬币，而且所有询问公用同一组面值，所以这张 dp 表可以只预处理一次。

第二步：把“超上界”的方案扣掉

对某次询问，设第 i 种硬币最多只能用 d_i 枚。

如果某个方案不合法，那么一定至少有一种硬币用多了。
这正是容斥原理的经典信号。

假设第 i 种硬币超限，也就是它至少用了：

d_i + 1

枚。
那我们先强制拿出这 d_i + 1 枚，剩下还要凑的金额就变成：

s - (d_i + 1) * c_i

而剩下部分又回到了“无限硬币方案数”的模型。

所以对每个硬币超限集合 mask，都能算出一个被多算的方案数，然后按容斥加减即可。

因为只有 4 种硬币，所以一共只需要枚举：

2^4 = 16

个子集，常数非常小。

最终做法

先用完全背包预处理无限硬币方案数 dp
每个询问枚举 16 个子集
对应地减去或加回“这些硬币都超限”的方案数

这样每个询问只要常数时间就能完成。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int coin[5];
int query_count;
vector<i64> dp;

i64 ways_with_unlimited(int s) {
    if (s < 0) {
        return 0;
    }
    return dp[s];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> coin[1] >> coin[2] >> coin[3] >> coin[4] >> query_count;

    vector<array<int, 5>> limits(query_count + 1);
    vector<int> target(query_count + 1);
    int max_s = 0;

    for (int i = 1; i <= query_count; i++) {
        cin >> limits[i][1] >> limits[i][2] >> limits[i][3] >> limits[i][4] >> target[i];
        max_s = max(max_s, target[i]);
    }

    // 先预处理“每种硬币都无限使用”时，凑出每个金额的方案数。
    dp.assign(max_s + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= 4; i++) {
        for (int s = coin[i]; s <= max_s; s++) {
            dp[s] += dp[s - coin[i]];
        }
    }

    for (int i = 1; i <= query_count; i++) {
        i64 ans = 0;

        // 容斥：mask 表示哪些硬币“超过了上界”。
        for (int mask = 0; mask < (1 << 4); mask++) {
            int need = target[i];
            int bits = 0;

            for (int j = 0; j < 4; j++) {
                if ((mask >> j) & 1) {
                    bits++;
                    need -= (limits[i][j + 1] + 1) * coin[j + 1];
                }
            }

            i64 add = ways_with_unlimited(need);
            if (bits & 1) {
                ans -= add;
            }
            else {
                ans += add;
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

复杂度

设所有询问里的最大目标金额为 S。

预处理完全背包： $O(4S)$
每个询问做 16 次容斥： $O(16)$

总时间复杂度：

$O(S + 16n)$

空间复杂度：

$O(S)$

总结

这题最关键的拆分是：

先把“上界限制”拿掉，得到一个通用的完全背包方案数表
再用容斥把“不合法的超限方案”扣掉

因为硬币种类只有 4，容斥的常数非常小，所以这种做法又稳又快。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。