Overview

The problem asks us to find the total number of ways to choose a subset of members from each of two groups such that, if the XOR (bitwise exclusive OR) of the skill values of the chosen members in each group are \(X\) and \(Y\) respectively, they satisfy \(X + Y = S\).

---

Analysis

Naive Approach and Its Limitations

The number of members in each group is at most \(N = 50\). If we try to naively search all possible subsets, there are \(2^{50} \approx 1.1 \times 10^{15}\) ways for just a single group, making it impossible to compute within the time limit.

Key Observations

1. Small Value Range The skill values \(A_i, B_i\) are less than \(2^{20}\) (from \(0\) to \(1,048,575\)). Therefore, any value that can be formed as a XOR sum of a subset must also be strictly less than \(2^{20}\). We observe that the number of possible values is at most \(2^{20} \approx 10^6\).

2. Introduction of Linear Basis To efficiently handle the set of possible XOR sums, we can use a linear basis, which applies the concept of a “basis” from linear algebra.

In a vector space of size \(N\) over \(\mathbb{F}_2\) (bitwise XOR), the set of values that can be formed by the XOR sum of any elements is identical to the set of values formed by the XOR sum of a few “linearly independent” elements (the basis). Since the values are less than \(2^{20}\), the size of the basis \(K\) is at most \(20\).

1. Regularity in the Number of Ways When we extract a basis of size \(K\) from the original \(N\) elements, there are \(2^{N-K}\) ways to choose the remaining \(N - K\) elements (non-basis elements).

No matter how we choose the non-basis elements, we can uniquely choose elements from the basis to compensate for their XOR sum and achieve any XOR sum \(v\) that can be represented by the basis. Therefore, for any XOR sum \(v\) that can be formed by the basis, the number of ways to choose a subset from the original array such that its XOR sum is \(v\) is uniformly \(2^{N-K}\).

Using this, we can dramatically reduce the search space from \(2^{50}\) to \(2^{20}\).

---

Algorithm

1. Extracting the Linear Basis

Using Gaussian elimination, we find the linear bases basisA and basisB from the arrays \(A\) and \(B\) of each group. We scan from the most significant bit (the 19th bit) downwards to determine the basis elements.

2. Enumerating All XOR Sums and Recording the Number of Combinations

We enumerate all possible XOR sums that can be formed from the obtained bases. If the size of the basis is \(K\), there are \(2^K\) possible XOR sums (at most \(2^{20} \approx 10^6\)).

For each XOR sum \(v\), we record the number of ways to choose a subset that forms it (\(2^{N-K}\) ways) in the arrays dpA[v] and dpB[v].

3. Summing Up the Valid Pairs

We search for pairs that satisfy \(X + Y = S\). We iterate \(X\) from \(0\) to \(2^{20}-1\). If the corresponding \(Y = S - X\) falls within the range \(0 \le Y < 2^{20}\), we add dpA[X] * dpB[Y] to the total answer.

---

Complexity

• Time Complexity: \(O(N \log (\max A_i) + 2^{\log(\max A_i)})\)

  • Basis Extraction: \(O(N \log(\max A_i))\). Since \(N \le 50\) and \(\log(\max A_i) \le 20\), this takes about \(1000\) operations.
  • Enumeration and Summation of XOR Sums: \(O(2^K)\). Since \(K \le 20\), this requires at most \(2^{20} \approx 1.05 \times 10^6\) loop iterations.
  • Overall, the execution time is very fast, taking only a few to tens of milliseconds.

• Space Complexity: \(O(2^{\log(\max A_i)})\)

  • The size of the arrays recording the number of occurrences of each XOR sum is \(2^{20}\) (about 1 million elements), which is well within the memory limit.

---

Implementation Points

• Constructing the Basis: In the get_basis function, for each element, we take the XOR with the already obtained basis elements to eliminate linearly dependent components. We add it to the basis only if a new, independent value remains.

• Index Control during Summation: We need \(Y = S - X\) to satisfy \(0 \le Y < 2^{20}\). To avoid unnecessary loops and prevent out-of-bounds array access, we limit the range of \(X\) to search from start = max(0, S - LIMIT + 1) to end = min(S, LIMIT - 1).

  Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    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]]
    
    def get_basis(arr):
        basis = []
        for x in arr:
            for b in basis:
                x = min(x, x ^ b)
            if x > 0:
                basis.append(x)
                basis.sort(reverse=True)
        return basis

    basisA = get_basis(A)
    basisB = get_basis(B)
    
    def get_all_xor_sums(basis):
        sums = [0]
        for g in basis:
            sums += [x ^ g for x in sums]
        return sums

    LIMIT = 1 << 20
    dpA = [0] * LIMIT
    dpB = [0] * LIMIT
    
    valA = 1 << (N - len(basisA))
    for v in get_all_xor_sums(basisA):
        dpA[v] = valA
        
    valB = 1 << (N - len(basisB))
    for v in get_all_xor_sums(basisB):
        dpB[v] = valB
        
    ans = 0
    start = max(0, S - LIMIT + 1)
    end = min(S, LIMIT - 1)
    
    for X in range(start, end + 1):
        ans += dpA[X] * dpB[S - X]
        
    print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3.5-flash-high.