Overview

This problem asks us to find the number of pairs of subsets chosen from two groups such that the sum of their XOR sums is equal to \(S\). We can count this efficiently by leveraging the property that the set of values formed by XOR subsets forms a “linear space” (vector space).

Analysis

Limitations of a Naive Approach

There are \(2^N\) subsets for each group. Since \(N \leq 50\), a brute-force search would require \(2^{50} \times 2^{50}\) combinations, which is far too slow to pass within the time limit.

Key Observation: XOR Subsets Form a Linear Space

The set of values that can be formed by the XOR sum of a subset chosen from a given sequence forms a linear space (span) over GF(2). If the dimension (rank) of this space is \(r\), it has the following crucial properties:

• There are exactly \(2^{r}\) distinct values that can be formed.
• Each of these values can be formed by exactly \(2^{N-r}\) different subsets.

For example, if \(A = [1, 1]\), the possible XOR sums are \(0\) (empty subset or choosing both) and \(1\) (choosing exactly one), which are \(2\) distinct values. Here, \(N=2\) and the rank is \(r=1\). Thus, each value is formed by \(2^{2-1}=2\) subsets. Indeed, \(0\) is formed by \(2\) subsets (the empty set and \(\{A_1, A_2\}\)), and \(1\) is formed by \(2\) subsets (\(\{A_1\}\) and \(\{A_2\}\)).

Solution Strategy

Using this property, we can decompose the problem as follows:

1. For each of Group 1 and Group 2, find the set of distinct XOR values (span) and the rank.
2. Count the number of pairs of values \((X, Y)\) such that \(X \in \text{span}_A\), \(Y \in \text{span}_B\), and \(X + Y = S\).
3. Multiply the number of valid value pairs by the number of subset combinations that achieve each pair, which is \(2^{N-r_A} \times 2^{N-r_B}\).

Since \(A_i, B_i < 2^{20}\), the rank is at most \(20\). Thus, the maximum size of the span is around \(2^{20} \approx 10^6\), which is small enough to be processed.

Algorithm

1. Constructing the Basis

We construct the linear basis using Gaussian elimination over GF(2). For each number, we examine its bits from the most significant bit (MSB). If a basis element with the same MSB already exists, we XOR the number with it. Otherwise, we insert the number as a new basis element. The number of elements in the basis is the rank \(r\).

2. Enumerating the Span

By taking the XOR of all possible combinations of “using or not using” each basis element, we can enumerate the span (the set of all possible values). If there are \(r\) basis elements, we obtain \(2^r\) values.

3. Counting the Pairs

• Store \(\text{span}_B\) in a hash set (e.g., set or unordered_set).
• For each value \(x\) in \(\text{span}_A\), check if \(S - x\) is in \(\text{span}_B\) (and ensure \(S - x \geq 0\)). If it is, increment the count of valid pairs by \(1\).

4. Multiplying by the Multiplier

Finally, the answer is the number of valid pairs multiplied by \(2^{N-r_A} \times 2^{N-r_B}\).

Note that since we are dealing with standard integer addition \(X + Y = S\) rather than a bitwise XOR sum, we cannot process the bits independently. We must explicitly enumerate and match the sets of values as described above. (Since \(S < 2^{21}\) and the values in the span are \(< 2^{20}\), the values fit well within a reasonable range.)

Complexity

Let \(r\) (\(\leq 20\)) be the rank. The size of the span is \(2^r\).

• Time Complexity: \(O(N \cdot 20 + 2^{r})\) (for basis construction, span enumeration, and matching). In the worst case, this is around \(2^{20}\) operations.
• Space Complexity: \(O(2^{r})\) (to store the span). In the worst case, this is around \(2^{20}\) elements.

Implementation Details

• Bit width: Since \(A_i, B_i < 2^{20}\), we should allocate a basis array for bits \(0\) to \(20\) (length \(21\)).

• Checking \(S - x \geq 0\): If \(S - x\) is negative, it will naturally not be found in the set, but we should be careful to avoid out-of-bounds errors or underflow during subtraction.

• Calculating the multiplier: We multiply the number of valid pairs by (1 << (N - rankA)) * (1 << (N - rankB)). Since \(N\) can be large, \(2^{N-r}\) can be very large. However, since the final answer is guaranteed to be less than \(2^{63}\), we can handle this safely (e.g., using 64-bit integers in C++ or arbitrary-precision integers in Python).

  Source Code

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()

---

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