AT_arc017_3.[ARC017C] 無駄なものが嫌いな人

我讨厌无用的东西，所以只说我想说的，不说废话。
世上有一种叫做“背包问题”的东西，就是考虑如何把物品装进一个固定大小的背包，使得价值尽可能高，但我觉得考虑这些都是无用的。
即使价值再高，如果背包里出现了多余的空间，我也无法容忍。我讨厌无用的东西。
现在，这里有一个大小为 $X$ 的背包和 $N$ 个物品。
第 $i$ 个物品的大小为 $w_i$。至于物品的价值，考虑也没用，所以忽略不计。
有多少种方法可以装物品，使得背包里没有多余的空间呢？
也就是说，从 $N$ 个物品中选出若干个，使得它们的大小之和恰好等于 $X$，有多少种选法？
我一开始想用手算这个问题，但发现这是一种无用的手段，所以决定拜托你来做。
请写一个没有无用计算时间的程序来解决这个问题，帮我节省无用的时间。

输入通过标准输入按以下格式给出。

$N$ $X$
$w_1$
$w_2$
$\vdots$
$w_N$

• 第 1 行给出表示物品个数的整数 $N\ (1\leq N\leq 32)$ 和表示背包大小的整数 $X\ (1\leq X\leq 10^9)$，两者以半角空格分隔。
• 第 2 行到第 $N$ 行，每行给出一个物品的大小。第 $i$ 行为第 $i$ 个物品的大小 $w_i\ (1\leq w_i\leq 5\times 10^7)$。

请输出一个整数，表示从 $N$ 个物品中选出若干个，使得它们的大小之和恰好等于 $X$ 的选法数。

例如：

5 5
1
1
2
3
4

输出：

4

无多余空间的选法有以下 $4$ 种：

• 选择物品 $1$、物品 $2$、物品 $4$：$1+1+3=5$
• 选择物品 $1$、物品 $5$：$1+4=5$
• 选择物品 $2$、物品 $5$：$1+4=5$
• 选择物品 $3$、物品 $4$：$2+3=5$

注意，物品 $1$ 和物品 $2$ 虽然重量相同，但视为不同的物品。

8 21
10
4
2
30
22
20
8
14

输出：

0

无论如何选择物品，都无法使大小之和恰好为 $21$。

20 100000000
35576749
38866484
6624951
39706038
11133516
25490903
14701702
17888322
14423251
32111678
24509097
43375049
35298298
21158709
30489274
37977301
19510726
28841291
10293962
12022699

输出：

45

16 8
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

输出：

12870

第 1 行：两个整数 $N$ 和 $X$，以空格分隔。
第 2 行到第 $N+1$ 行：每行一个整数 $w_i$，表示第 $i$ 个物品的大小。

输出一个整数，表示选出若干个物品，使得它们的大小之和恰好等于 $X$ 的选法数。

• 物品的个数 $N$ 不超过 $32$，可以考虑使用“折半枚举”或“meet-in-the-middle”算法。
• 物品的大小和背包容量都可能很大，不能用常规的动态规划。
• 物品可以不选，也可以全部选，选法数包括所有可能的子集。
• 物品即使大小相同，也视为不同的物品。

由 ChatGPT 4.1 翻译