No.044 C

動的計画法を使う.

$i$ 枚目のカードまで見たときに $j$ 枚使って合計が $k$ となる組み合わせの数を $C(i, j, k)$ とする.

このとき,

$$C(i, j, k) = C(i-1, j, k) + C(i-1, j-1, k-x_i)$$

となる. これを DP で更新していき, 最後に $C(N, i, iA)$ を合計する.

なお組み合わせの数は最大で $2^{50}$ なので long の範囲に収まる.