← 返回题目列表

AtCoder · arc017_3

C. 讨厌无用之物的人

中文机器翻译题面 查看原题

問題文

我讨厌无用的话,所以我就只说我想说的话,不说不必要的话。
世界上有一种叫做背包问题的东西,其想法是在一定大小的背包中装满物品,使其尽可能有价值,但思考这个问题是没有意义的。
无论价值有多高,我都不能浪费背包里的空间。我讨厌无用的东西。
现在,这是尺寸。 X 背包和 有 N 项。 第
i 项的大小为 w_i 。忽略该物品的价值,因为考虑它是毫无意义的。
有多少种方法可以将物品装入背包而不浪费空间?
换句话说,N 从单品来看,总尺寸堪称完美,没有浪费。 X 有多少种选择?
我尝试直接解决这个问题,但结果证明这是一种浪费的方法,所以我决定问你。
我希望你能帮助我编写一个程序来解决这个问题,而不浪费计算时间,从而节省我的时间。

入力

输入将以以下形式通过标准输入给出。

N X
w_1
w_2
:
w_N
  • 1 行包含一个表示项目数的整数。 N (1 \leq N \leq 32) 和一个表示背包大小的整数 X (1 \leq X \leq 10^9) 由半角空格分隔。 来自行
  • 2 在 N 行中,给出了项目的大小。其中 一个整数,表示第 i (1 \leq i \leq N) 行中,i 个项目的大小 写入 w_i (1 \leq w_i \leq 5 \times 10^7) 。

出力

N 选择一些商品并找到其尺寸的完美总和。 在一行中,打印一个整数,表示有多少种方式可以满足 X 。

入力例1

5 5
1
1
2
3
4

出力例1

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 被视为不同的项目,即使它们具有相同的重量。

入力例2

8 21
10
4
2
30
22
20
8
14

出力例2

0
无论您如何选择商品,它们的尺寸总和都是完美的。 不能将其设为 21 。

入力例3

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

出力例3

45

入力例4

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

出力例4

12870