Overview

This problem asks us to find the number of assignments of transmitter modes (A or B) out of \(2^N\) possible assignments such that all \(M\) given target signal values can be represented as the XOR (exclusive OR) sum of the output values of a subset of the selected transmitters.

Analysis

1. Focusing on Constraints

Notice that the number of transmitters \(N\) is extremely small, being at most \(15\). Since each transmitter has \(2\) modes, A and B, there are only \(2^N \le 2^{15} = 32,768\) possible assignment patterns in total. Therefore, an approach that performs an exhaustive search (brute-force) over all assignments and checks whether each satisfies the condition is effective.

2. Checking Representability by XOR Sum (Linear Basis)

Once a mode assignment is fixed, resulting in a set of transmitter output values \(X = \{X_1, X_2, \dots, X_N\}\), we need to quickly check whether each target signal value \(T_j\) can be represented as the XOR sum of a subset of \(X\).

This can be viewed as a problem in vector spaces (linear algebra) over \(\mathbb{F}_2\), where XOR is treated as addition. By constructing a linear basis from the set \(X\), we can check whether any number \(T_j\) can be represented as the XOR sum of elements in \(X\) in \(O(\log(\max T_j))\) time.

3. Optimization by Simplifying Target Signal Values

If we naively check whether all target signal values \(T_1, T_2, \dots, T_M\) can be represented, we would need to perform \(M\) checks for each assignment. To speed up this check, we can precompute the linear basis \(T_{\text{basis}}\) of the set of target signal values \(T\) itself. The statement “all elements in \(T\) can be represented” is equivalent to “all elements in the linear basis of \(T\) can be represented”. Since the size of the basis of \(T\) is at most the number of bits (at most \(60\) in this case), we can significantly reduce the number of checks.

---

Algorithm

1. Constructing the Basis of Target Signal Values From the input \(M\) target signal values \(T_1, \dots, T_M\), construct a linear basis target_basis using Gaussian elimination. If the size of target_basis is larger than the number of transmitters \(N\), it is impossible to represent them no matter how we choose the modes. Thus, we can immediately output 0 and terminate (early return).

2. Exhaustive Search of Assignments Iterate through the integers mask from \(0\) to \(2^N - 1\). If the \(i\)-th bit of mask is 0, set the mode of transmitter \(i\) to A (value \(V_i\)); if it is 1, set it to B (value \(W_i\)). This determines the set of output values \(X\) for each transmitter.

3. Constructing the Basis of Transmitter Outputs From the determined elements of \(X\), construct a linear basis basis in the same way using Gaussian elimination.

4. Checking Representability For each element \(t\) in target_basis, check if it can be represented using basis. Specifically, iterating from the most significant bit (MSB) of \(t\) downwards, if there is an element in basis with the same MSB, we XOR \(t\) with that element. If \(t\) eventually becomes \(0\), it is representable. If all elements in target_basis are representable, the mask satisfies the condition, so we increment the answer count by \(1\).

5. Output Output the final count modulo \(10^9 + 7\).

---

Complexity

• Time Complexity: \(O(M \log(\max T) + 2^N \cdot N \log(\max V))\)

  • Constructing the basis of target signal values takes \(O(M \log(\max T))\) time.
  • In the search over all assignments (\(2^N\) iterations), constructing the transmitter basis takes \(O(N \log(\max V))\) time, and checking representability takes \(O(B \log(\max V))\) time (where \(B\) is the size of target_basis, with \(B \le N\)).
  • Since \(N \le 15\) and \(\log(\max V) \le 60\), even in the worst case, the number of operations inside the loop is around \(3.2 \times 10^4 \times 15 \times 60 \approx 2.9 \times 10^7\) basic operations, which easily fits within the time limit (usually 2 seconds).

• Space Complexity: \(O(N + M + \log(\max T))\)

  • It is extremely memory-efficient as it only uses arrays to store the bases and input data.

---

Implementation Points

• Leveraging std::bit_width By using std::bit_width introduced in C++20, we can quickly obtain the position of the most significant bit (MSB) of a number (i.e., its bit length in binary). This allows us to write the Gaussian elimination process in a simple and fast manner.

• Early Return If the size of the basis of target signal values exceeds \(N\), it is absolutely impossible to represent them due to an insufficient number of transmitters. Thus, we can avoid unnecessary computations by outputting \(0\) and terminating before starting the search.

  Source Code

#include <iostream>
#include <vector>
#include <bit>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> V(N), W(N);
    for (int i = 0; i < N; ++i) {
        cin >> V[i] >> W[i];
    }

    vector<long long> T(M);
    for (int j = 0; j < M; ++j) {
        cin >> T[j];
    }

    vector<long long> t_basis(61, 0);
    for (int j = 0; j < M; ++j) {
        long long x = T[j];
        while (x > 0) {
            int bit = std::bit_width(static_cast<unsigned long long>(x)) - 1;
            if (!t_basis[bit]) {
                t_basis[bit] = x;
                break;
            }
            x ^= t_basis[bit];
        }
    }

    vector<long long> target_basis;
    for (int bit = 60; bit >= 0; --bit) {
        if (t_basis[bit]) {
            target_basis.push_back(t_basis[bit]);
        }
    }

    if (target_basis.size() > N) {
        cout << 0 << "\n";
        return 0;
    }

    long long ans = 0;
    vector<long long> X(N);
    vector<long long> basis(61);
    vector<pair<int, long long>> basis_list;
    basis_list.reserve(N);

    for (int mask = 0; mask < (1 << N); ++mask) {
        for (int i = 0; i < N; ++i) {
            X[i] = (mask & (1 << i)) ? W[i] : V[i];
        }

        fill(basis.begin(), basis.end(), 0);
        for (int i = 0; i < N; ++i) {
            long long x = X[i];
            while (x > 0) {
                int bit = std::bit_width(static_cast<unsigned long long>(x)) - 1;
                if (!basis[bit]) {
                    basis[bit] = x;
                    break;
                }
                x ^= basis[bit];
            }
        }

        basis_list.clear();
        for (int bit = 60; bit >= 0; --bit) {
            if (basis[bit]) {
                basis_list.push_back({bit, basis[bit]});
            }
        }

        bool ok = true;
        for (long long t : target_basis) {
            for (auto [bit, val] : basis_list) {
                if ((t >> bit) & 1) {
                    t ^= val;
                }
            }
            if (t != 0) {
                ok = false;
                break;
            }
        }

        if (ok) {
            ans++;
        }
    }

    cout << ans % 1000000007 << "\n";

    return 0;
}

---

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