Overview

This problem asks us to find the total number of mode assignments (choosing either mode A or B for each transmitter) such that all target signal values are contained within the XOR span of the selected signal values.

Analysis

The condition that the XOR sum of some subset of selected transmitters matches the target signal value \(T_j\) is equivalent to saying that \(T_j\) is contained in the “XOR span” generated by the set of selected signal values.

Since \(N \leq 15\) is small, we can consider an approach that explores all \(2^N\) possible combinations of choosing mode A or B for each transmitter. Naively enumerating all combinations and checking if the \(M\) target signal values can be formed for each combination would have too high of a computational complexity if we consider subsets for each combination.

Here, we can use the concept of a linear basis (or XOR basis) to efficiently manage “the range of XOR values that can be formed by a set of numbers”. Using a linear basis, we can determine whether a value \(x\) can be formed by the XOR sum of elements in the set in \(O(60)\) time.

Therefore, we can manage the state by using Depth First Search (DFS) to choose the mode of each transmitter one by one and add the chosen value to the linear basis. Once we have chosen the modes for all transmitters, we can check if all \(M\) target signal values are contained in the space spanned by the current linear basis.

Algorithm

1. Brute-force Search via DFS: For each transmitter \(i\), we branch into two cases: choosing mode A (value \(V_i\)) and choosing mode B (value \(W_i\)).
2. Constructing the Linear Basis: Add the chosen value to the current linear basis (array basis). To add a value to the linear basis, we look at the most significant bit (MSB) of the value. If a basis element already exists at that bit position, we XOR the value with it to clear the bit. If the position is empty, we register the value as a new basis element at that position.
3. Backtracking (State Restoration): When returning from the DFS, if we added an element to the basis, we remove it to restore the state. This allows us to manage the state with a single array without allocating extra memory.
4. Checking: Once the modes for all transmitters have been chosen (\(i = N\)), we check whether each of the target signal values \(T_1, \ldots, T_M\) can be represented by the current linear basis (i.e., whether they can be reduced to \(0\) by XORing with the basis vectors). If all can be represented, we return \(1\); otherwise, if even one cannot, we return \(0\).

Complexity

• Time Complexity: \(O(2^N \cdot (N+M) \cdot 60)\) The number of leaf nodes is \(2^N\). At each leaf, we perform \(M\) checks, each taking \(O(60)\) time. Adding an element to the basis also takes \(O(60)\) time. For \(N=15, M=100\), this results in about \(2 \times 10^8\) operations, which is well within the time limit for C++.
• Space Complexity: \(O(60)\) This is the memory required for the linear basis array basis[60] and storing the input. The recursion depth of the DFS is \(N\).

Implementation Details

• When adding a value to the linear basis, we need to repeatedly XOR it with existing basis elements to eliminate its most significant bits.

• If the value is successfully added (i.e., pos != -1), we roll back the state by setting basis[pos] = 0 after returning from the DFS. If the value cannot be added (i.e., it is already in the span), the basis does not change, so no rollback is necessary.

• Bitwise operations should be performed using 64-bit integers (unsigned long long).

  Source Code

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;

int N, M;
vector<unsigned long long> V, W, T;
unsigned long long basis[60];

int dfs(int i) {
    if (i == N) {
        for (int j = 0; j < M; ++j) {
            unsigned long long val = T[j];
            for (int k = 59; k >= 0; --k) {
                if (val & (1ULL << k)) {
                    if (basis[k]) val ^= basis[k];
                    else break;
                }
            }
            if (val != 0) return 0;
        }
        return 1;
    }
    
    int res = 0;
    
    // Choice A
    {
        unsigned long long v = V[i];
        int pos = -1;
        for (int k = 59; k >= 0; --k) {
            if (v & (1ULL << k)) {
                if (basis[k]) v ^= basis[k];
                else {
                    basis[k] = v;
                    pos = k;
                    break;
                }
            }
        }
        res = (res + dfs(i + 1)) % MOD;
        if (pos != -1) basis[pos] = 0;
    }
    
    // Choice B
    {
        unsigned long long w = W[i];
        int pos = -1;
        for (int k = 59; k >= 0; --k) {
            if (w & (1ULL << k)) {
                if (basis[k]) w ^= basis[k];
                else {
                    basis[k] = w;
                    pos = k;
                    break;
                }
            }
        }
        res = (res + dfs(i + 1)) % MOD;
        if (pos != -1) basis[pos] = 0;
    }
    
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (!(cin >> N >> M)) return 0;
    
    V.resize(N);
    W.resize(N);
    T.resize(M);
    
    for (int i = 0; i < N; ++i) {
        cin >> V[i] >> W[i];
    }
    for (int i = 0; i < M; ++i) {
        cin >> T[i];
    }
    
    cout << dfs(0) << "\n";
    
    return 0;
}

This editorial was generated by or-glm5.2-high.