概要

各グループで選んだ部分集合の XOR を \(X,Y\) とし、\(X+Y=S\) となる選び方の組数を数える問題です。

ポイントは、部分集合 XOR の集合を XOR の線形基底 で表し、同じ XOR 値を作る部分集合数をまとめて扱うことです。

考察

各スキル値は \(2^{20}\) 未満なので、20 ビットのベクトルとみなせます。
部分集合の XOR は、各要素を「選ぶ / 選ばない」による XOR、つまり \(\mathbb{F}_2\) 上の線形結合です。

例えば、あるグループのスキル値が

[ 1, 2, 3 ]

だとすると、\(3 = 1 \oplus 2\) なので、独立な値は \(1,2\) の 2 個だけです。
このような独立な値の集合を XOR 線形基底 と呼びます。

あるグループの XOR 線形基底のランクを \(r\) とすると、

• 作れる XOR 値の種類数は \(2^r\)
• 各 XOR 値を作る部分集合の個数はすべて等しく \(2^{N-r}\)

になります。

したがって、第 1 グループのランクを \(r_A\)、第 2 グループのランクを \(r_B\) とすると、まず

[ (x,y) \quad (x \in V_A,\ y \in V_B,\ x+y=S) ]

を満たす XOR 値の組数 を数えればよいです。
ここで \(V_A,V_B\) はそれぞれのグループで作れる XOR 値の集合です。

その値の組数を \(P\) とすると、実際の部分集合の選び方の組数は

[

P \times 2^{N-r_A} \times 2^{N-r_B}

P \times 2^{2N-r_A-r_B} ]

です。

素朴な方法がだめな理由

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

一方で、XOR 値は 20 ビットなので高々 \(2^{20}\) 種類しかありません。
線形基底を使うことで、部分集合そのものではなく「作れる XOR 値」だけを効率よく扱えます。

また、同じ XOR 値を作る部分集合が複数あるため、単に XOR 値の集合だけを数えると WA になります。
最後に \(2^{N-r}\) を掛ける必要があります。

アルゴリズム

\(D=20\)、\(M=2^D\) とします。
各 XOR 値は必ず \(0\) 以上 \(M-1\) 以下です。

1. 第 1 グループ、第 2 グループそれぞれについて XOR 線形基底を作る

   • ランクをそれぞれ \(r_A,r_B\) とする

2. 作れる XOR 値の組数 \(P\) を数える

   • ランクが小さい方の空間を列挙する
   • もう一方の空間について、ある値が作れるかを高速に判定できるようにする

3. 値 \(z\) を一方のグループで作れる XOR 値として列挙する

   • もう一方で必要な値は \(S-z\)
   • \(S-z\) が \(0\) 以上 \(M-1\) 以下で、かつもう一方の空間に含まれていれば 1 組数える

4. 最後に

[ 2^{2N-r_A-r_B} ]

を掛ける

値の範囲について

\(z\) に対して、もう一方の値 \(S-z\) が XOR 値としてあり得るには

[ 0 \leq S-z < M ]

である必要があります。
これは

[ S-M+1 \leq z \leq S ]

と同値です。

さらに \(z\) 自身も \(0 \leq z < M\) なので、列挙時には

[ \max(0, S-M+1) \leq z \leq \min(M-1, S) ]

だけを確認すればよいです。

ランク 20 の場合

ランクが 20 の場合、そのグループではすべての 20 ビット値

[ 0,1,\ldots,2^{20}-1 ]

を作れます。

その場合は membership 配列を作る必要がなく、範囲条件だけで判定できます。

計算量

\(D=20\) とします。

• 時間計算量: \(O(ND + 2^D)\)
• 空間計算量: \(O(2^D)\)

\(2^{20}=1,048,576\) なので、十分高速に処理できます。

実装のポイント

• XOR 線形基底は、各値の最上位ビットを見ながら掃き出し法のように作ります。

• 基底のランクが \(r\) なら、作れる XOR 値は \(2^r\) 個です。

• 列挙は Gray code 的に行うことで、毎回 XOR を一から計算せずに済みます。

  • コード中の

  (i & -i).bit_length() - 1
  

  は、次に反転する基底の番号を求めています。

• membership 判定には長さ \(2^{20}\) の bytearray を使っています。

  • set よりも高速かつ省メモリです。

• 最後の掛け算

[ 2^{2N-r_A-r_B} ]

は、コードでは左シフト << によって実装しています。

ソースコード

import sys

DIM = 20
M = 1 << DIM

def build_basis(arr):
    basis = [0] * DIM
    rank = 0
    for x in arr:
        v = x
        while v:
            i = v.bit_length() - 1
            if basis[i]:
                v ^= basis[i]
            else:
                basis[i] = v
                rank += 1
                break
    return [x for x in basis if x], rank

def make_membership(bs):
    mem = bytearray(M)
    mem[0] = 1
    cur = 0
    total = 1 << len(bs)
    for i in range(1, total):
        cur ^= bs[(i & -i).bit_length() - 1]
        mem[cur] = 1
    return mem

def count_with_membership(bs, mem, S):
    lo = S - M + 1
    if lo < 0:
        lo = 0
    hi = S
    if hi >= M:
        hi = M - 1
    if lo > hi:
        return 0

    cnt = mem[S] if lo == 0 else 0
    cur = 0
    total = 1 << len(bs)

    for i in range(1, total):
        cur ^= bs[(i & -i).bit_length() - 1]
        if cur >= lo and cur <= hi:
            cnt += mem[S - cur]
    return cnt

def count_with_full_space(bs, S):
    lo = S - M + 1
    if lo < 0:
        lo = 0
    hi = S
    if hi >= M:
        hi = M - 1
    if lo > hi:
        return 0

    if len(bs) == DIM:
        return hi - lo + 1

    cnt = 1 if lo == 0 else 0
    cur = 0
    total = 1 << len(bs)

    for i in range(1, total):
        cur ^= bs[(i & -i).bit_length() - 1]
        if cur >= lo and cur <= hi:
            cnt += 1
    return cnt

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

    basis_a, rank_a = build_basis(A)
    basis_b, rank_b = build_basis(B)

    if rank_a <= rank_b:
        enum_basis = basis_a
        mark_basis = basis_b
        mark_rank = rank_b
    else:
        enum_basis = basis_b
        mark_basis = basis_a
        mark_rank = rank_a

    if mark_rank == DIM:
        pairs = count_with_full_space(enum_basis, S)
    else:
        mem = make_membership(mark_basis)
        pairs = count_with_membership(enum_basis, mem, S)

    ans = pairs << (2 * N - rank_a - rank_b)
    print(ans)

if __name__ == "__main__":
    main()

---

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