007 - チーム虚無新人賞おめでとう!

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 6 /


TLE
1sec
MLE
64MB
得点
100

問題

ところで、n個の自然数があった。i番目はaiである。

自然数xが与えられるので、自然数をn個から1個以上選んだ時にその総和がxになる組み合わせの数を出力せよ。

入力

n x
a1 
a2 
・
・
・
an

制約

すべての入出力ケースにおいて以下を満たす。
  • 2≦n≦30 1≦x≦1000 1≦ai≦30

小課題

小課題1[1点]

  • n≦20

小課題2[9点]

  • 追加の制約はない

入出力例

入力例1

2 2
1
1

1+1の一通りである。

出力例1

1

入力例2

3 3
1
2
3

1+2と3の二通りである。

出力例2

2

入力例3

10 41
1
2
3
4
5
6
7
8
9
10

出力例3

17
解説(クリックで開く)

この問題は、部分和問題という有名な問題です。解法はDPです。DPを用いればn≦100でも間に合うのですが、制約が小さいため、他の解法でも求めることができます。具体的な解法に関しては、調べた方が分かりやすいので割愛します。