Summary

This problem asks us to count the number of configurations of transmitter modes (A or B for each transmitter) such that the set of all possible XOR sums (composite signals) obtained by choosing any subset of active transmitters contains all the target signal values \(T_j\).

Analysis

XOR and Vector Spaces

The operation of “choosing some values and taking their XOR” is easier to understand if we think of it in a vector space over \(\mathrm{GF}(2)\) (the Galois field of two elements, \(0\) and \(1\)). If we view each signal value as a \(60\)-dimensional vector of \(0\)s and \(1\)s representing its bits, the XOR operation corresponds to vector addition.

Then, if we let the signal values of transmitters \(1, \dots, N\) be \(x_1, \dots, x_N\), the set of all composite signals that can be formed by choosing a subset of transmitters is exactly the linear span of \(x_1, \dots, x_N\). The empty set corresponds to \(0\).

Therefore, being able to achieve the target \(T_j\) is equivalent to “\(T_j\) being contained in this linear space.”

Conditions to Achieve All Targets

For all \(T_j\) to be contained in the span, it is sufficient and necessary that the space spanned by \(T_1, \dots, T_M\) is contained in the space spanned by \(x_1, \dots, x_N\).

The key point here is that we can reduce the target values \(T\) to a linear basis. We do not need to check all \(M\) targets individually; it is sufficient to check whether each vector in the basis constructed from \(T\) is contained in the transmitter-side span. If all vectors in the basis are contained, any \(T_j\) (which is a linear combination of these basis vectors) will automatically be contained as well.

Naive Approach and Pruning

Since \(N \le 15\), there are at most \(2^{15} = 32768\) possible mode assignments. We can easily enumerate all of them. For each assignment, we can construct the basis of the transmitter side and check if all vectors in the target basis are contained in its span.

However, the dimension of the space spanned by \(N\) vectors is at most \(N\). Therefore, if the dimension (rank) of the target basis exceeds \(N\), it is impossible to satisfy the condition under any assignment, so we can immediately return \(0\) (this is a small pruning step, but it is also useful for correctness).

Algorithm

1. Construct the target basis: Build a linear basis tbasis over \(\mathrm{GF}(2)\) from \(T_1, \dots, T_M\). This can be implemented using Gaussian elimination (maintaining a representative vector for each most significant bit (MSB) position).
   • If the rank of the target basis exceeds \(N\), the answer is \(0\).
2. Enumerate all assignments: Try all \(2^N\) possible values of mask. If the \(i\)-th bit of mask is set, transmitter \(i\) is set to mode B (value \(W_i\)); otherwise, it is set to mode A (value \(V_i\)).
3. Construct the transmitter basis: Construct a linear basis basis from the \(N\) chosen values.
4. Containment check: For each vector tv in the target basis, check if it can be reduced to \(0\) using basis. If we encounter an MSB for which no basis vector exists in basis and thus cannot reduce it further, then tv is not contained in the span, and this assignment is invalid.
5. Count the number of assignments where all target basis vectors can be reduced to \(0\), and output the count modulo \(10^9+7\).

Process of Gaussian Elimination (Insertion and Query)

For a vector \(v\), we look at its most significant bit position \(h\). If basis[h] exists, we XOR \(v\) with it to reduce \(v\). If it does not exist, we either insert \(v\) at basis[h] (for insertion) or conclude that it cannot be reduced to \(0\) and fail (for query/containment check). We repeat this process until \(v\) becomes \(0\).

Complexity

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

• Target basis construction: \(O(M \cdot B)\)
• Processing each assignment: \(O(N \cdot B)\) for basis construction, and \(O(\mathrm{rank} \cdot B) \le O(N \cdot B)\) for the containment check.
• Since we do this for \(2^N\) assignments, the total time for this part is \(O(2^N \cdot N \cdot B)\).

Therefore,

• Time Complexity: \(O(2^N \cdot N \cdot B + M \cdot B)\) (with \(B=60\))
• Space Complexity: \(O(B + N + M)\)

Since \(N \le 15\), \(2^N \cdot N \cdot B\) is approximately \(32768 \times 15 \times 60 \approx 3 \times 10^7\), which is well within the time limit.

Key Implementation Points

• Since the signal values are at most \(2^{60}-1\), allocate the basis array with a size of \(60\). In Python, arbitrary-precision integers can be used directly, allowing for straightforward bitwise operations.

• The most significant bit position can be obtained using v.bit_length() - 1.

• By reducing the target side to a basis first, we can limit the number of checks to “the dimension of the basis (at most \(N\))” even if \(M\) is very large. This is the key to optimization.

• Adding a pruning step to immediately return \(0\) if the rank of the target basis exceeds \(N\) allows us to handle obviously impossible cases quickly.

• Since we are counting the number of valid assignments, we just need to output the count modulo \(10^9+7\) at the end (although \(2^N \le 32768\) means overflow is not an issue, we still take the modulo as specified in the problem).

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    V = [0]*N
    W = [0]*N
    for i in range(N):
        V[i] = int(data[idx]); idx += 1
        W[i] = int(data[idx]); idx += 1
    T = [int(data[idx+j]) for j in range(M)]
    idx += M

    MOD = 10**9 + 7

    # target basis
    tbasis = [0]*60
    trank = 0
    for t in T:
        v = t
        while v:
            h = v.bit_length() - 1
            bh = tbasis[h]
            if bh == 0:
                tbasis[h] = v
                trank += 1
                break
            v ^= bh
    if trank > N:
        print(0)
        return

    tvecs = [x for x in tbasis if x]

    count = 0
    for mask in range(1 << N):
        basis = [0]*60
        m = mask
        for i in range(N):
            v = W[i] if (m >> i) & 1 else V[i]
            while v:
                h = v.bit_length() - 1
                bh = basis[h]
                if bh == 0:
                    basis[h] = v
                    break
                v ^= bh
        ok = True
        for tv in tvecs:
            v = tv
            while v:
                h = v.bit_length() - 1
                bh = basis[h]
                if bh == 0:
                    ok = False
                    break
                v ^= bh
            if not ok:
                break
        if ok:
            count += 1

    print(count % MOD)

main()

---

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