概要

各送信機をモード A / B のどちらかに設定したとき、稼働させる送信機の集合を自由に選んで得られる XOR の値（合成信号）の全体が、すべての目標信号値 \(T_j\) を含むような設定の数を数える問題です。

考察

XOR と線形空間

「いくつかの値を選んで XOR を取る」という操作は、\(\mathrm{GF}(2)\)（\(0,1\) の二元体）上のベクトル空間で考えると見通しが良くなります。各信号値を「ビットごとに \(0/1\) を並べた \(60\) 次元ベクトル」とみなすと、XOR はベクトルの加算（足し算）に対応します。

すると、送信機 \(1,\dots,N\) の信号値を \(x_1,\dots,x_N\) としたとき、部分集合を選んで作れる合成信号の全体は、\(x_1,\dots,x_N\) が張る線形空間（span）に一致します。空集合は \(0\) に対応します。

したがって、目標 \(T_j\) を実現できることは「\(T_j\) がこの線形空間に含まれること」と同値です。

すべての目標を実現できる条件

すべての \(T_j\) が span に含まれるためには、\(T_1,\dots,T_M\) が張る空間が、\(x_1,\dots,x_N\) が張る空間に含まれていればよいです。

ここで重要なのは、\(T\) 側を基底（linear basis）にまとめてしまえることです。\(M\) 個の目標すべてを個別にチェックする必要はなく、\(T\) から作った基底の各ベクトルが送信機側の span に入るかだけ確認すれば十分です。基底に含まれるベクトルがすべて入っていれば、その線形結合である任意の \(T_j\) も自動的に入るからです。

素朴なアプローチと枝刈り

\(N \le 15\) なので、モードの割り当ては最大 \(2^{15} = 32768\) 通りです。これは全列挙できます。各割り当てについて送信機側の基底を作り、目標基底のベクトルがすべて span に入るか判定すればよいです。

ただし、\(N\) 個のベクトルが張る空間の次元は高々 \(N\) です。よって目標基底の次元（ランク）が \(N\) を超えている場合、どんな割り当てでも実現不可能なので、即座に答え \(0\) を返せます（小さな枝刈りですが正当性のためにも有効です）。

アルゴリズム

1. 目標側の基底を作る: \(T_1,\dots,T_M\) から \(\mathrm{GF}(2)\) 上の線形基底 tbasis を構築する。最上位ビット位置ごとに代表ベクトルを保持する「掃き出し法」で実装する。
   • もし目標基底のランクが \(N\) を超えたら答えは \(0\)。
2. 全割り当てを列挙: \(2^N\) 通りの mask を試す。mask のビット \(i\) が立っていれば送信機 \(i\) はモード B（値 \(W_i\)）、立っていなければモード A（値 \(V_i\)）とする。
3. 送信機側の基底を構築: 選ばれた \(N\) 個の値から基底 basis を作る。
4. 包含判定: 目標基底の各ベクトル tv を basis で掃き出して \(0\) に落ちるか調べる。途中で最上位ビットに対応する基底ベクトルが存在せず \(0\) にできない場合、tv は span に含まれないので、その割り当ては不適。
5. すべての目標基底ベクトルが \(0\) に落ちる割り当ての数を数え、\(10^9+7\) で割った余りを出力する。

掃き出し（基底への挿入・判定）の流れ

ベクトル \(v\) について、最上位ビット位置 \(h\) を見て、basis[h] が存在すればそれと XOR して \(v\) を小さくし、存在しなければそこに \(v\) を登録する（挿入の場合）、あるいは \(0\) にできず失敗とする（判定の場合）、という操作を \(v\) が \(0\) になるまで繰り返します。

計算量

ビット幅を \(B=60\) とします。

• 目標基底の構築: \(O(M \cdot B)\)
• 各割り当ての処理: 基底構築に \(O(N \cdot B)\)、判定に \(O(\mathrm{rank} \cdot B) \le O(N \cdot B)\)
• これを \(2^N\) 通り行うので、全体で \(O(2^N \cdot N \cdot B)\)

したがって、

• 時間計算量: \(O(2^N \cdot N \cdot B + M \cdot B)\)（\(B=60\)）
• 空間計算量: \(O(B + N + M)\)

\(N \le 15\) より \(2^N \cdot N \cdot B\) は約 \(32768 \times 15 \times 60 \approx 3 \times 10^7\) 程度で、十分高速です。

実装のポイント

• 信号値は最大 \(2^{60}-1\) なので、基底配列のサイズは \(60\) で確保する。Python では多倍長整数をそのまま使えるため、ビット演算で素直に書ける。

• 最上位ビット位置は v.bit_length() - 1 で取得できる。

• 目標側は一度基底にまとめてから判定することで、\(M\) が大きくても判定回数を「基底の次元（高々 \(N\)）」に抑えられる。これが効率化の鍵。

• ランクが \(N\) を超えたら即 \(0\) を返す枝刈りを入れておくと、明らかに不可能なケースを高速に処理できる。

• 数える対象は割り当ての個数そのものなので、最後に % MOD を取って出力すればよい（\(2^N \le 32768\) なのでオーバーフローの心配はないが、問題指定に従って剰余を取る）。

  ソースコード

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()

---

この解説は claude4.8opus-high によって生成されました。