概要

\(2\) つのグループからそれぞれ部分集合を選び、XOR の和が \(S\) になる選び方の組の数を数える問題です。XOR の部分集合が作る値が「線形空間」になることを利用して効率的に数えます。

考察

素朴なアプローチの問題点

各グループの部分集合は \(2^N\) 通りあり、\(N \leq 50\) なので全探索すると \(2^{50} \times 2^{50}\) 通りとなり、到底間に合いません。

重要な気づき：XOR 部分集合は線形空間をなす

ある数列から選んだ部分集合の XOR で作れる値の集合は、GF(2) 上の線形空間（span） になります。この空間の次元（ランク）を \(r\) とすると、

• 作れる 異なる値 はちょうど \(2^{r}\) 種類
• そして どの値も、ちょうど \(2^{N-r}\) 個の部分集合から作られる

という重要な性質があります。

たとえば \(A = [1, 1]\) の場合、作れる XOR は \(0\)（空集合 or 両方選ぶ）と \(1\)（片方だけ選ぶ）の \(2\) 種類です。\(N=2\)、ランク \(r=1\) なので、各値は \(2^{2-1}=2\) 個の部分集合から作られます。実際 \(0\) は「空集合」と「\(\{1,1\}\)」の \(2\) 通り、\(1\) は「\(\{A_1\}\)」と「\(\{A_2\}\)」の \(2\) 通りで一致します。

解決方針

この性質により、問題は次のように分解できます。

1. グループ \(1, 2\) それぞれで、作れる 異なる XOR 値の集合（span）と ランク を求める。
2. \(X \in \text{span}_A\) かつ \(Y \in \text{span}_B\) かつ \(X + Y = S\) を満たす 値の組 \((X, Y)\) の個数を数える。
3. 各値の組に対し、それを実現する部分集合の組み合わせ数 \(2^{N-r_A} \times 2^{N-r_B}\) を掛ける。

値の種類は \(A_i, B_i < 2^{20}\) よりランクは高々 \(20\) なので、span のサイズは最大でも \(2^{20} \approx 10^6\) 程度で扱えます。

アルゴリズム

1. 基底（basis）の構築

掃き出し法（ガウスの消去法の GF(2) 版）で線形基底を作ります。各数を上位ビットから見て、そのビットを持つ基底があれば XOR で消し、なければ新しい基底として追加します。追加された基底の本数がランク \(r\) です。

2. span の列挙

基底の各要素を「使う／使わない」の全組み合わせで XOR を取ると、span（作れる値の集合）が列挙できます。基底が \(r\) 本なら \(2^r\) 個の値が得られます。

3. 組の数え上げ

• \(\text{span}_B\) を集合（set）にしておく。
• \(\text{span}_A\) の各値 \(x\) について、\(S - x\) が \(\text{span}_B\) に含まれるか（かつ \(S-x \geq 0\)）を確認し、含まれれば \(1\) つ数える。

4. 倍率を掛ける

最後に、数えた値の組の個数に \(2^{N-r_A} \times 2^{N-r_B}\) を掛けたものが答えです。

なお、XOR の和ではなく通常の整数の加算 \(X+Y=S\) なので、ビットごとに独立に処理することはできず、上記のように値の集合を実際に列挙して照合する必要があります（\(S < 2^{21}\)、span の値 \(< 2^{20}\) なので範囲も十分収まります）。

計算量

ランクを \(r\)（\(\leq 20\)）とします。span のサイズは \(2^r\) です。

• 時間計算量: \(O(N \cdot 20 + 2^{r})\)（基底構築と span の列挙・照合）。最悪でも \(2^{20}\) 程度。
• 空間計算量: \(O(2^{r})\)（span を保持するため）。最悪 \(2^{20}\) 程度。

実装のポイント

• ビット幅に注意：\(A_i, B_i < 2^{20}\) なので基底配列は \(0\)〜\(20\) ビット（長さ \(21\)）を確保します。

• \(S - x \geq 0\) の確認：\(S - x\) が負になる場合は set の照合だけでも弾けますが、引き算の結果が範囲外にならないよう意識します。

• 倍率の計算：(1 << (N - rankA)) * (1 << (N - rankB)) で各値の組に対する部分集合の組み合わせ数を掛けます。\(N\) が大きいので \(2^{N-r}\) は巨大になり得ますが、答えは \(2^{63}\) 未満が保証されているため Python の多倍長整数でそのまま扱えます。

  ソースコード

import sys

def get_basis(arr):
    basis = [0] * 21
    rank = 0
    for v in arr:
        cur = v
        for i in range(20, -1, -1):
            if not (cur >> i) & 1:
                continue
            if basis[i] == 0:
                basis[i] = cur
                rank += 1
                break
            cur ^= basis[i]
    bs = [basis[i] for i in range(21) if basis[i]]
    return bs, rank

def main():
    data = sys.stdin.buffer.read().split()
    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]]

    bsA, rankA = get_basis(A)
    bsB, rankB = get_basis(B)

    # enumerate span A
    spanA = [0]
    for b in bsA:
        spanA = spanA + [x ^ b for x in spanA]

    # enumerate span B as set
    spanB = [0]
    for b in bsB:
        spanB = spanB + [x ^ b for x in spanB]
    setB = set(spanB)

    count = 0
    for x in spanA:
        if (S - x) in setB:
            count += 1

    factor = (1 << (N - rankA)) * (1 << (N - rankB))
    print(count * factor)

main()

---

この解説は claude4.8opus-high によって生成されました。