概要

\(N \le 40\) 個の品物からいくつか選んで合計がちょうど \(S\) になる選び方の数を数えます。全探索 \(2^N\) は大きすぎるため、半分に分けて数える「Meet-in-the-Middle」で解きます。

考察

各お菓子は「買う/買わない」の2択なので、素朴には全ての部分集合を調べて合計が \(S\) かどうかを数えればよいです。しかし計算量は \(2^N\) で、\(N=40\) のとき \(2^{40} \approx 10^{12}\) 通りとなり、現実的な時間では終わりません（TLE）。

ここで重要な気づきは、「40個は多いが、20個ずつなら全列挙できる」という点です。
\(N\) 個を左右の2グループに分け、左の部分集合和の一覧 \(L\)、右の部分集合和の一覧 \(R\) を作ります。すると「左から和が \(x\)、右から和が \(S-x\)」となる組の数を数えれば答えになります。

例えば \(S=10\) のとき、左で \(3\) 円作る方法が \(c_1\) 通り、右で \(7\) 円作る方法が \(c_2\) 通りなら、合計 \(10\) 円になる組み合わせは \(c_1 \times c_2\) 通りあります。
値段が同じでも別のお菓子は別物なので、「部分集合和の重複」は“通り数”として正しく数える必要があります。

アルゴリズム

1. 配列 \(A\) を前半と後半に分割する（左: \(n_1=\lfloor N/2 \rfloor\) 個、右: \(N-n_1\) 個）。
2. 左側について、全ての部分集合和を列挙して配列 \(L\) に入れる。右側も同様に \(R\) を作る。
   
   • 部分集合和は、初期 \([0]\) から始め、各要素 \(a\) について「既存の和 \(s\)」と「\(s+a\)」を追加していけば \(2^k\) 個作れる。
3. \(L\) と \(R\) をソートする。
4. 二本のポインタで「\(L[i] + R[j]\) が \(S\) になる組数」を数える（\(i\) は小さい方から、\(j\) は大きい方から動かす）。
   • もし \(L[i]+R[j]=S\) なら、同じ値が連続している個数をそれぞれ数え（\(c_1, c_2\)）、\(ans += c_1 \times c_2\) として一気に加算する。
   • もし和が小さければ \(i\) 側を進め、大きければ \(j\) 側を戻す。
   • 同じ値が連続している部分はまとめてスキップし、無駄な比較を減らす。

この方法で、全探索 \(2^{40}\) を、\(2^{20}\) 規模の列挙＋ソート＋線形走査に落とせます。

計算量

左右の要素数をそれぞれ \(n_1, n_2\) とすると、\(|L|=2^{n_1}, |R|=2^{n_2}\) です。 - 時間計算量: \(O(2^{n_1} + 2^{n_2} + 2^{n_1}\log 2^{n_1} + 2^{n_2}\log 2^{n_2})\)
（支配的には \(O(2^{N/2}\,N)\) 程度） - 空間計算量: \(O(2^{n_1} + 2^{n_2})\)

実装のポイント

• 部分集合和の列挙は sums.extend([sums[i] + a for i in range(m)]) のように「今ある分だけ」を元に拡張すると簡潔です。

• 重複の数え上げが重要です。同じ和が複数回出るのは「異なる選び方」が存在することを意味するので、c1 * c2 を加算する必要があります。

• \(S\) や \(A_i\) は最大 \(10^{12}\) ですが、Python の整数は桁あふれしないためそのまま扱えます。

• 入力が大きくなり得るので sys.stdin.buffer.read() を使うと安定します。

  ソースコード

import sys

def all_sums(arr):
    sums = [0]
    for a in arr:
        m = len(sums)
        sums.extend([sums[i] + a for i in range(m)])
    return sums

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    S = int(data[1])
    A = list(map(int, data[2:]))

    n1 = N // 2
    left = A[:n1]
    right = A[n1:]

    L = all_sums(left)
    R = all_sums(right)
    L.sort()
    R.sort()

    i, j = 0, len(R) - 1
    ans = 0

    while i < len(L) and j >= 0:
        s = L[i] + R[j]
        if s == S:
            v1 = L[i]
            c1 = 0
            while i < len(L) and L[i] == v1:
                c1 += 1
                i += 1

            v2 = R[j]
            c2 = 0
            while j >= 0 and R[j] == v2:
                c2 += 1
                j -= 1

            ans += c1 * c2
        elif s < S:
            v1 = L[i]
            while i < len(L) and L[i] == v1:
                i += 1
        else:
            v2 = R[j]
            while j >= 0 and R[j] == v2:
                j -= 1

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。