/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 433 点
問題文
高橋君は駄菓子屋で N 種類のお菓子を見つけました。i 番目 (1 \leq i \leq N) のお菓子の値段は A_i 円です。各お菓子は 1 つずつしか在庫がないため、それぞれのお菓子について「買う」か「買わない」かのどちらかを選びます。なお、異なる種類のお菓子であっても値段が同じことがありますが、それらは異なるお菓子として区別します。
高橋君はちょうど S 円を持っています。せっかくなので、手持ちのお金を余らせず、ぴったり S 円分のお菓子を買いたいと考えています。
N 種類のお菓子から 0 個以上を選ぶ方法のうち、選んだお菓子の値段の合計がちょうど S 円になるような選び方は何通りあるか求めてください。ただし、1 つもお菓子を選ばない場合、値段の合計は 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
- 1 行目には、お菓子の種類数を表す整数 N と、高橋君の所持金を表す整数 S が、スペース区切りで与えられる。
- 2 行目には、各お菓子の値段を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
選んだお菓子の値段の合計がちょうど S 円になるような選び方の個数を 1 行で出力してください。
入力例 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
Score : 433 pts
Problem Statement
Takahashi found N kinds of sweets at a candy shop. The price of the i-th (1 \leq i \leq N) sweet is A_i yen. Since there is only one of each sweet in stock, for each sweet he must choose either "buy" or "don't buy." Note that different kinds of sweets may have the same price, but they are still distinguished as different sweets.
Takahashi has exactly S yen. Since he wants to make the most of it, he would like to buy sweets that cost exactly S yen in total, without leaving any money.
Among all ways to select 0 or more sweets from the N kinds, find the number of ways such that the total price of the selected sweets is exactly S yen. Note that if no sweets are selected, the total price is considered to be 0 yen.
Constraints
- 1 \leq N \leq 40
- 0 \leq S \leq 10^{12}
- 1 \leq A_i \leq 10^{12}
- All inputs are integers
Input
N S A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of kinds of sweets and an integer S representing the amount of money Takahashi has, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the price of each sweet, separated by spaces.
Output
Print in one line the number of ways to select sweets such that the total price of the selected sweets is exactly S yen.
Sample Input 1
4 10 2 3 5 7
Sample Output 1
2
Sample Input 2
6 15 1 2 4 5 8 10
Sample Output 2
4
Sample Input 3
10 1000000000000 100000000000 200000000000 300000000000 400000000000 500000000000 600000000000 700000000000 800000000000 900000000000 1000000000000
Sample Output 3
10