形式化题目

有 $N$ 种硬币，第 $i$ 种面值 $A_i$、数量 $C_i$。从所有硬币中任取若干枚（第 $i$ 种至多取 $C_i$ 枚），把取出的硬币面值相加得到 $S$，称 $S$ 能被拼成。记

求 $|R \cap [1,M]|$，即 $1 \sim M$ 中能被拼成的面值个数。$0 \in R$ 对应一枚都不取的空方案，不计入答案。

暴力解法

思路

最直白的做法是按「物品」而不是按「种类」思考：第 $i$ 种硬币有 $C_i$ 枚，就把它摊成 $C_i$ 件互不相同的单枚硬币，于是问题变成 $K=\sum_i C_i$ 件物品的 0/1 背包。设 $f[s]$ 表示面值 $s$ 能否拼成，初始 $f[0]=\text{true}$，其余为假：

1
2
3
4
5f[0] = true
for 每枚硬币（面值 a）:
    for s = M down to a:
        f[s] = f[s] or f[s - a]
answer = f[1..M] 中 true 的个数

逆序枚举 $s$ 保证每枚硬币最多用一次。这个做法语义完全正确，也不需要任何额外理解：它就是「可行性 0/1 背包」重复 $K$ 遍。

拿样例一（$A=(1,2,4)$，$C=(2,1,1)$，$M=10$）走一遍，把每种硬币全部用上时的可达集合列出来：

最后一行的位向量里有 $9$ 个 1，去掉面值 $0$ 得 $8$，与样例输出一致。第二组样例是 $A=(1,4)$、$C=(2,1)$、$M=5$：两枚 1 元和一枚 4 元能拼出 $R=\{0,1,2,4,5\}$，去掉 $0$ 后是 $4$，也与输出相符。观察重点：表格右侧的位向量在逐步「变胖」，而且是整体地变胖——这就是后面优化的抓手。

代码

本层只用文字与表格说明朴素做法，brute.cpp 不单独给出：它与正解共享同一套 0/1 背包语义，差别只在「物品怎么打包」和「状态怎么推进」，单独放一份代码文件不会带来新的信息。

复杂度

$K=\sum_i C_i \leqslant 10^5$ 件物品，每件扫描 $O(M)$ 个面值，时间 $O\big(M \sum_i C_i\big)$，最坏约 $10^{10}$ 次转移；空间 $O(M)$ 个布尔量。

瓶颈

两个瓶颈可以分别消除：

1. 物品太多：每枚硬币单独当一件物品，外层次数被 $\sum_i C_i$ 撑到 $10^5$。
2. 一次只推进一格：内层 for s 每次只处理一个面值 $s$，是标量操作，而 $M=10^5$ 的规模完全可以并行处理。

正解

思路

消除瓶颈一：二进制拆分，把 $C_i$ 件物品压成 $O(\log C_i)$ 组。

$C_i$ 枚同面值硬币不必逐枚考虑，把它们打包成若干「组」，第 $j$ 组含 $2^{j-1}$ 枚，最后一组取剩下的部分。以 $C=10$ 为例，拆成 $1,2,4,3$ 四组：

$0 \sim 10$ 每种枚数都能由这 4 组的某个子集凑出，所以「在 $1,2,4,3$ 上做 0/1 背包」与「在 10 枚单枚硬币上做 0/1 背包」的可达集合完全相同——差别只是同一种取法可能有多种凑法，而可行性问题不关心方案数。物品数随之从 $\sum_i C_i \leqslant 10^5$ 降到 $\sum_i (\lfloor \log_2 C_i\rfloor + 1) \leqslant 1000$。

消除瓶颈二：用一个大整数的比特位表示整个布尔数组。

把 $f$ 压成一个整数 $B$：第 $s$ 位为 $1$ 表示「面值 $s$ 可拼成」，初始 $B=1$（只有空方案 $S=0$）。取一组面值和为 $v$ 的硬币，就是「不取这组」或「取这组」——后者让所有可达面值整体加上 $v$，在位向量上正好是整体左移 $v$ 位：

一句 Python 表达式就完成了整轮转移。int 的 <<、|、& 在 C 层按机器字批量执行，一次操作相当于 $O(M/64)$ 次标量布尔运算，这正是瓶颈二想要的并行度。三处收尾：

• 只关心面值 $\leqslant M$，每组之后用 B &= (1 << (M+1)) - 1 裁掉高位，防止整数无意义地变长。
• 若某组的面值和 $v > M$，它只会在 $>M$ 的位上置 1，对答案没有贡献，直接跳过；面值本身就超过 $M$ 的硬币因此自动失效。
• 最终答案就是 $B$ 中 1 的个数减 1（去掉第 0 位的空集）：B.bit_count() - 1。

正确性：对组数做归纳。假设处理完前若干组后 $B$ 的第 $s$ 位为 1 当且仅当 $s$ 可拼成；新增一组 $v$ 时，「不取」保持原样的可达集合，「取」把每位 $s$ 变成 $s+v$，即 $B \ll v$，两者取或恰是新集合。又因为每一步只做加法、面值恒正，被掩码裁掉的 $>M$ 的位不可能再降回来，裁剪不丢解。归纳成立，算法正确。

代码

batch_sizes(count) 只回答「一种硬币该拆成哪几组」；solve 里 reach 即位向量 $B$，mask 负责裁剪，shift = value * take 是一组的面值和，reach |= reach << shift 就是上面那条转移。

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 硬币组合：多重背包二进制拆分，用位图整体左移表示「面值和能否拼成」。
#include <cstdio>
#include <vector>

typedef long long ll;

const int MAXM = 100005;
unsigned long long W64[(MAXM + 64) / 64 + 16];
int nw;

// reach |= reach << s，然后把超出 m 的位清掉
void shift_or(ll s, ll m) {
    ll ws = s >> 6, bs = s & 63;
    if (bs == 0) {
        for (int i = nw - 1; i >= (int)ws; i--) W64[i] |= W64[i - ws];
    } else {
        for (int i = nw - 1; i > (int)ws; i--) {
            W64[i] |= (W64[i - ws] << bs) | (W64[i - ws - 1] >> (64 - bs));
        }
        W64[ws] |= W64[0] << bs;
    }
    int lastbit = (int)(m >> 6);
    int rem = (int)(m & 63);
    W64[lastbit] &= (rem == 63) ? ~0ULL : ((1ULL << (rem + 1)) - 1);
    for (int i = lastbit + 1; i < nw; i++) W64[i] = 0;
}

int main() {
    ll n, m;
    while (scanf("%lld %lld", &n, &m) == 2) {
        if (n == 0 && m == 0) break; // 终止用例，不产生输出
        std::vector<ll> values(n), counts(n);
        for (ll i = 0; i < n; i++) scanf("%lld", &values[i]);
        for (ll i = 0; i < n; i++) scanf("%lld", &counts[i]);

        nw = (int)((m + 1 + 63) / 64) + 2;
        for (int i = 0; i < nw; i++) W64[i] = 0;
        W64[0] = 1; // 第 0 位 = 空集

        for (ll i = 0; i < n; i++) {
            ll count = counts[i];
            ll size = 1;
            while (count) {
                ll take = size < count ? size : count; // 最后一组可能不满
                ll shift = values[i] * take;
                if (shift <= m) { // 位移超过 m 的组只会落到 m 之外
                    shift_or(shift, m);
                }
                count -= take;
                size <<= 1;
            }
        }

        ll total = 0;
        for (int i = 0; i < nw; i++) total += __builtin_popcountll(W64[i]);
        printf("%lld\n", total - 1); // 去掉第 0 位的空集
    }
    return 0;
}

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 20:24
# update_at: 2026-10-01 20:24

import sys


def batch_sizes(count: int) -> list[int]:
    """把 count 枚同面值硬币拆成 1,2,4,... 枚的若干组，每组当作一件 0/1 物品。"""
    sizes: list[int] = []
    size = 1
    while count:
        take = min(size, count)  # 最后一组可能不满，用 min 一步收尾，不必单独判残留
        sizes.append(take)
        count -= take
        size <<= 1
    return sizes


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []

    while True:
        n, m = next(data), next(data)
        if n == 0 and m == 0:  # 终止用例，不产生输出
            break
        values = [next(data) for _ in range(n)]
        counts = [next(data) for _ in range(n)]

        # 用一个大整数的第 s 位表示「面值 s 能被拼成」，第 0 位 = 空集。
        # 一组面值和 shift 的硬币就是一次整体左移；mask 保证只留下 0..m 位。
        reach: int = 1
        mask = (1 << (m + 1)) - 1
        for value, count in zip(values, counts):
            for take in batch_sizes(count):
                shift = value * take
                if shift <= m:  # 位移超过 m 的组只会落到 m 之外，对答案没有任何影响
                    reach |= reach << shift
                    reach &= mask

        out.append(str(reach.bit_count() - 1))  # 去掉第 0 位的空集

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：$O\big(\frac{M}{w}\sum_i \log_2 C_i\big)$，$w=64$ 为机器字长。按题面上限约为 $1563 \times 1000 \approx 1.6\times10^{6}$ 次字运算，Python 层只执行约 $1000$ 次大整数位运算；相比暴力的 $10^{10}$ 次标量转移降低约 $\sum C_i / \sum \log C_i \approx 100$ 倍。
• 空间复杂度：$O(M)$ 个比特（$10^5$ 位约 13 KB）加一个掩码整数，与 $N$、$C_i$ 无关。

总结

本题是多重背包的可行性版本，两步优化都指向「不要一枚一枚地处理」：用二进制拆分把 $\sum C_i$ 件物品压成 $\sum \log C_i$ 组，再用大整数当 bitset 让整个布尔数组一次左移并取或，$O(M\sum C_i)$ 因此变成 $O(\frac{M}{64}\sum \log C_i)$。Python 里不需要手写 bitset 类，int 本身就是无限宽的位向量，reach |= reach << v 与 reach.bit_count() 已经足够。20 组真实数据实测 0.041 s、峰值内存 15.3 MB，输出与标准答案完全一致。