Overview

This problem asks us to count the number of configurations (setting each transmitter to either Mode A or Mode B) such that all target signal values \(T_j\) can be formed by the XOR sum of the chosen signal values. Since \(N \leq 15\) is small, we can try all \(2^N\) possible configurations.

Analysis

First, let’s consider the set of values that can be formed by the XOR sum of a subset of active transmitters. Given \(N\) values \(a_1, a_2, \ldots, a_N\), the set of all values that can be formed by choosing any subset and taking their XOR sum is a linear space (XOR space) spanned by these values.

An important observation is as follows:

Whether a target value \(T_j\) can be formed by the XOR sum of a subset is equivalent to whether \(T_j\) belongs to the XOR space spanned by \(\{a_1, \ldots, a_N\}\).

Since XOR can be viewed as vector addition over GF(2) (the field of two elements), linear algebra concepts can be applied directly. By representing each value as a 60-bit vector and constructing a basis (XOR basis / linear basis) using Gaussian elimination, we can determine whether a value is in the space:

• A value \(T\) is in the space \(\iff\) \(T\) becomes \(0\) after being reduced by the basis.

This allows us to perform the check efficiently.

Naively searching through all \(2^N\) subsets for each \(T_j\) would require \(2^N\) configurations \(\times\) \(M\) targets \(\times\) \(2^N\) subsets, which is far too slow. By using an XOR basis, we can check each target value quickly (in \(O(\text{number of bits})\) time), allowing for efficient computation.

Algorithm

1. There are \(2^N\) possible mode assignments. We can iterate through all patterns using an integer mask (\(0 \le \text{mask} < 2^N\)). For each transmitter \(i\), we use \(W_i\) if the \(i\)-th bit of mask is set, and \(V_i\) otherwise.

2. For each mask, construct the XOR basis from the \(N\) chosen values.

   • Let basis[b] be the basis vector whose most significant bit (MSB) is \(b\).
   • For each chosen value \(x\), we inspect its bits from most significant to least significant. For each set bit \(b\), if basis[b] is empty, we register \(x\) there. Otherwise, we update \(x \mathbin{\oplus}= \mathrm{basis}[b]\) and continue the reduction.

3. For all target values \(T_j\), reduce \(T_j\) using the basis in the same manner.

   • If it becomes \(0\) after reduction, it can be formed. If it does not become \(0\), it cannot.
   • If there is even one target value that cannot be formed, the current mask is invalid.

4. Count the number of valid masks and output the result modulo \(10^9+7\).

As a concrete example, suppose \(V = (3, 5)\) and we choose Mode A for both. The space spanned by \(3 = (011)_2\) and \(5 = (101)_2\) contains \(3 \oplus 5 = 6\) and \(0\), meaning \(\{0, 3, 5, 6\}\) can be formed. If the target is \(T = 6\), reducing it with the basis will result in \(0\), so it is correctly determined that it can be formed.

Complexity

Let \(B = 60\) be the bit width.

• For each mask, constructing the basis takes \(O(N \cdot B)\) and checking the targets takes \(O(M \cdot B)\).
• Since we repeat this for all \(2^N\) configurations:
  • Time Complexity: \(O(2^N \cdot (N + M) \cdot B)\)
  • Space Complexity: \(O(N + M + B)\) (the basis array has a constant size proportional to the bit width)

With \(N \leq 15\), \(M \leq 100\), and \(B = 60\), this is well within the time limit.

Implementation Details

• Since the signal values can be up to \(2^{60}-1\), always use 64-bit integers (unsigned long long). Note that bit shifts must also be done using 64-bit operations, such as 1ULL << b.

• Make sure to initialize (zero-clear) the basis array for each mask before constructing it.

• When counting the answer, there are only \(2^{15} = 32768\) possible configurations, so there is almost no risk of overflow during the summation. However, taking the modulo at the end ensures safety.

• The XOR sum of an empty set is \(0\). Since this always reduces to \(0\) with any basis, a target \(T_j = 0\) is automatically determined to be formable (no special handling is required).

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, M;
    scanf("%d %d", &N, &M);
    vector<unsigned long long> V(N), W(N);
    for(int i=0;i<N;i++){
        scanf("%llu %llu", &V[i], &W[i]);
    }
    vector<unsigned long long> T(M);
    for(int j=0;j<M;j++) scanf("%llu", &T[j]);
    
    const long long MOD = 1000000007;
    long long ans = 0;
    
    for(int mask=0; mask<(1<<N); mask++){
        // build basis
        unsigned long long basis[64];
        for(int b=0;b<64;b++) basis[b]=0;
        for(int i=0;i<N;i++){
            unsigned long long x = (mask>>i&1) ? W[i] : V[i];
            for(int b=59;b>=0;b--){
                if(!((x>>b)&1ULL)) continue;
                if(basis[b]==0){ basis[b]=x; break; }
                x ^= basis[b];
            }
        }
        // check all targets
        bool ok=true;
        for(int j=0;j<M && ok;j++){
            unsigned long long x = T[j];
            for(int b=59;b>=0;b--){
                if(!((x>>b)&1ULL)) continue;
                if(basis[b]==0){ ok=false; break; }
                x ^= basis[b];
            }
            if(x!=0) ok=false;
        }
        if(ok){
            ans++;
            if(ans>=MOD) ans-=MOD;
        }
    }
    
    printf("%lld\n", ans%MOD);
    return 0;
}

---

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