Overview

This problem asks us to count the number of pairs of subsets such that \(X+Y=S\), where \(X\) and \(Y\) are the XOR sums of the chosen subsets in each group, respectively.

The key is to represent the set of possible XOR values that can be formed by each group using an “XOR linear basis”, and count the number of subsets that form the same XOR value collectively.

Analysis

There are \(2^N\) possible subsets for each group.
However, since \(N \leq 50\), enumerating all subsets would take up to

\[ 2^{50} \]

operations, which is far too slow.

The crucial point here is that all skill values satisfy

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

This means that the XOR sums are also always at least \(0\) and strictly less than \(2^{20}\).
Since XOR can be viewed as addition modulo \(2\) for each bit, the set of subset XOR sums forms a “vector space of dimension at most \(20\)”.

For example, considering the set of possible XOR values that can be formed by the first group, they can be represented in the form:

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

where \(c_i\) is \(1\) if the member is chosen, and \(0\) otherwise.

Since this is a linear combination over XOR, the set of all possible XOR values can be represented by an XOR linear basis.

---

If the rank of the linear basis is \(r\), the number of distinct possible XOR values is

\[ 2^r \]

Also, since there are \(N\) members originally, there are \(2^N\) ways to choose a subset.
Since there are \(2^r\) distinct XOR values, the number of subsets that form each XOR value is equally

\[ 2^{N-r} \]

This corresponds to the size of the kernel of the linear map being \(2^{N-r}\).

Therefore, if we let

• \(r_A\) be the rank of the first group
• \(r_B\) be the rank of the second group

we can count the number of pairs of distinct XOR values \((X,Y)\) satisfying \(X+Y=S\), and multiply this count by

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

to obtain the answer.

---

Note that the condition is

\[ X + Y = S \]

and not

\[ X \oplus Y = S \]

Since \(+\) here is standard integer addition, we cannot process it directly using only the linearity of XOR.
Therefore, we generate all possible XOR values for each group, and for each \(X\), we check if

\[ Y = S - X \]

can be formed by the second group.

Algorithm

First, we construct the XOR linear basis for each group.

1. Constructing the XOR Linear Basis

We insert each value \(x\) into the basis.

Iterating from the most significant bit downward, if there is no basis element that has this bit as its most significant bit, we insert it.
If there is already one, we XOR it and continue.

This ensures that only linearly independent values remain in the basis.

2. Generating Possible XOR Values

When there are \(r\) elements in the basis, \(2^r\) distinct XOR values can be formed.

We start with the set

\[ \{0\} \]

For each basis element \(v\), we take all elements currently in the set, XOR them with \(v\), and add the results to the set.

For example, if the current set is

\[ \{0, 1\} \]

and the new basis element is \(2\), we add

\[ 0 \oplus 2 = 2 \]

\[ 1 \oplus 2 = 3 \]

to get

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

3. Enabling Fast Search for the Second Group’s XOR Values

We generate all possible XOR values for the second group and record them in an array in_b.

Since the values are in the range \([0, 2^{20})\), they can be managed using an array of size \(2^{20}\).

4. Counting Pairs of Distinct XOR Values Satisfying the Condition

For each value \(x\) that can be formed by the first group, we calculate

\[ y = S - x \]

If

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

and \(y\) can be formed by the second group, we find one pair of distinct XOR values \((x,y)\).

Let this count be pair_count.

5. Converting to the Number of Subset Choices

For each pair of distinct XOR values, there are

• \(2^{N-r_A}\) ways to choose a subset that forms \(x\) in the first group
• \(2^{N-r_B}\) ways to choose a subset that forms \(y\) in the second group

Therefore, the answer is

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

In summary:

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

Complexity

• Time Complexity: \(O(N \log M + 2^{r_A} + 2^{r_B} + M)\)
• Space Complexity: \(O(2^{r_A} + 2^{r_B} + M)\)

where

\[ M = 2^{20} \]

Also, since \(r_A, r_B \leq 20\), the complexities are practically:

• Time Complexity: \(O(N \cdot 20 + 2^{20})\)
• Space Complexity: \(O(2^{20})\)

which is fast enough.

Implementation Details

In the XOR linear basis, we store the “basis element whose most significant bit is \(b\)” in basis[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];
}

With this process, values that can already be represented by the existing basis are not added, and only linearly independent values are inserted.

Although the answer is guaranteed to be less than \(2^{63}\), the code uses __int128 to safely handle operations like bit shifts during calculations.

__int128 ans = (__int128)pair_count << exponent;

Finally, since __int128 cannot be printed directly with cout, we convert it to a decimal string using a custom output function before printing.

Source Code

#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;
}

---

This editorial was generated by gpt-5.5-high.