Overview

This problem asks us to count the number of pairs of subsets chosen from each group such that the XOR sums of the subsets, \(X\) and \(Y\), satisfy \(X + Y = S\). We can solve this by utilizing the fact that XOR forms a linear algebraic structure (a vector space over \(\mathrm{GF}(2)\)).

Observations

Limitations of a Naive Approach

Since each group has \(N \le 50\) people, there are \(2^{50}\) ways to choose a subset from each group, resulting in up to \(2^{100}\) combinations in total. An exhaustive search is far too slow.

Key Observation 1: XOR Forms a Vector Space

The XOR sum of a subset can be viewed as a linear combination of the skill value vectors over \(\mathrm{GF}(2)\). The set of XOR sums that can be formed from the skill values of the first group (the span) consists of exactly \(2^{r_1}\) distinct values, where \(r_1\) is the rank of the basis.

Even more importantly, the number of subsets that produce any reachable value \(X\) is always the same, namely \(2^{N - r_1}\). This is because the number of subsets whose XOR sum is \(0\) (the kernel) is \(2^{N - r_1}\), and by shifting them, each reachable value appears the same number of times.

For example, if the skill values are \(\{3, 3\}\), the basis is \(\{3\}\) with rank \(1\), and the reachable XOR values are \(\{0, 3\}\). The value \(0\) can be formed in \(2\) ways: “choose neither” or “choose both” (\(=2^{2-1}\)), and \(3\) can also be formed in \(2\) ways: “choose only the 1st person” or “choose only the 2nd person”.

Key Observation 2: Counting by Grouping Values

Therefore,

• Let \(C\) be the number of value pairs \((X, Y)\) where \(X\) is a reachable value of the first group, \(Y\) is a reachable value of the second group, and \(X + Y = S\).
• The number of subsets forming each value is \(2^{N-r_1}\) and \(2^{N-r_2}\), respectively.

Thus, the answer we seek is:

\[ C \times 2^{N - r_1} \times 2^{N - r_2} = C \times 2^{2N - r_1 - r_2} \]

Now, we just need to find the number of value pairs \(C\).

How to Count the Number of Value Pairs

The number of reachable values is at most \(2^{r_1}\) and \(2^{r_2}\). Since the skill values are less than \(2^{20}\), the rank is at most \(20\), meaning there are at most \(2^{20}\) distinct values.

We can proceed as follows:

1. Enumerate all reachable values \(Y\) of the second group and record inB[Y] = true in an array of size \(2^{20}\).
2. Enumerate all reachable values \(X\) of the first group. If \(Y = S - X\) satisfies \(0 \le Y < 2^{20}\) and inB[Y] is true, count it as a valid pair.

This allows us to find \(C\) in \(O(2^{20})\) time.

Algorithm

1. Basis Construction: Use Gaussian elimination to construct the basis from the skill values of each group, and find the ranks \(r_1, r_2\).
2. Enumerating Span B: Enumerate all XOR sums of the subsets of the basis, and record the reachable values in the array inB.
3. Enumerating Span A and Matching: Similarly, for each value \(X\) in span A, check if \(S - X\) is in span B, and count the number of pairs \(C\).
4. Calculating the Answer: Output \(C \times 2^{2N - r_1 - r_2}\).

When enumerating the span, using a Gray code is highly efficient. By iterating \(i\) from \(1\) to \(2^r - 1\) and XORing the basis vector corresponding to the changed bit position (__builtin_ctzll(i)), we can update to the next value in \(O(1)\) time at each step.

Complexity

Since the basis values are less than \(2^{20}\), the rank is at most \(20\), and the size of the span is at most \(2^{20}\).

• Time Complexity: \(O(2^{r_1} + 2^{r_2}) = O(2^{20})\) (Basis construction takes \(O(N \cdot 20)\))
• Space Complexity: \(O(2^{20})\) (for the inB array)

Implementation Points

• Formula for the Number of Subsets Producing a Reachable Value: The core of the solution is “Answer \(= C \times 2^{2N - r_1 - r_2}\)”. Make sure to leverage the fact that each reachable value is formed exactly the same number of times (\(2^{N-r}\) times).

• Range Checking: Since \(S < 2^{21}\) and \(X < 2^{20}\), \(Y = S - X\) can be negative or greater than or equal to \(2^{20}\). To prevent out-of-bounds access on the inB array, always check if \(0 \le Y < 2^{20}\).

• Overflow Prevention: Since the answer is guaranteed to be less than \(2^{63}\), the shift amount \(2N - r_1 - r_2\) will be less than \(64\) when \(C > 0\). It is safe to calculate C << power using unsigned long long (output \(0\) if \(C = 0\)).

• Gray Code Enumeration: By using the update val ^= basis[__builtin_ctzll(i)], you can generate all elements of the span without duplicates in \(O(1)\) per element.

  Source Code

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

vector<int> getBasis(const vector<int>& v){
    int b[21] = {0};
    for(int x : v){
        for(int i = 20; i >= 0; i--){
            if(!((x >> i) & 1)) continue;
            if(!b[i]){ b[i] = x; break; }
            x ^= b[i];
        }
    }
    vector<int> res;
    for(int i = 0; i <= 20; i++) if(b[i]) res.push_back(b[i]);
    return res;
}

int main(){
    int N; 
    long long S;
    scanf("%d %lld", &N, &S);
    vector<int> A(N), B(N);
    for(int i = 0; i < N; i++) scanf("%d", &A[i]);
    for(int i = 0; i < N; i++) scanf("%d", &B[i]);
    
    vector<int> bsA = getBasis(A);
    vector<int> bsB = getBasis(B);
    int r1 = (int)bsA.size();
    int r2 = (int)bsB.size();
    
    const int LIM = 1 << 20;
    static vector<char> inB;
    inB.assign(LIM, 0);
    
    // enumerate span B
    {
        int val = 0;
        inB[val] = 1;
        long long total = 1LL << r2;
        for(long long i = 1; i < total; i++){
            int pos = __builtin_ctzll(i);
            val ^= bsB[pos];
            inB[val] = 1;
        }
    }
    
    // enumerate span A
    long long count = 0;
    {
        int val = 0;
        auto check = [&](int X){
            long long Y = S - X;
            if(Y >= 0 && Y < LIM && inB[(int)Y]) count++;
        };
        check(0);
        long long total = 1LL << r1;
        for(long long i = 1; i < total; i++){
            int pos = __builtin_ctzll(i);
            val ^= bsA[pos];
            check(val);
        }
    }
    
    int power = 2 * N - r1 - r2;
    unsigned long long ans;
    if(count == 0){
        ans = 0;
    } else {
        // guaranteed answer < 2^63, so power < 64 here
        ans = (unsigned long long)count << power;
    }
    
    printf("%llu\n", ans);
    return 0;
}

---

This editorial was generated by claude4.8opus-high.