概要

2つのグループからそれぞれメンバーの部分集合を選び、各グループの選ばれたメンバーのスキル値の XOR（排他的論理和）を \(X, Y\) としたとき、\(X + Y = S\) を満たすような選び方の総数を求める問題です。

---

考察

素朴なアプローチとその限界

各グループのメンバー数は最大で \(N = 50\) です。 素直にすべての部分集合の選び方を全探索しようとすると、1つのグループだけでも \(2^{50} \approx 1.1 \times 10^{15}\) 通りあり、制限時間内に計算することは不可能です。

重要な観察

1. 値の範囲が小さい スキル値 \(A_i, B_i\) は \(2^{20}\) 未満（\(0\) から \(1,048,575\) まで）です。したがって、部分集合の XOR 和として作りうる値も必ず \(2^{20}\) 未満になります。 取りうる値の種類数が高々 \(2^{20} \approx 10^6\) 通りしかないことに注目します。

2. 線形基底（Linear Basis）の導入 XOR 和の集合を効率的に扱うために、線形代数の「基底」の考え方を応用した線形基底を利用します。

サイズ \(N\) の数論的ベクトル空間において、任意の要素の XOR 和で作れる値の集合は、いくつかの「線形独立」な要素（基底）の XOR 和で作れる値の集合と一致します。 値が \(2^{20}\) 未満であるため、基底のサイズ \(K\) は最大でも \(20\) になります。

1. 選び方の数の規則性 元の \(N\) 個の要素からサイズ \(K\) の基底を取り出したとき、基底に含まれない残りの \(N - K\) 個の要素（非基底）の選び方は \(2^{N-K}\) 通りあります。

非基底の要素をどのように選んでも、その XOR 和を補うように基底の要素を一意に選ぶことで、基底から作れる任意の XOR 和 \(v\) を実現できます。 したがって、基底から作れる任意の XOR 和 \(v\) について、元の配列から XOR 和が \(v\) になるような部分集合の選び方は一律で \(2^{N-K}\) 通りになります。

これを利用すると、探索空間を \(2^{50}\) から \(2^{20}\) へと劇的に削減できます。

---

アルゴリズム

1. 線形基底の抽出

各グループの配列 \(A, B\) から、掃き出し法（ガウスの消去法）を用いて線形基底 basisA, basisB を求めます。 最大ビット（19ビット目）から順に走査し、基底となる要素を決定します。

2. XOR 和の全列挙と組み合わせ数の記録

求めた基底から作られるすべての XOR 和を列挙します。 基底のサイズを \(K\) とすると、作られる XOR 和は \(2^K\) 個（最大 \(2^{20} \approx 10^6\) 個）です。

各 XOR 和 \(v\) に対して、それを作る部分集合の選び方の数（\(2^{N-K}\) 通り）を配列 dpA[v], dpB[v] に記録します。

3. 条件を満たす組の集計

\(X + Y = S\) を満たすペアを探索します。 \(X\) を \(0\) から \(2^{20}-1\) まで走査し、対応する \(Y = S - X\) が \(0 \le Y < 2^{20}\) の範囲に収まる場合、dpA[X] * dpB[Y] を答えに加算します。

---

計算量

• 時間計算量: \(O(N \log (\max A_i) + 2^{\log(\max A_i)})\)

  • 基底の抽出: \(O(N \log(\max A_i))\)。\(N \le 50\), \(\log(\max A_i) \le 20\) なので、約 \(1000\) 回の演算。
  • XOR 和の列挙と集計: \(O(2^K)\)。\(K \le 20\) なので、最大でも \(2^{20} \approx 1.05 \times 10^6\) 回のループ。
  • 全体として、実行時間は数ミリ秒〜数十ミリ秒程度で非常に高速に動作します。

• 空間計算量: \(O(2^{\log(\max A_i)})\)

  • XOR 和の出現回数を記録する配列のサイズは \(2^{20}\)（約 100万要素）であり、メモリ制限に対して十分に余裕があります。

---

実装のポイント

• 基底の構築: get_basis 関数では、各要素に対してすでに得られている基底との XOR を取ることで、線形従属な成分を消去し、新しく独立な値が残った場合のみ基底に追加しています。

• 集計時のインデックス制御: \(Y = S - X\) が \(0 \le Y < 2^{20}\) を満たす必要があります。 無駄なループを避けるため、探索する \(X\) の範囲を start = max(0, S - LIMIT + 1) から end = min(S, LIMIT - 1) に制限して、配列の範囲外参照を防いでいます。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    S = int(data[1])
    A = [int(x) for x in data[2:2+N]]
    B = [int(x) for x in data[2+N:2+2*N]]
    
    def get_basis(arr):
        basis = []
        for x in arr:
            for b in basis:
                x = min(x, x ^ b)
            if x > 0:
                basis.append(x)
                basis.sort(reverse=True)
        return basis

    basisA = get_basis(A)
    basisB = get_basis(B)
    
    def get_all_xor_sums(basis):
        sums = [0]
        for g in basis:
            sums += [x ^ g for x in sums]
        return sums

    LIMIT = 1 << 20
    dpA = [0] * LIMIT
    dpB = [0] * LIMIT
    
    valA = 1 << (N - len(basisA))
    for v in get_all_xor_sums(basisA):
        dpA[v] = valA
        
    valB = 1 << (N - len(basisB))
    for v in get_all_xor_sums(basisB):
        dpB[v] = valB
        
    ans = 0
    start = max(0, S - LIMIT + 1)
    end = min(S, LIMIT - 1)
    
    for X in range(start, end + 1):
        ans += dpA[X] * dpB[S - X]
        
    print(ans)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.5-flash-high によって生成されました。