分数: 433 分
问题陈述
高桥发现 N 糖果店里的各种糖果。的价格 i-th (1 \leq i \leq N) 甜蜜的是 A_i 日元。由于每种糖果只有一种库存,因此对于每种糖果,他必须选择“购买”或“不购买”。请注意,不同种类的糖果可能具有相同的价格,但它们仍然被区分为不同的糖果。
高桥正好有 S 日元。因为他想充分利用它,所以他想买正值的糖果 总共 S 日元,没有留下任何钱。
在所有方式中选择 0 或更多糖果 N 种,找出使所选糖果的总价恰好为的方法数 S 日元。请注意,如果没有选择糖果,则总价被视为 0 日元。
约束
- 1 \leq N \leq 40
- 0 \leq S \leq 10^{12}
- 1 \leq A_i \leq 10^{12}
- 所有输入均为整数
输入
N S A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 代表糖果的种类数和一个整数 S 代表高桥拥有的金额,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 代表每种糖果的价格,以空格分隔。
输出
一行打印选择糖果的方法数,使得所选糖果的总价恰好为 S 日元。
示例输入 1
4 10 2 3 5 7
示例输出 1
2
示例输入 2
6 15 1 2 4 5 8 10
示例输出 2
4
示例输入 3
10 1000000000000 100000000000 200000000000 300000000000 400000000000 500000000000 600000000000 700000000000 800000000000 900000000000 1000000000000
示例输出 3
10