概要

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

ポイントは、各グループで作れる XOR 値の集合を「XOR 線形基底」で表し、同じ XOR 値を作る部分集合数をまとめて数えることです。

考察

各グループの部分集合は \(2^N\) 通りあります。
しかし \(N \leq 50\) なので、全ての部分集合を列挙すると最大で

\[ 2^{50} \]

通りとなり、到底間に合いません。

ここで重要なのは、スキル値がすべて

\[ 0 \leq A_i, B_i < 2^{20} \]

であることです。

つまり、XOR の結果も常に \(0\) 以上 \(2^{20}\) 未満です。
XOR は各ビットごとの足し算を \(2\) で割った余りとして見られるので、部分集合 XOR の集合は「\(20\) 次元以下のベクトル空間」になります。

例えば、第 \(1\) グループで作れる XOR 値の集合を考えると、

\[ c_1 A_1 \oplus c_2 A_2 \oplus \cdots \oplus c_N A_N \]

という形で表せます。
ここで \(c_i\) は、そのメンバーを選ぶなら \(1\)、選ばないなら \(0\) です。

これは XOR に関する線形結合なので、作れる XOR 値全体は XOR 線形基底によって表せます。

---

線形基底のランクを \(r\) とすると、作れる異なる XOR 値の個数は

\[ 2^r \]

個です。

また、元のメンバー数は \(N\) 人なので、部分集合の選び方は \(2^N\) 通りあります。
そのうち異なる XOR 値が \(2^r\) 個あるため、各 XOR 値を作る部分集合の個数は等しく

\[ 2^{N-r} \]

個になります。

これは線形写像の核の大きさが \(2^{N-r}\) であることに対応しています。

したがって、

• 第 \(1\) グループのランクを \(r_A\)
• 第 \(2\) グループのランクを \(r_B\)

とすると、異なる XOR 値の組 \((X,Y)\) で \(X+Y=S\) を満たすものを数え、その個数に

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

を掛ければ答えになります。

---

注意点として、条件は

\[ X \oplus Y = S \]

ではなく、

\[ X + Y = S \]

です。

ここでの \(+\) は通常の整数加算なので、XOR の線形性だけで直接処理することはできません。
そのため、各グループで作れる XOR 値を列挙し、\(X\) に対して

\[ Y = S - X \]

が第 \(2\) グループで作れるかを調べます。

アルゴリズム

まず、各グループについて XOR 線形基底を作ります。

1. XOR 線形基底を作る

各値 \(x\) を基底に追加します。

上位ビットから見て、まだそのビットを最高位ビットに持つ基底がなければ追加します。
すでにある場合は XOR して消去します。

これにより、独立な値だけが基底に残ります。

2. 作れる XOR 値を列挙する

基底が \(r\) 個あるとき、作れる XOR 値は \(2^r\) 個です。

最初に集合を

\[ \{0\} \]

としておき、基底の値 \(v\) ごとに、現在ある値すべてに対して \(v\) を XOR した値を追加します。

例えば、現在の集合が

\[ \{0, 1\} \]

で、新しい基底が \(2\) なら、

\[ 0 \oplus 2 = 2 \]

\[ 1 \oplus 2 = 3 \]

を追加して、

\[ \{0, 1, 2, 3\} \]

になります。

3. 第 \(2\) グループの XOR 値を高速に検索できるようにする

第 \(2\) グループで作れる XOR 値を列挙し、配列 in_b に記録します。

値の範囲は \(0\) 以上 \(2^{20}\) 未満なので、長さ \(2^{20}\) の配列で管理できます。

4. 条件を満たす異なる XOR 値の組を数える

第 \(1\) グループで作れる各値 \(x\) について、

\[ y = S - x \]

を計算します。

もし

\[ 0 \leq y < 2^{20} \]

かつ、第 \(2\) グループで \(y\) が作れるなら、異なる XOR 値の組 \((x,y)\) が \(1\) つ見つかります。

この個数を pair_count とします。

5. 部分集合の選び方の個数に変換する

異なる XOR 値の組ごとに、

• 第 \(1\) グループで \(x\) を作る部分集合は \(2^{N-r_A}\) 通り
• 第 \(2\) グループで \(y\) を作る部分集合は \(2^{N-r_B}\) 通り

あります。

よって答えは

\[ \text{pair\_count} \times 2^{N-r_A} \times 2^{N-r_B} \]

です。

まとめると、

\[ \text{ans} = \text{pair\_count} \times 2^{(N-r_A)+(N-r_B)} \]

となります。

計算量

• 時間計算量: \(O(N \log M + 2^{r_A} + 2^{r_B} + M)\)
• 空間計算量: \(O(2^{r_A} + 2^{r_B} + M)\)

ただし、

\[ M = 2^{20} \]

です。

また、\(r_A, r_B \leq 20\) なので、実質的には

• 時間計算量: \(O(N \cdot 20 + 2^{20})\)
• 空間計算量: \(O(2^{20})\)

程度で十分高速です。

実装のポイント

XOR 線形基底では、basis[b] に「最高位ビットが \(b\) の基底」を保存しています。

for (int b = LOG - 1; b >= 0; --b) {
    if (((x >> b) & 1) == 0) continue;
    if (!basis[b]) {
        basis[b] = x;
        rank++;
        return;
    }
    x ^= basis[b];
}

この処理で、すでにある基底で表せる値は追加されず、独立な値だけが追加されます。

また、答えは \(2^{63}\) 未満と保証されていますが、計算途中のシフトなどで安全に扱うため、コードでは __int128 を使っています。

__int128 ans = (__int128)pair_count << exponent;

最後に __int128 はそのまま cout できないため、専用の出力関数で十進文字列に変換して出力しています。

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct LinearBasis {
    static constexpr int LOG = 20;
    int basis[LOG]{};
    int rank = 0;

    void add(int x) {
        for (int b = LOG - 1; b >= 0; --b) {
            if (((x >> b) & 1) == 0) continue;
            if (!basis[b]) {
                basis[b] = x;
                rank++;
                return;
            }
            x ^= basis[b];
        }
    }

    vector<int> enumerate() const {
        vector<int> vals;
        vals.reserve(1 << rank);
        vals.push_back(0);

        for (int b = 0; b < LOG; ++b) {
            if (!basis[b]) continue;
            int sz = vals.size();
            for (int i = 0; i < sz; ++i) {
                vals.push_back(vals[i] ^ basis[b]);
            }
        }
        return vals;
    }
};

void print_int128(__int128 x) {
    if (x == 0) {
        cout << 0 << '\n';
        return;
    }
    string s;
    while (x > 0) {
        s.push_back(char('0' + x % 10));
        x /= 10;
    }
    reverse(s.begin(), s.end());
    cout << s << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, S;
    cin >> N >> S;

    LinearBasis la, lb;

    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        la.add(a);
    }

    for (int i = 0; i < N; ++i) {
        int b;
        cin >> b;
        lb.add(b);
    }

    constexpr int M = 1 << 20;

    vector<int> avals = la.enumerate();
    vector<int> bvals = lb.enumerate();

    vector<unsigned char> in_b(M, 0);
    for (int y : bvals) in_b[y] = 1;

    long long pair_count = 0;
    for (int x : avals) {
        int y = S - x;
        if (0 <= y && y < M && in_b[y]) {
            pair_count++;
        }
    }

    int exponent = (N - la.rank) + (N - lb.rank);
    __int128 ans = (__int128)pair_count << exponent;

    print_int128(ans);

    return 0;
}

---

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