← 返回题目列表

AtCoder · awc0002_e

E. 糖果拼盘

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

分数: 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