概要

各送信機について \(V_i\) または \(W_i\) のどちらかを選び、選ばれた \(N\) 個の値の部分集合 XOR で、すべての目標値 \(T_j\) を作れるような選び方の数を求める問題です。

部分集合 XOR で作れる値の集合は、XOR を加法とみなした線形空間になるため、線形基底を使って判定します。

考察

あるモードの決定を固定したとします。

このとき、送信機 \(i\) から選ばれた値を \(A_i\) とすると、作れる値は

\[ A_{i_1} \oplus A_{i_2} \oplus \cdots \oplus A_{i_k} \]

の形の値です。

これは、\(A_1, A_2, \ldots, A_N\) が張る XOR の線形空間です。

つまり、目標値 \(T_j\) が作れるかどうかは、

\[ T_j \in \mathrm{span}(A_1, A_2, \ldots, A_N) \]

で判定できます。

---

素朴な方法

各モードの選び方は \(2^N\) 通りあります。

それぞれについて、さらに送信機の部分集合をすべて試すと、部分集合も \(2^N\) 通りあるため、

\[ O(2^N \cdot 2^N) \]

となります。

\(N \leq 15\) なので \(2^{30}\) 程度になり、かなり重いです。

---

線形基底による高速化

XOR に関する線形基底を作ると、次のことが効率よくできます。

• 値を基底に追加する
• ある値が現在の基底で表せるか判定する

値は \(0\) 以上 \(2^{60}-1\) 以下なので、ビット数は高々 \(60\) です。

したがって、基底への追加や所属判定は \(O(60)\) でできます。

また、すべての目標値 \(T_j\) を個別に判定する代わりに、目標値全体の線形基底を先に作っておきます。

目標値たちが張る空間を

\[ \mathrm{span}(T_1, T_2, \ldots, T_M) \]

とすると、すべての \(T_j\) が作れることは、

\[ \mathrm{span}(T_1, T_2, \ldots, T_M) \subseteq \mathrm{span}(A_1, A_2, \ldots, A_N) \]

と同値です。

そのため、目標値の基底ベクトルだけを判定すれば十分です。

例えば、目標値が \(T_1, T_2, T_3\) で、\(T_3 = T_1 \oplus T_2\) なら、\(T_1\) と \(T_2\) が作れれば \(T_3\) も必ず作れます。

アルゴリズム

1. 目標値 \(T_1, T_2, \ldots, T_M\) から XOR 線形基底を作る。
2. 目標値の基底のランクが \(N\) より大きい場合、答えは \(0\)。
   • 選ばれる値は高々 \(N\) 個なので、それらが張る空間のランクは最大でも \(N\) です。
3. 送信機を前半と後半に分ける。
   • 前半のサイズを \(n_1\)
   • 後半のサイズを \(n_2\) とする。
4. 前半について、各モード選択に対する線形基底をあらかじめ作る。
5. 後半についても同様に、各モード選択に対する線形基底を作る。
6. 前半の選び方と後半の選び方を全通り組み合わせる。
7. それぞれについて、前半の基底に後半の基底をマージし、全体の基底を作る。
8. 目標値の基底ベクトルがすべて全体の基底で表せるなら、そのモード選択は条件を満たす。
9. 条件を満たす選び方の数を数える。

---

XOR 線形基底について

線形基底では、各ビットについて「そのビットを最高位に持つ基底ベクトル」を管理します。

例えば、値 \(x\) を基底に追加するときは、高いビットから順に見ていきます。

• そのビットに対応する基底がすでにあるなら、\(x\) と XOR して最高位ビットを消す
• 対応する基底がないなら、\(x\) を新しい基底として追加する

最後に \(x = 0\) になれば、元の値はすでに基底で表せる値だったことになります。

値 \(x\) が現在の基底で表せるかどうかも同様に、高いビットから消していき、最終的に \(0\) になれば表せます。

計算量

• 時間計算量: \(O(2^N \cdot 60 \cdot N)\) 程度
• 空間計算量: \(O(2^{N/2} \cdot 60)\)

\(N \leq 15\) なので、\(2^N = 32768\) であり、十分高速に動作します。

実装のポイント

• 値は \(2^{60}-1\) 以下なので、ビットは \(0\) から \(59\) まで見れば十分です。

• XOR 線形基底は unsigned long long で扱うと安全です。

• 目標値はすべてを判定するのではなく、目標値の線形基底だけを判定すれば十分です。

• 答えは \(10^9+7\) で割った余りを出力します。

• 空集合の XOR は \(0\) ですが、線形空間には常に \(0\) が含まれるため、特別な処理は不要です。

  ソースコード

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

using ull = unsigned long long;
const int MAXB = 60;
const long long MOD = 1000000007LL;

struct Basis {
    ull b[MAXB]{};
    int rank = 0;

    bool insert_vec(ull x) {
        for (int i = MAXB - 1; i >= 0; --i) {
            if (((x >> i) & 1ULL) == 0) continue;
            if (b[i]) x ^= b[i];
            else {
                b[i] = x;
                ++rank;
                return true;
            }
        }
        return false;
    }

    bool contains(ull x) const {
        for (int i = MAXB - 1; i >= 0; --i) {
            if (((x >> i) & 1ULL) == 0) continue;
            if (!b[i]) return false;
            x ^= b[i];
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

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

    Basis target_basis;
    for (int i = 0; i < M; ++i) {
        ull t;
        cin >> t;
        target_basis.insert_vec(t);
    }

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

    vector<ull> targets;
    for (int i = 0; i < MAXB; ++i) {
        if (target_basis.b[i]) targets.push_back(target_basis.b[i]);
    }

    int n1 = N / 2;
    int n2 = N - n1;

    int s1 = 1 << n1;
    int s2 = 1 << n2;

    vector<Basis> left(s1), right(s2);

    for (int mask = 0; mask < s1; ++mask) {
        Basis bs;
        for (int i = 0; i < n1; ++i) {
            bs.insert_vec((mask >> i) & 1 ? W[i] : V[i]);
        }
        left[mask] = bs;
    }

    for (int mask = 0; mask < s2; ++mask) {
        Basis bs;
        for (int i = 0; i < n2; ++i) {
            int idx = n1 + i;
            bs.insert_vec((mask >> i) & 1 ? W[idx] : V[idx]);
        }
        right[mask] = bs;
    }

    long long ans = 0;

    for (int lm = 0; lm < s1; ++lm) {
        for (int rm = 0; rm < s2; ++rm) {
            Basis bs = left[lm];

            for (int i = 0; i < MAXB; ++i) {
                if (right[rm].b[i]) bs.insert_vec(right[rm].b[i]);
            }

            bool ok = true;
            for (ull t : targets) {
                if (!bs.contains(t)) {
                    ok = false;
                    break;
                }
            }

            if (ok) {
                ++ans;
                if (ans >= MOD) ans -= MOD;
            }
        }
    }

    cout << ans % MOD << '\n';
    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。