概要

各送信機をモード A・B のどちらかに設定したとき、選んだ信号値の XOR ですべての目標信号値 \(T_j\) を作れるような設定の数を数える問題です。\(N \leq 15\) と小さいので、\(2^N\) 通りの設定をすべて試すことができます。

考察

まず、「いくつかの送信機を稼働させたときの XOR」で作れる値の集合について考えます。\(N\) 個の値 \(a_1, a_2, \ldots, a_N\) から、好きな部分集合を選んで XOR を取って作れる値の全体は、これらの値が張る線形空間（XOR 空間）になります。

ここで重要なのは次の観察です。

ある目標値 \(T_j\) が「部分集合の XOR で作れる」かどうかは、\(\{a_1, \ldots, a_N\}\) が張る XOR 空間に \(T_j\) が含まれるかどうかと同値である。

XOR は GF(2)（2 元体）上のベクトル演算とみなせるため、線形代数の考え方がそのまま使えます。値を 60 ビットのベクトルとみなし、「掃き出し法（ガウスの消去法）」で基底（XOR 基底 / linear basis）を作れば、

• ある値 \(T\) が空間に含まれる ⟺ \(T\) を基底で消去していったとき最終的に \(0\) になる

という判定ができます。

素朴に「各 \(T_j\) について部分集合 \(2^N\) 通りを全探索」してしまうと、設定 \(2^N\) 通り × 目標 \(M\) 個 × 部分集合 \(2^N\) 通りとなり非常に重くなります。XOR 基底を使えば、各目標の判定が高速（ビット数程度）に行えるため、効率よく処理できます。

アルゴリズム

1. モードの割り当ては \(2^N\) 通り。各送信機 \(i\) について mask の \(i\) ビット目が立っていれば \(W_i\)、立っていなければ \(V_i\) を使う、というように mask（\(0\) 以上 \(2^N\) 未満の整数）で全パターンを列挙します。

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

   • basis[b] を「最上位ビットが \(b\) である基底ベクトル」とします。
   • 値 \(x\) を上位ビットから見ていき、立っているビット \(b\) について basis[b] がまだ空なら \(x\) をそこに登録、そうでなければ \(x \mathbin{\oplus}= \mathrm{basis}[b]\) として消去を続けます。

3. すべての目標値 \(T_j\) について、同じ要領で基底を使って \(T_j\) を消去します。

   • 消去後に \(0\) になれば「作れる」、\(0\) にならなければ「作れない」。
   • 1 つでも作れない目標があれば、その mask は条件を満たしません。

4. 条件を満たす mask の個数を数え、\(10^9+7\) で割った余りを出力します。

具体例として、\(V = (3, 5)\) で両方モード A を選んだとします。\(3 = (011)_2\), \(5 = (101)_2\) が張る空間には \(3 \oplus 5 = 6\) や \(0\) も含まれ、\(\{0, 3, 5, 6\}\) が作れます。目標 \(T = 6\) なら、基底で消去すると \(0\) になるので「作れる」と判定されます。

計算量

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

• 各 mask ごとに基底構築が \(O(N \cdot B)\)、目標判定が \(O(M \cdot B)\)。

• これを \(2^N\) 通り行うので、

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

• 空間計算量: \(O(N + M + B)\)（基底配列はビット幅ぶんで定数サイズ）

\(N \leq 15\), \(M \leq 100\), \(B = 60\) より十分高速に間に合います。

実装のポイント

• 信号値は最大 \(2^{60}-1\) なので、必ず 64 ビット整数（unsigned long long）で扱います。ビットを取り出す際のシフトも 1ULL << b のように 64 ビットで行うことに注意してください。

• 各 mask ごとに基底配列を必ず初期化（ゼロクリア）してから構築します。

• 答えを数える際、\(2^{15} = 32768\) 通りしかないので途中でオーバーフローの心配はほぼありませんが、最後に MOD を取っておけば安全です。

• 空集合の XOR は \(0\) であり、これは常に基底で消去して \(0\) になるため、\(T_j = 0\) の目標は自動的に「作れる」と判定されます（特別扱い不要）。

  ソースコード

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

int main(){
    int N, M;
    scanf("%d %d", &N, &M);
    vector<unsigned long long> V(N), W(N);
    for(int i=0;i<N;i++){
        scanf("%llu %llu", &V[i], &W[i]);
    }
    vector<unsigned long long> T(M);
    for(int j=0;j<M;j++) scanf("%llu", &T[j]);
    
    const long long MOD = 1000000007;
    long long ans = 0;
    
    for(int mask=0; mask<(1<<N); mask++){
        // build basis
        unsigned long long basis[64];
        for(int b=0;b<64;b++) basis[b]=0;
        for(int i=0;i<N;i++){
            unsigned long long x = (mask>>i&1) ? W[i] : V[i];
            for(int b=59;b>=0;b--){
                if(!((x>>b)&1ULL)) continue;
                if(basis[b]==0){ basis[b]=x; break; }
                x ^= basis[b];
            }
        }
        // check all targets
        bool ok=true;
        for(int j=0;j<M && ok;j++){
            unsigned long long x = T[j];
            for(int b=59;b>=0;b--){
                if(!((x>>b)&1ULL)) continue;
                if(basis[b]==0){ ok=false; break; }
                x ^= basis[b];
            }
            if(x!=0) ok=false;
        }
        if(ok){
            ans++;
            if(ans>=MOD) ans-=MOD;
        }
    }
    
    printf("%lld\n", ans%MOD);
    return 0;
}

---

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