概要

各送信機について \(V_i\) か \(W_i\) のどちらかを選び、選ばれた \(N\) 個の値の XOR で作れる値の集合が、すべての目標値 \(T_j\) を含むような選び方の数を求めます。

XOR はビットごとの足し算を \(\bmod 2\) で行う操作なので、線形代数の「基底」を使って判定できます。

考察

送信機のモードを固定したとします。

このとき、各送信機から得られる値を \(X_1, X_2, \ldots, X_N\) とすると、稼働させる送信機の部分集合を自由に選べるので、作れる値は

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

の形で表せるすべての値です。

これは、\(X_1, X_2, \ldots, X_N\) が張る XOR の線形空間と考えられます。

つまり、ある目標値 \(T\) が作れるかどうかは、

\(T\) が選ばれた値たちの XOR 線形結合で表せるか

を判定すればよいです。

---

素朴には、各モードの選び方 \(2^N\) 通りについて、さらに部分集合 \(2^N\) 通りを列挙して作れる XOR を調べる方法が考えられます。

しかしこれは全体でおよそ

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

となり、\(N = 15\) でもかなり重くなります。

そこで、各選び方について「XOR 基底」を作ります。

XOR 基底を使うと、ある値が作れるかどうかを \(O(60)\) 程度で判定できます。値は \(2^{60}\) 未満なので、見るべきビット数は最大 \(60\) 個です。

---

また、目標値 \(T_1, T_2, \ldots, T_M\) すべてを毎回確認する必要はありません。

目標値たち自身についても XOR 基底を作ります。

例えば、ある目標値が他の目標値の XOR で表せるなら、その目標値は独立に確認する必要がありません。

目標値全体の XOR 基底を \(B_T\) とすると、選ばれた送信機の値の張る空間が \(B_T\) の各基底ベクトルを含んでいれば、すべての \(T_j\) を作れることになります。

---

さらに、選ばれた送信機は \(N\) 個しかないので、それらが張る空間の次元は最大でも \(N\) です。

したがって、目標値たちの XOR 基底のランクが \(N\) を超えている場合、絶対にすべての目標値を作ることはできません。

この場合は答えは \(0\) です。

アルゴリズム

まず、目標値 \(T_1, T_2, \ldots, T_M\) から XOR 基底を作ります。

この基底のランクを target_rank とします。

• target_rank == 0 の場合
  すべての目標値は \(0\) です。
  \(0\) は空集合を選べば必ず作れるので、どのモード選択でも条件を満たします。
  よって答えは \(2^N\) です。

• target_rank > N の場合
  \(N\) 個の値から作れる XOR 空間のランクは最大 \(N\) なので不可能です。
  よって答えは \(0\) です。

それ以外の場合、各モード選択を全探索します。

モード選択はビットマスクで表します。

• mask の \(i\) ビット目が \(0\) なら送信機 \(i\) はモード A、つまり \(V_i\)
• mask の \(i\) ビット目が \(1\) なら送信機 \(i\) はモード B、つまり \(W_i\)

とします。

各 mask について、選ばれた値たちから XOR 基底を作ります。

その後、目標値の基底に含まれる各値が、この基底で表せるかを調べます。

すべて表せるなら、そのモード選択は条件を満たすので答えに \(1\) を加えます。

---

XOR 基底では、basis[p] に「最上位ビットが \(p\) である基底ベクトル」を持たせます。

値 \(x\) を基底に追加するときは、次のようにします。

1. \(x\) の最上位ビットを \(p\) とする
2. basis[p] が存在すれば、\(x \leftarrow x \oplus basis[p]\) として最上位ビットを消す
3. basis[p] が存在しなければ、そこに \(x\) を登録する
4. \(x = 0\) になった場合、すでに基底で表せるので追加しない

ある値 \(x\) が基底で表せるかどうかも同様です。

最上位ビットを順に消していき、最後に \(0\) になれば表せます。途中で消せないビットが出たら表せません。

計算量

\(B = 60\) とします。

• 時間計算量: \(O\left(MB + 2^N \cdot (N + R)B\right)\)
  ここで \(R\) は目標値の XOR 基底のサイズで、\(R \leq 60\) です。
• 空間計算量: \(O(N + M + B)\)

制約では \(N \leq 15\) なので、\(2^N\) 通りの全探索は十分間に合います。

実装のポイント

値はすべて \(2^{60}\) 未満なので、XOR 基底の配列サイズは \(60\) で十分です。

basis = [0] * 60

insert_basis は、基底に新しい値を追加できた場合に True を返します。これにより、目標値たちのランクを数えられます。

if insert_basis(target_basis_arr, t):
    target_rank += 1

また、目標値はすべてを毎回確認するのではなく、目標値の基底だけを確認します。

target_basis = [x for x in target_basis_arr if x]

これにより、\(M\) が最大 \(100\) でも効率よく判定できます。

ソースコード

import sys

MOD = 10**9 + 7

def insert_basis(basis, x):
    while x:
        p = x.bit_length() - 1
        if basis[p]:
            x ^= basis[p]
        else:
            basis[p] = x
            return True
    return False

def in_span(basis, x):
    while x:
        p = x.bit_length() - 1
        if basis[p] == 0:
            return False
        x ^= basis[p]
    return True

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    idx = 0
    N = data[idx]
    M = data[idx + 1]
    idx += 2

    V = [0] * N
    W = [0] * N
    for i in range(N):
        V[i] = data[idx]
        W[i] = data[idx + 1]
        idx += 2

    T = data[idx:idx + M]

    target_basis_arr = [0] * 60
    target_rank = 0
    for t in T:
        if insert_basis(target_basis_arr, t):
            target_rank += 1

    if target_rank == 0:
        print(pow(2, N, MOD))
        return

    if target_rank > N:
        print(0)
        return

    target_basis = [x for x in target_basis_arr if x]

    ans = 0
    for mask in range(1 << N):
        basis = [0] * 60

        for i in range(N):
            x = W[i] if (mask >> i) & 1 else V[i]
            insert_basis(basis, x)

        ok = True
        for t in target_basis:
            if not in_span(basis, t):
                ok = False
                break

        if ok:
            ans += 1

    print(ans % MOD)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。