概要

各送信機のモード（AまたはB）の割り当て \(2^N\) 通りのうち、選択された送信機の出力値のXOR（排他的論理和）和によって、与えられた \(M\) 個の目標信号値すべてを表現できるような割り当ての総数を求める問題です。

考察

1. 制約に着目する

送信機の数 \(N\) が \(15\) 以下と非常に小さいことに注目します。各送信機のモードは A と B の \(2\) 通りなので、すべての割り当てパターンは \(2^N \le 2^{15} = 32,768\) 通りしかありません。したがって、すべての割り当てを全探索し、それぞれについて条件を満たすか判定するアプローチが有効です。

2. XOR和による表現可能性の判定（線形基底）

あるモードの割り当て（送信機の出力値の集合 \(X = \{X_1, X_2, \dots, X_N\}\)）が決まったとき、目標信号値 \(T_j\) を \(X\) の部分集合のXOR和で表現できるかを高速に判定する必要があります。

これは、XORを足し算とみなした \(\mathbb{F}_2\) 上のベクトル空間（線形代数）の問題として捉えることができます。 集合 \(X\) から線形基底（Linear Basis）を構築することで、任意の数 \(T_j\) が \(X\) の要素のXOR和で表せるかどうかを \(O(\log(\max T_j))\) の時間で判定できます。

3. 目標信号値の整理による高速化

目標信号値 \(T_1, T_2, \dots, T_M\) のすべてが表現可能かを愚直に判定すると、各割り当てに対して \(M\) 回の判定が必要になります。 ここで、目標信号値の集合 \(T\) 自体の線形基底 \(T_{\text{basis}}\) をあらかじめ求めておくことで、判定を高速化できます。 「\(T\) のすべての要素が表現可能である」ことと、「\(T\) の線形基底のすべての要素が表現可能である」ことは同値です。\(T\) の基底のサイズは最大でもビット数（今回は \(60\)）以下になるため、判定回数を大幅に削減できます。

---

アルゴリズム

1. 目標信号値の基底の構築 入力された \(M\) 個の目標信号値 \(T_1, \dots, T_M\) から、掃き出し法（ガウスの消去法）を用いて線形基底 target_basis を構築します。 もし target_basis のサイズが送信機の数 \(N\) よりも大きければ、どのようにモードを選んでも表現不可能であるため、即座に 0 を出力して終了します（早期リターン）。

2. 割り当ての全探索 \(0\) から \(2^N - 1\) までの整数 mask をループします。mask の第 \(i\) ビットが 0 なら送信機 \(i\) のモードを A（値 \(V_i\)）、1 なら B（値 \(W_i\)）とします。これにより、各送信機の出力値の集合 \(X\) が決まります。

3. 送信機出力の基底の構築 決定した \(X\) の要素から、同様に掃き出し法を用いて線形基底 basis を構築します。

4. 表現可能性の判定 target_basis の各要素 \(t\) について、basis を用いて表現できるか判定します。 具体的には、\(t\) の最上位ビットから順に、basis に同じ最上位ビットを持つ要素があれば XOR を取っていきます。最終的に \(t\) が \(0\) になれば表現可能です。 target_basis のすべての要素が表現可能であれば、その mask は条件を満たすため、答えのカウントを \(1\) 増やします。

5. 出力 最終的なカウントを \(10^9 + 7\) で割った余りを出力します。

---

計算量

• 時間計算量: \(O(M \log(\max T) + 2^N \cdot N \log(\max V))\)

  • 目標信号値の基底構築に \(O(M \log(\max T))\) かかります。
  • 各割り当ての探索（\(2^N\) 回）において、送信機の基底構築に \(O(N \log(\max V))\)、表現可能性の判定に \(O(B \log(\max V))\)（\(B\) は target_basis のサイズで \(B \le N\)）かかります。
  • \(N \le 15\)、\(\log(\max V) \le 60\) であるため、最悪の場合でもループ内の計算回数は \(3.2 \times 10^4 \times 15 \times 60 \approx 2.9 \times 10^7\) 回の基本操作となり、実行時間制限（通常2秒）に十分間に合います。

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

  • 基底や入力データを保持するための配列のみを使用するため、極めて省メモリです。

---

実装のポイント

• std::bit_width の活用 C++20 で導入された std::bit_width を使用することで、ある数の最上位ビット（MSB）の位置（2進数で表したときの桁数）を高速に取得できます。これにより、掃き出し法の処理をシンプルかつ高速に記述できます。

• 早期リターン 目標信号値の基底のサイズが \(N\) を超えている場合、送信機の数が足りず絶対に表現できないため、探索を行う前に \(0\) を出力して終了することで無駄な計算を省いています。

  ソースコード

#include <iostream>
#include <vector>
#include <bit>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> V(N), W(N);
    for (int i = 0; i < N; ++i) {
        cin >> V[i] >> W[i];
    }

    vector<long long> T(M);
    for (int j = 0; j < M; ++j) {
        cin >> T[j];
    }

    vector<long long> t_basis(61, 0);
    for (int j = 0; j < M; ++j) {
        long long x = T[j];
        while (x > 0) {
            int bit = std::bit_width(static_cast<unsigned long long>(x)) - 1;
            if (!t_basis[bit]) {
                t_basis[bit] = x;
                break;
            }
            x ^= t_basis[bit];
        }
    }

    vector<long long> target_basis;
    for (int bit = 60; bit >= 0; --bit) {
        if (t_basis[bit]) {
            target_basis.push_back(t_basis[bit]);
        }
    }

    if (target_basis.size() > N) {
        cout << 0 << "\n";
        return 0;
    }

    long long ans = 0;
    vector<long long> X(N);
    vector<long long> basis(61);
    vector<pair<int, long long>> basis_list;
    basis_list.reserve(N);

    for (int mask = 0; mask < (1 << N); ++mask) {
        for (int i = 0; i < N; ++i) {
            X[i] = (mask & (1 << i)) ? W[i] : V[i];
        }

        fill(basis.begin(), basis.end(), 0);
        for (int i = 0; i < N; ++i) {
            long long x = X[i];
            while (x > 0) {
                int bit = std::bit_width(static_cast<unsigned long long>(x)) - 1;
                if (!basis[bit]) {
                    basis[bit] = x;
                    break;
                }
                x ^= basis[bit];
            }
        }

        basis_list.clear();
        for (int bit = 60; bit >= 0; --bit) {
            if (basis[bit]) {
                basis_list.push_back({bit, basis[bit]});
            }
        }

        bool ok = true;
        for (long long t : target_basis) {
            for (auto [bit, val] : basis_list) {
                if ((t >> bit) & 1) {
                    t ^= val;
                }
            }
            if (t != 0) {
                ok = false;
                break;
            }
        }

        if (ok) {
            ans++;
        }
    }

    cout << ans % 1000000007 << "\n";

    return 0;
}

---

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