概要

各グループから部分集合を選んで得られる XOR の値 \(X, Y\) について \(X + Y = S\) となる「選び方の組」の個数を数える問題です。XOR が線形代数（\(\mathrm{GF}(2)\) 上のベクトル空間）の構造を持つことを利用して解きます。

考察

素朴なアプローチの問題点

各グループは \(N \le 50\) 人いるので、部分集合の選び方は各グループ \(2^{50}\) 通り、組み合わせると最大 \(2^{100}\) 通りにもなります。全列挙は到底間に合いません。

重要な気づき1：XOR は線形空間をなす

部分集合の XOR を考えると、これは「スキル値ベクトルの \(\mathrm{GF}(2)\) 上の線形結合」と見なせます。第 \(1\) グループのスキル値から作れる XOR の集合（張る空間, span）は、基底のランクを \(r_1\) とすると、ちょうど \(2^{r_1}\) 個の異なる値からなります。

さらに重要なのは、ある到達可能な値 \(X\) を作る部分集合の個数はすべて等しく \(2^{N - r_1}\) 個である、という事実です。これは、XOR が \(0\) になる部分集合（核）の個数が \(2^{N - r_1}\) 個であり、それらをずらすことで各到達値が同じ回数現れるためです。

例えばスキル値が \(\{3, 3\}\) の場合、基底は \(\{3\}\) でランク \(1\)、到達可能な XOR は \(\{0, 3\}\) の \(2\) 値です。\(0\) は「何も選ばない」「両方選ぶ」の \(2\) 通り（\(=2^{2-1}\)）、\(3\) も「1人目だけ」「2人目だけ」の \(2\) 通りで作れます。

重要な気づき2：値ごとにまとめて数える

したがって、

• 第 \(1\) グループの到達可能値 \(X\)、第 \(2\) グループの到達可能値 \(Y\) について \(X + Y = S\) を満たす (値の)ペア数 を \(C\) とする
• それぞれの値を作る部分集合の数は \(2^{N-r_1}\) 個と \(2^{N-r_2}\) 個

なので、求める答えは

\[ C \times 2^{N - r_1} \times 2^{N - r_2} = C \times 2^{2N - r_1 - r_2} \]

となります。あとは値のペア数 \(C\) を求めればよいです。

値のペア数の数え方

到達可能値の個数は最大でも \(2^{r_1}, 2^{r_2}\) ですが、スキル値が \(2^{20}\) 未満なのでランクは高々 \(20\)、つまり値の種類は最大 \(2^{20}\) 個です。

そこで次のようにします。

1. 第 \(2\) グループの到達可能値 \(Y\) をすべて列挙し、inB[Y] = true と長さ \(2^{20}\) の配列に記録する。
2. 第 \(1\) グループの到達可能値 \(X\) をすべて列挙し、\(Y = S - X\) が \(0 \le Y < 2^{20}\) かつ inB[Y] が真なら、ペアとしてカウントする。

これで \(C\) が \(O(2^{20})\) で求まります。

アルゴリズム

1. 基底の構築：掃き出し法で各グループのスキル値から基底を作り、ランク \(r_1, r_2\) を求める。
2. span B の列挙：基底の部分集合の XOR を全列挙し、到達可能値を配列 inB に記録する。
3. span A の列挙とマッチング：同様に span A の各値 \(X\) について \(S - X\) が span B に含まれるか確認し、ペア数 \(C\) を数える。
4. 答えの計算：\(C \times 2^{2N - r_1 - r_2}\) を出力する。

span の列挙では、グレイコードを使うと効率的です。\(i\) を \(1\) から \(2^r - 1\) まで増やし、変化したビット位置（__builtin_ctzll(i)）の基底ベクトルだけを XOR で足し引きすることで、毎回 \(O(1)\) で次の値に更新できます。

計算量

基底の値が \(2^{20}\) 未満なのでランクは高々 \(20\)、span のサイズは高々 \(2^{20}\) です。

• 時間計算量: \(O(2^{r_1} + 2^{r_2}) = O(2^{20})\)（基底構築は \(O(N \cdot 20)\)）
• 空間計算量: \(O(2^{20})\)（inB 配列）

実装のポイント

• 到達値を作る部分集合数の公式：「答え \(= C \times 2^{2N - r_1 - r_2}\)」が本質です。各到達値が同じ回数（\(2^{N-r}\) 回）作られることを必ず押さえましょう。

• 範囲チェック：\(S < 2^{21}\)、\(X < 2^{20}\) なので \(Y = S - X\) は負になったり \(2^{20}\) 以上になったりし得ます。inB 配列の範囲外アクセスを防ぐため、\(0 \le Y < 2^{20}\) を必ず確認します。

• オーバーフロー対策：答えは \(2^{63}\) 未満が保証されているため、\(C > 0\) のときシフト量 \(2N - r_1 - r_2\) は \(64\) 未満に収まります。unsigned long long で C << power を計算すれば安全です（\(C = 0\) のときは \(0\) を出力）。

• グレイコード列挙：val ^= basis[__builtin_ctzll(i)] という更新で、span の全要素を重複なく \(O(1)\) ずつ生成できます。

  ソースコード

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

vector<int> getBasis(const vector<int>& v){
    int b[21] = {0};
    for(int x : v){
        for(int i = 20; i >= 0; i--){
            if(!((x >> i) & 1)) continue;
            if(!b[i]){ b[i] = x; break; }
            x ^= b[i];
        }
    }
    vector<int> res;
    for(int i = 0; i <= 20; i++) if(b[i]) res.push_back(b[i]);
    return res;
}

int main(){
    int N; 
    long long S;
    scanf("%d %lld", &N, &S);
    vector<int> A(N), B(N);
    for(int i = 0; i < N; i++) scanf("%d", &A[i]);
    for(int i = 0; i < N; i++) scanf("%d", &B[i]);
    
    vector<int> bsA = getBasis(A);
    vector<int> bsB = getBasis(B);
    int r1 = (int)bsA.size();
    int r2 = (int)bsB.size();
    
    const int LIM = 1 << 20;
    static vector<char> inB;
    inB.assign(LIM, 0);
    
    // enumerate span B
    {
        int val = 0;
        inB[val] = 1;
        long long total = 1LL << r2;
        for(long long i = 1; i < total; i++){
            int pos = __builtin_ctzll(i);
            val ^= bsB[pos];
            inB[val] = 1;
        }
    }
    
    // enumerate span A
    long long count = 0;
    {
        int val = 0;
        auto check = [&](int X){
            long long Y = S - X;
            if(Y >= 0 && Y < LIM && inB[(int)Y]) count++;
        };
        check(0);
        long long total = 1LL << r1;
        for(long long i = 1; i < total; i++){
            int pos = __builtin_ctzll(i);
            val ^= bsA[pos];
            check(val);
        }
    }
    
    int power = 2 * N - r1 - r2;
    unsigned long long ans;
    if(count == 0){
        ans = 0;
    } else {
        // guaranteed answer < 2^63, so power < 64 here
        ans = (unsigned long long)count << power;
    }
    
    printf("%llu\n", ans);
    return 0;
}

---

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