Overview

This problem asks us to find the number of ways to choose either \(V_i\) or \(W_i\) for each transmitter such that all target values \(T_j\) can be represented as the XOR sum of a subset of the chosen \(N\) values.

Since the set of values that can be formed by subset XORs constitutes a vector space (where XOR is considered as addition), we can determine this using a linear basis.

Analysis

Suppose we fix the choice of mode for each transmitter.

If we let \(A_i\) be the value chosen from transmitter \(i\), the values that can be formed are of the form:

\[ A_{i_1} \oplus A_{i_2} \oplus \cdots \oplus A_{i_k} \]

This is the XOR vector space spanned by \(A_1, A_2, \ldots, A_N\).

In other words, whether a target value \(T_j\) can be formed can be determined by:

\[ T_j \in \mathrm{span}(A_1, A_2, \ldots, A_N) \]

---

Naive Approach

There are \(2^N\) ways to choose the modes.

For each choice, if we also try all possible subsets of transmitters, there are \(2^N\) subsets, leading to a complexity of:

\[ O(2^N \cdot 2^N) \]

Since \(N \leq 15\), this is around \(2^{30}\) operations, which is too slow.

---

Optimization Using Linear Basis

By constructing a linear basis for XOR, we can perform the following operations efficiently:

• Add a value to the basis
• Determine if a value can be represented by the current basis

Since the values are between \(0\) and \(2^{60}-1\), the number of bits is at most \(60\).

Therefore, adding to the basis and checking membership can be done in \(O(60)\) time.

Additionally, instead of checking each target value \(T_j\) individually, we can construct the linear basis for the target values beforehand.

If we denote the space spanned by the target values as:

\[ \mathrm{span}(T_1, T_2, \ldots, T_M) \]

then the condition that all \(T_j\) can be formed is equivalent to:

\[ \mathrm{span}(T_1, T_2, \ldots, T_M) \subseteq \mathrm{span}(A_1, A_2, \ldots, A_N) \]

Thus, it is sufficient to check only the basis vectors of the target values.

For example, if the target values are \(T_1, T_2, T_3\) and \(T_3 = T_1 \oplus T_2\), then if \(T_1\) and \(T_2\) can be formed, \(T_3\) can also be formed.

Algorithm

1. Construct the XOR linear basis from the target values \(T_1, T_2, \ldots, T_M\).
2. If the rank of the target values’ basis is greater than \(N\), the answer is \(0\).
   • Since we choose at most \(N\) values, the rank of the space spanned by them is at most \(N\).
3. Divide the transmitters into the first half and the second half.
   • Let the size of the first half be \(n_1\).
   • Let the size of the second half be \(n_2\).
4. For the first half, precompute the linear basis for each mode choice.
5. Similarly, for the second half, precompute the linear basis for each mode choice.
6. Combine all choices of the first half and the second half.
7. For each combination, merge the basis of the first half with the basis of the second half to construct the overall basis.
8. If all basis vectors of the target values can be represented by the overall basis, then this mode choice satisfies the condition.
9. Count the number of choices that satisfy the condition.

---

XOR Linear Basis

In a linear basis, we maintain the “basis vector whose highest bit is at position \(i\)” for each bit.

For example, when adding a value \(x\) to the basis, we examine the bits from highest to lowest:

• If there is already a basis vector corresponding to that bit, we XOR \(x\) with it to clear the highest bit.
• If there is no corresponding basis vector, we add \(x\) as the new basis vector for this bit.

If \(x\) becomes \(0\) at the end, it means the original value was already representable by the basis.

Similarly, to determine if a value \(x\) can be represented by the current basis, we clear bits from highest to lowest; if it eventually becomes \(0\), it is representable.

Complexity

• Time complexity: around \(O(2^N \cdot 60 \cdot N)\)
• Space complexity: \(O(2^{N/2} \cdot 60)\)

Since \(N \leq 15\), we have \(2^N = 32768\), which runs sufficiently fast.

Implementation Details

• Since the values are at most \(2^{60}-1\), it is sufficient to examine bits from \(0\) to \(59\).

• It is safe to use unsigned long long to handle the XOR linear basis.

• Instead of checking all target values, it is sufficient to check only the linear basis of the target values.

• The answer should be output modulo \(10^9+7\).

• The XOR of an empty set is \(0\), but since a vector space always contains \(0\), no special handling is required.

  Source Code

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

using ull = unsigned long long;
const int MAXB = 60;
const long long MOD = 1000000007LL;

struct Basis {
    ull b[MAXB]{};
    int rank = 0;

    bool insert_vec(ull x) {
        for (int i = MAXB - 1; i >= 0; --i) {
            if (((x >> i) & 1ULL) == 0) continue;
            if (b[i]) x ^= b[i];
            else {
                b[i] = x;
                ++rank;
                return true;
            }
        }
        return false;
    }

    bool contains(ull x) const {
        for (int i = MAXB - 1; i >= 0; --i) {
            if (((x >> i) & 1ULL) == 0) continue;
            if (!b[i]) return false;
            x ^= b[i];
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

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

    Basis target_basis;
    for (int i = 0; i < M; ++i) {
        ull t;
        cin >> t;
        target_basis.insert_vec(t);
    }

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

    vector<ull> targets;
    for (int i = 0; i < MAXB; ++i) {
        if (target_basis.b[i]) targets.push_back(target_basis.b[i]);
    }

    int n1 = N / 2;
    int n2 = N - n1;

    int s1 = 1 << n1;
    int s2 = 1 << n2;

    vector<Basis> left(s1), right(s2);

    for (int mask = 0; mask < s1; ++mask) {
        Basis bs;
        for (int i = 0; i < n1; ++i) {
            bs.insert_vec((mask >> i) & 1 ? W[i] : V[i]);
        }
        left[mask] = bs;
    }

    for (int mask = 0; mask < s2; ++mask) {
        Basis bs;
        for (int i = 0; i < n2; ++i) {
            int idx = n1 + i;
            bs.insert_vec((mask >> i) & 1 ? W[idx] : V[idx]);
        }
        right[mask] = bs;
    }

    long long ans = 0;

    for (int lm = 0; lm < s1; ++lm) {
        for (int rm = 0; rm < s2; ++rm) {
            Basis bs = left[lm];

            for (int i = 0; i < MAXB; ++i) {
                if (right[rm].b[i]) bs.insert_vec(right[rm].b[i]);
            }

            bool ok = true;
            for (ull t : targets) {
                if (!bs.contains(t)) {
                    ok = false;
                    break;
                }
            }

            if (ok) {
                ++ans;
                if (ans >= MOD) ans -= MOD;
            }
        }
    }

    cout << ans % MOD << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.