概要

各送信機のモード（AまたはB）を選び、選んだ信号値の集合から作れるXORの範囲に、すべての目標信号値が含まれるようなモードの割り当て方の総数を求める問題です。

考察

送信機をいくつか選んでXORをとった値が目標信号値 \(T_j\) と一致するということは、選んだモードの信号値の集合が張る「XOR空間」に \(T_j\) が含まれるということです。

\(N \leq 15\) と小さいため、各送信機のモードをAかBか選ぶ全 \(2^N\) 通りの組み合わせを探索する方針が立ちます。素朴にすべての組み合わせを列挙し、それぞれの組み合わせで \(M\) 個の目標信号値が作れるかを判定するのは、組み合わせごとに部分集合を考えると計算量が大きくなりすぎます。

ここで、「ある数の集合が作れるXORの範囲」を効率よく管理する線形基底という概念を用います。線形基底を使うと、ある値 \(x\) がその集合のXORで作れるかどうかを \(O(60)\) で判定できます。

したがって、DFS（深さ優先探索）を用いて送信機のモードを1つずつ選び、その値を線形基底に追加していくことで状態を管理します。すべての送信機のモードを選び終わった段階で、\(M\) 個の目標信号値がすべて現在の線形基底が張る空間に含まれるかを確認すれば良いです。

アルゴリズム

1. DFSによる全探索: 各送信機 \(i\) について、モードA（値 \(V_i\)）を選ぶ場合とモードB（値 \(W_i\)）を選ぶ場合の2通りに分岐します。
2. 線形基底の構築: 選んだ値を現在の線形基底（配列 basis）に追加します。線形基底への追加は、値の最上位ビットを見て、すでにそのビット位置に基底が存在すればXORをとってビットを落とし、空いていればその位置に基底として登録します。
3. バックトラック（状態の復元）: DFSから戻ってきた際、基底に追加した要素があれば削除して状態を元に戻します。これにより、余分なメモリを確保することなく1つの配列で状態を管理できます。
4. 判定: すべての送信機のモードを選び終わったら（\(i = N\)）、目標信号値 \(T_1, \ldots, T_M\) について、それぞれが現在の線形基底で表現できるか（基底ベクトルのXORで \(0\) にできるか）を確認します。すべて表現できれば \(1\)、1つでもできなければ \(0\) を返します。

計算量

• 時間計算量: \(O(2^N \cdot (N+M) \cdot 60)\) 葉ノードの数は \(2^N\) 通り、各ノードで \(M\) 個のチェックを行い各チェックに \(O(60)\) かかります。基底の追加も \(O(60)\) です。\(N=15, M=100\) で \(2 \times 10^8\) 程度の演算となり、C++なら十分に実行時間内に終わります。
• 空間計算量: \(O(60)\) 線形基底の配列 basis[60] と入力の保存に必要なメモリです。再帰の深さは \(N\) です。

実装のポイント

• 線形基底に値を追加する際、既存の基底とXORをとることで値の最上位ビットを下にずらしていく処理が必要です。

• 追加できた場合（pos != -1）は、DFSから戻った後に basis[pos] = 0 として状態をロールバックします。追加できなかった場合（値がすでに空間に含まれる場合）は基底が変わらないため、ロールバックは不要です。

• 64ビット整数（unsigned long long）を用いてビット演算を行います。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;

int N, M;
vector<unsigned long long> V, W, T;
unsigned long long basis[60];

int dfs(int i) {
    if (i == N) {
        for (int j = 0; j < M; ++j) {
            unsigned long long val = T[j];
            for (int k = 59; k >= 0; --k) {
                if (val & (1ULL << k)) {
                    if (basis[k]) val ^= basis[k];
                    else break;
                }
            }
            if (val != 0) return 0;
        }
        return 1;
    }
    
    int res = 0;
    
    // Choice A
    {
        unsigned long long v = V[i];
        int pos = -1;
        for (int k = 59; k >= 0; --k) {
            if (v & (1ULL << k)) {
                if (basis[k]) v ^= basis[k];
                else {
                    basis[k] = v;
                    pos = k;
                    break;
                }
            }
        }
        res = (res + dfs(i + 1)) % MOD;
        if (pos != -1) basis[pos] = 0;
    }
    
    // Choice B
    {
        unsigned long long w = W[i];
        int pos = -1;
        for (int k = 59; k >= 0; --k) {
            if (w & (1ULL << k)) {
                if (basis[k]) w ^= basis[k];
                else {
                    basis[k] = w;
                    pos = k;
                    break;
                }
            }
        }
        res = (res + dfs(i + 1)) % MOD;
        if (pos != -1) basis[pos] = 0;
    }
    
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if (!(cin >> N >> M)) return 0;
    
    V.resize(N);
    W.resize(N);
    T.resize(M);
    
    for (int i = 0; i < N; ++i) {
        cin >> V[i] >> W[i];
    }
    for (int i = 0; i < M; ++i) {
        cin >> T[i];
    }
    
    cout << dfs(0) << "\n";
    
    return 0;
}

この解説は or-glm5.2-high によって生成されました。