Summary

Let \(X\) and \(Y\) be the XOR sums of the chosen subsets from each group. This problem asks us to find the number of pairs of subsets such that \(X+Y=S\).

The key point is to represent the set of subset XOR sums using an XOR linear basis, allowing us to handle the number of subsets that produce the same XOR value collectively.

Analysis

Since each skill value is less than \(2^{20}\), we can view them as 20-bit vectors.
The XOR sum of a subset corresponds to a linear combination over \(\mathbb{F}_2\) based on whether we “choose” or “do not choose” each element.

For example, if the skill values of a group are

[ 1, 2, 3 ]

since \(3 = 1 \oplus 2\), only the two values \(1\) and \(2\) are independent.
A set of such independent values is called an XOR linear basis.

If the rank of the XOR linear basis of a group is \(r\), then:

• The number of distinct XOR values that can be formed is \(2^r\).
• The number of subsets that form each of these XOR values is equal and is \(2^{N-r}\).

Therefore, letting \(r_A\) be the rank of the first group and \(r_B\) be the rank of the second group, we first need to count the number of pairs of XOR values

[ (x,y) \quad (x \in V_A,\ y \in V_B,\ x+y=S) ]

where \(V_A\) and \(V_B\) are the sets of XOR values that can be formed in each group.

If this count of pairs of XOR values is \(P\), the actual number of pairs of subset choices is

[

P \times 2^{N-r_A} \times 2^{N-r_B}

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

Why the Naive Approach Fails

There are \(2^N\) possible subsets for each group.
Since \(N \leq 50\), enumerating all of them would take \(2^{50}\) operations, which is far too slow.

On the other hand, XOR values are 20-bit, so there are at most \(2^{20}\) distinct values.
By using a linear basis, we can efficiently handle only the “reachable XOR values” instead of the subsets themselves.

Also, because multiple subsets can produce the same XOR value, simply counting the number of distinct XOR values will result in a WA (Wrong Answer).
We must multiply by \(2^{N-r}\) at the end.

Algorithm

Let \(D=20\) and \(M=2^D\).
Each XOR value is always between \(0\) and \(M-1\) inclusive.

1. Build an XOR linear basis for both the first and second groups.

   • Let their ranks be \(r_A\) and \(r_B\), respectively.

2. Count the number of pairs of XOR values \(P\).

   • Enumerate the space of the group with the smaller rank.
   • For the other group, enable fast membership queries to check if a value can be formed.

3. Enumerate a value \(z\) from the XOR values that can be formed by one group.

   • The required value for the other group is \(S-z\).
   • If \(S-z\) is between \(0\) and \(M-1\) inclusive, and is contained in the other group’s space, increment the count by 1.

4. Finally, multiply by

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

On the Range of Values

For \(z\), the other value \(S-z\) must satisfy the following to be a valid XOR value:

[ 0 \leq S-z < M ]

This is equivalent to:

[ S-M+1 \leq z \leq S ]

Furthermore, since \(z\) itself must satisfy \(0 \leq z < M\), we only need to check \(z\) in the range:

[ \max(0, S-M+1) \leq z \leq \min(M-1, S) ]

Case of Rank 20

If the rank of a group is 20, we can form all 20-bit values:

[ 0,1,\ldots,2^{20}-1 ]

In this case, we do not need to construct a membership array; we can determine it solely by the range conditions.

Complexity

Let \(D=20\).

• Time Complexity: \(O(ND + 2^D)\)
• Space Complexity: \(O(2^D)\)

Since \(2^{20}=1,048,576\), this is fast enough.

Implementation Points

• The XOR linear basis is constructed using a Gaussian elimination-like method by looking at the most significant bit (MSB) of each value.

• If the rank of the basis is \(r\), \(2^r\) distinct XOR values can be formed.

• Enumeration can be done using a Gray code order to avoid recomputing the XOR sum from scratch every time.

  • In the code,

  (i & -i).bit_length() - 1
  

  finds the index of the next basis element to flip.

• We use a bytearray of length \(2^{20}\) for membership queries.

  • This is faster and uses less memory than a set.

• The final multiplication by

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

is implemented using a bitwise left shift << in the code.

Source Code

import sys

DIM = 20
M = 1 << DIM

def build_basis(arr):
    basis = [0] * DIM
    rank = 0
    for x in arr:
        v = x
        while v:
            i = v.bit_length() - 1
            if basis[i]:
                v ^= basis[i]
            else:
                basis[i] = v
                rank += 1
                break
    return [x for x in basis if x], rank

def make_membership(bs):
    mem = bytearray(M)
    mem[0] = 1
    cur = 0
    total = 1 << len(bs)
    for i in range(1, total):
        cur ^= bs[(i & -i).bit_length() - 1]
        mem[cur] = 1
    return mem

def count_with_membership(bs, mem, S):
    lo = S - M + 1
    if lo < 0:
        lo = 0
    hi = S
    if hi >= M:
        hi = M - 1
    if lo > hi:
        return 0

    cnt = mem[S] if lo == 0 else 0
    cur = 0
    total = 1 << len(bs)

    for i in range(1, total):
        cur ^= bs[(i & -i).bit_length() - 1]
        if cur >= lo and cur <= hi:
            cnt += mem[S - cur]
    return cnt

def count_with_full_space(bs, S):
    lo = S - M + 1
    if lo < 0:
        lo = 0
    hi = S
    if hi >= M:
        hi = M - 1
    if lo > hi:
        return 0

    if len(bs) == DIM:
        return hi - lo + 1

    cnt = 1 if lo == 0 else 0
    cur = 0
    total = 1 << len(bs)

    for i in range(1, total):
        cur ^= bs[(i & -i).bit_length() - 1]
        if cur >= lo and cur <= hi:
            cnt += 1
    return cnt

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, S = data[0], data[1]
    A = data[2:2 + N]
    B = data[2 + N:2 + 2 * N]

    basis_a, rank_a = build_basis(A)
    basis_b, rank_b = build_basis(B)

    if rank_a <= rank_b:
        enum_basis = basis_a
        mark_basis = basis_b
        mark_rank = rank_b
    else:
        enum_basis = basis_b
        mark_basis = basis_a
        mark_rank = rank_a

    if mark_rank == DIM:
        pairs = count_with_full_space(enum_basis, S)
    else:
        mem = make_membership(mark_basis)
        pairs = count_with_membership(enum_basis, mem, S)

    ans = pairs << (2 * N - rank_a - rank_b)
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.