Overview

This problem asks us to determine, when deciding the operation mode (A or B) for each transmitter, whether all target signal values can be generated by “combinations of XOR (bitwise exclusive OR) of the chosen transmitter signal values.”

By focusing on the fact that the number of transmitters \(N\) is extremely small (at most \(15\)), we can solve this problem efficiently by combining brute-force search (exhaustive search) and XOR linear basis (Gaussian elimination).

---

Analysis

1. How to determine “can it be formed by XOR?”

The problem of “whether a specific target value can be formed by the XOR sum of some subset of values” can be determined quickly using an XOR linear basis (XOR Basis).

This is exactly the same concept as “can it be represented as a linear combination of vectors (Gaussian elimination)” in linear algebra. When each signal value is represented in binary, it can be viewed as a vector with each bit as a component. The XOR operation corresponds to addition without carry (addition over \(\mathrm{GF}(2)\)).

Therefore, the determination can be made using the following procedure: 1. Find the “basis” set \(B_T\) that spans the target signal values \(T = \{T_1, T_2, \ldots, T_M\}\). 2. Similarly, find the basis set \(B_X\) from the set of signal values chosen for each transmitter, \(X = \{x_1, x_2, \ldots, x_N\}\). 3. The necessary and sufficient condition for all elements of \(T\) to be formed by the XOR sum of elements of \(X\) is “all elements of \(B_T\) can be represented by the XOR sum of elements of \(B_X\).”

2. Utilizing the constraint \(N \le 15\)

For each transmitter, there are \(2\) choices: Mode A or Mode B. Since the total number of transmitters is \(N \le 15\), there are at most \(2^{15} = 32,768\) possible mode assignments.

Since this number is extremely small, we can exhaustively search all assignments (\(2^N\) ways) using bit brute-force, and check if the condition is satisfied for each. This will easily run within the time limit.

---

Algorithm

Step 1: Find the basis \(B_T\) of the target signal values \(T\)

First, construct the basis \(B_T\) from the list of target signal values \(T\). If the size of \(B_T\) (the number of elements in the basis) becomes larger than \(N\), then the number of independent target values is greater than the number of transmitters \(N\). Thus, it is absolutely impossible to achieve all target values regardless of how the modes are chosen. In this case, immediately output 0 and terminate.

Step 2: Brute-force search the mode assignments

Loop through integers mask from \(0\) to \(2^N - 1\). If the \(i\)-th bit of mask is 0, transmitter \(i\) chooses Mode A (\(V_i\)); if it is 1, it chooses Mode B (\(W_i\)).

Step 3: Find the basis \(B_X\) of the selected signal values \(X\)

For each mask, construct the basis \(B_X\) from the \(N\) selected signal values.

Step 4: Determination

For each element \(t\) in \(B_T\), perform elimination using the basis \(B_X\). Specifically, using the elements \(b\) of \(B_X\), we update \(t \leftarrow t \oplus b\) whenever \(t \oplus b < t\). If \(t\) eventually becomes \(0\), it means that \(t\) can be represented by (i.e., can be formed from) the XOR sum of the elements of \(B_X\). Only when all elements of \(B_T\) become \(0\), the mask satisfies the condition, so we increment the answer counter by \(+1\).

---

Complexity

Let \(D = 60\) be the maximum number of bits of the values.

• Time Complexity: \(O(M \cdot D + 2^N \cdot N \cdot D)\)

  • Finding the basis of \(T\) takes \(O(M \cdot D)\).
  • For each mask (\(2^N\) ways), constructing the basis \(B_X\) takes \(O(N \cdot D)\), and the determination takes \(O(|B_T| \cdot D) = O(N \cdot D)\).
  • Substituting \(N = 15, M = 100, D = 60\), the total worst-case number of operations is approximately \(32,768 \times 15 \times 60 \approx 3 \times 10^7\), which runs fast in under \(1\) second even in Python.

• Space Complexity: \(O(N + M)\)

  • Since the size of the basis is at most \(D\) (or \(N\)), it operates with very little memory.

---

Implementation Points

• How to construct the basis: When adding to the basis, keeping the values sorted in descending order (by the position of their most significant set bit) makes the elimination straightforward. When inserting a new element \(x\), compare it with the existing basis elements \(b\), and if \(x \oplus b < x\) (meaning we can eliminate the most significant bit of \(x\)), update \(x \leftarrow x \oplus b\). If \(x > 0\) in the end, insert it into the appropriate position (maintaining the descending order).

  Source Code

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    M = int(data[1])
    
    pairs = []
    idx = 2
    for _ in range(N):
        v = int(data[idx])
        w = int(data[idx+1])
        pairs.append((v, w))
        idx += 2
        
    T = [int(x) for x in data[idx:idx+M]]
    
    # T の基底を求める
    basis_T = []
    for t in T:
        for b in basis_T:
            if (t ^ b) < t:
                t ^= b
        if t > 0:
            inserted = False
            for i in range(len(basis_T)):
                if t > basis_T[i]:
                    basis_T.insert(i, t)
                    inserted = True
                    break
            if not inserted:
                basis_T.append(t)
                
    if len(basis_T) > N:
        print(0)
        return
        
    ans = 0
    pow2 = [1 << i for i in range(N)]
    
    for mask in range(1 << N):
        basis_X = []
        for i, (v, w) in enumerate(pairs):
            x = w if (mask & pow2[i]) else v
            for b in basis_X:
                if (x ^ b) < x:
                    x ^= b
            if x > 0:
                inserted = False
                for j in range(len(basis_X)):
                    if x > basis_X[j]:
                        basis_X.insert(j, x)
                        inserted = True
                        break
                if not inserted:
                    basis_X.append(x)
                    
        possible = True
        for t in basis_T:
            for b in basis_X:
                if (t ^ b) < t:
                    t ^= b
            if t > 0:
                possible = False
                break
        if possible:
            ans += 1
            
    print(ans % 1000000007)

if __name__ == '__main__':
    solve()

---

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