概要

各送信機の動作モード（AまたはB）を決定したときに、目標とするすべての信号値が「選んだ送信機の信号値の XOR（排他的論理和）の組み合わせ」によって作り出せるかを判定する問題です。

送信機の数 \(N\) が最大でも \(15\) と非常に小さいことに着目し、全探索とXORの線形基底（掃き出し法）を組み合わせることで効率的に解くことができます。

---

考察

1. 「XORで作れるか」をどう判定するか？

「いくつかの値の XOR 和によって特定の目標値を作れるか」という問題は、XORの線形基底（XOR Basis）を用いることで高速に判定できます。

これは、線形代数における「ベクトルの一次結合で表せるか（掃き出し法）」と全く同じ考え方です。 各信号値を \(2\) 進数で表したとき、各ビットを成分とするベクトルとみなすことができます。XOR 演算は、繰り上がりのない加算（GF(2) 上の加算）に対応します。

したがって、以下の手順で判定が可能になります： 1. 目標信号値の集合 \(T = \{T_1, T_2, \ldots, T_M\}\) から、それらを構成する「基底」の集合 \(B_T\) を求めます。 2. 各送信機で選んだ信号値の集合 \(X = \{x_1, x_2, \ldots, x_N\}\) から、同様に基底の集合 \(B_X\) を求めます。 3. \(T\) のすべての要素が \(X\) の要素の XOR 和で作れるための必要十分条件は、「\(B_T\) のすべての要素が \(B_X\) の要素の XOR 和で表せること」です。

2. \(N \le 15\) という制約の活用

各送信機について、モード A とモード B の \(2\) 通りの選択肢があります。 送信機の総数は \(N \le 15\) なので、モードの割り当て方は最大でも \(2^{15} = 32,768\) 通りしかありません。

この数は非常に小さいため、すべての割り当て方法（\(2^N\) 通り）をビット全探索し、それぞれについて条件を満たすかを判定すれば、実行時間制限に余裕で間に合います。

---

アルゴリズム

ステップ 1: 目標信号値 \(T\) の基底 \(B_T\) を求める

まず、目標信号値のリスト \(T\) から基底 \(B_T\) を構築します。 もし \(B_T\) のサイズ（基底の要素数）が \(N\) より大きくなった場合、送信機の数 \(N\) よりも独立な目標値の数が多いため、どのようにモードを選んでも絶対にすべての目標値を達成できません。この場合は即座に 0 を出力して終了します。

ステップ 2: モードの割り当てを全探索

\(0\) から \(2^N - 1\) までの整数 mask をループします。 mask の \(i\) 番目のビットが 0 ならば送信機 \(i\) はモード A（\(V_i\)）を、1 ならばモード B（\(W_i\)）を選択するものとします。

ステップ 3: 選択された信号値 \(X\) の基底 \(B_X\) を求める

各 mask について、選ばれた \(N\) 個の信号値から基底 \(B_X\) を構築します。

ステップ 4: 判定

\(B_T\) の各要素 \(t\) について、基底 \(B_X\) を使って掃き出しを行います。 具体的には、\(B_X\) の要素 \(b\) を用いて、\(t \oplus b < t\) となる場合に \(t \leftarrow t \oplus b\) と更新していきます。 最終的に \(t\) が \(0\) になれば、その \(t\) は \(B_X\) の要素の XOR 和で表せる（＝作ることができる）ということです。 \(B_T\) のすべての要素が \(0\) になった場合のみ、その mask は条件を満たすため、答えのカウンタを \(+1\) します。

---

計算量

値の最大ビット数を \(D = 60\) とします。

• 時間計算量: \(O(M \cdot D + 2^N \cdot N \cdot D)\)

  • \(T\) の基底を求めるのに \(O(M \cdot D)\)。
  • 各マスク（\(2^N\) 通り）において、基底 \(B_X\) の構築に \(O(N \cdot D)\)、判定に \(O(|B_T| \cdot D) = O(N \cdot D)\) かかります。
  • \(N = 15, M = 100, D = 60\) を代入すると、全体の最悪演算回数は約 \(32,768 \times 15 \times 60 \approx 3 \times 10^7\) 回となり、Pythonでも \(1\) 秒未満で高速に動作します。

• 空間計算量: \(O(N + M)\)

  • 基底のサイズは最大でも \(D\)（または \(N\)）であるため、非常に少ないメモリで動作します。

---

実装のポイント

• 基底の構築方法: 基底を追加する際は、値を大きい順（最上位ビットが立っている順）にソートして保持しておくと、掃き出しが簡単に行えます。 新しく要素 \(x\) を挿入する際は、既存の基底 \(b\) と比較し、\(x \oplus b < x\) となる（\(x\) の最上位ビットを消せる）場合に \(x \leftarrow x \oplus b\) と更新します。最終的に \(x > 0\) であれば、適切な位置（降順を維持する位置）に挿入します。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    M = int(data[1])
    
    pairs = []
    idx = 2
    for _ in range(N):
        v = int(data[idx])
        w = int(data[idx+1])
        pairs.append((v, w))
        idx += 2
        
    T = [int(x) for x in data[idx:idx+M]]
    
    # T の基底を求める
    basis_T = []
    for t in T:
        for b in basis_T:
            if (t ^ b) < t:
                t ^= b
        if t > 0:
            inserted = False
            for i in range(len(basis_T)):
                if t > basis_T[i]:
                    basis_T.insert(i, t)
                    inserted = True
                    break
            if not inserted:
                basis_T.append(t)
                
    if len(basis_T) > N:
        print(0)
        return
        
    ans = 0
    pow2 = [1 << i for i in range(N)]
    
    for mask in range(1 << N):
        basis_X = []
        for i, (v, w) in enumerate(pairs):
            x = w if (mask & pow2[i]) else v
            for b in basis_X:
                if (x ^ b) < x:
                    x ^= b
            if x > 0:
                inserted = False
                for j in range(len(basis_X)):
                    if x > basis_X[j]:
                        basis_X.insert(j, x)
                        inserted = True
                        break
                if not inserted:
                    basis_X.append(x)
                    
        possible = True
        for t in basis_T:
            for b in basis_X:
                if (t ^ b) < t:
                    t ^= b
            if t > 0:
                possible = False
                break
        if possible:
            ans += 1
            
    print(ans % 1000000007)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3.5-flash-high によって生成されました。