概要

2つのグループからそれぞれ部分集合を選び、選んだ要素のXORを \(X, Y\) としたときに \(X + Y = S\) となる選び方の総数を求める問題です。

考察

この問題を素朴に解こうとすると、第1グループから選ぶ要素の組み合わせは \(2^N\) 通り、第2グループも \(2^N\) 通りあるため、全体で \(2^{2N}\) 通りの組み合わせを調べる必要があります。\(N=50\) の場合、これは天文学的な数になり、実行時間制限に間に合いません。

ここで、問題を2つの独立した部分問題に分割することを考えます。 第1グループから選んだ部分集合のXORを \(X\)、第2グループから選んだ部分集合のXORを \(Y\) とします。 目標は \(X + Y = S\) を満たす組 \((X, Y)\) の選び方の総数を求めることです。

もし、「第1グループから選んだ部分集合のXORが \(x\) になる選び方の数」が分かっていれば、それに対応する「第2グループから選んだ部分集合のXORが \(S - x\) になる選び方の数」を掛け合わせることで、条件を満たす組の数が計算できます。

XORの値の範囲は、要素の最大値が \(2^{20}\) 未満であるため、\(0\) 以上 \(2^{20}-1\) 以下の整数に収まります。したがって、各グループについて「XORが各値になる選び方の数」を計算できれば、全体の答えを効率よく求めることができます。

アルゴリズム

動的計画法（DP）を用いて、各グループのXORの分布を求めます。

1. DPの定義:

   • dpA[x]: 第1グループから要素を選び、そのXORが \(x\) になるような選び方の総数
   • dpB[y]: 第2グループから要素を選び、そのXORが \(y\) になるような選び方の総数

2. DPの初期化:

   • どの要素も選ばないとき、XORは \(0\) になるため、dpA[0] = 1, dpB[0] = 1 とします。

3. DPの遷移:

   • 要素を1つずつ見ていき、「その要素を選ばない場合」と「その要素を選ぶ場合」で配列を更新します。
   • 要素 \(A_i\) を追加する場合、現在のXORが \(j\) である選び方を元に、\(A_i\) を選ぶとXORが \(j \oplus A_i\) （\(\oplus\) はXOR演算）に遷移します。
   • 具体的には、新しい配列 nextA を用意し、nextA[j] += dpA[j]（選ばない場合）と nextA[j \oplus A[i]] += dpA[j]（選ぶ場合）を行います。
   • 全ての要素について遷移を行えば、最終的なXORの分布が求まります。第2グループについても同様です。

4. 答えの計算:

   • 第1グループのXORを \(x\) と固定したとき、第2グループのXORは \(y = S - x\) である必要があります。
   • \(y\) が \(0\) 以上 \(2^{20}\) 未満の範囲にある場合、ans += dpA[x] * dpB[S - x] と足し合わせることで全体の答えが求まります。

計算量

• 時間計算量: \(O(N \cdot 2^{20})\)。DPの更新が \(N\) 回、各更新で \(2^{20}\) 通りの状態を処理するため。2つのグループで行うため全体で約 \(2 \cdot 50 \cdot 2^{20} \approx 10^8\) 回のループとなり、十分に間に合います。
• 空間計算量: \(O(2^{20})\)。DPテーブルとしてサイズ \(2^{20}\) の配列を2つ用意するため。

実装のポイント

• DPテーブルのサイズは \(2^{20} = 1048576\) と大きいため、std::vector の copy と swap を用いて効率的に配列の更新と入れ替えを行います。

• 最後に \(X + Y = S\) を計算する際、\(y = S - x\) が負の値や \(2^{20}\) 以上の値になる場合は、第2グループで到達不可能なXOR値であるため、配列の範囲外アクセスを防ぐために条件分岐で除外する必要があります。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int N;
    long long S;
    if (!(cin >> N >> S)) return 0;

    vector<int> A(N), B(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) cin >> B[i];

    const int SZ = 1 << 20;
    vector<long long> dpA(SZ, 0), nextA(SZ, 0);
    dpA[0] = 1;

    for (int i = 0; i < N; ++i) {
        copy(dpA.begin(), dpA.end(), nextA.begin());
        for (int j = 0; j < SZ; ++j) {
            nextA[j ^ A[i]] += dpA[j];
        }
        swap(dpA, nextA);
    }

    vector<long long> dpB(SZ, 0), nextB(SZ, 0);
    dpB[0] = 1;

    for (int i = 0; i < N; ++i) {
        copy(dpB.begin(), dpB.end(), nextB.begin());
        for (int j = 0; j < SZ; ++j) {
            nextB[j ^ B[i]] += dpB[j];
        }
        swap(dpB, nextB);
    }

    long long ans = 0;
    for (int x = 0; x < SZ; ++x) {
        long long y = S - x;
        if (y >= 0 && y < SZ) {
            ans += dpA[x] * dpB[y];
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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