「各グループのメンバーの部分集合 \(2^N\) 通りについての、選ばれたメンバーのスキル値の XOR の分布は？」を高速に求めることができれば十分です。

ベクトル空間の基底の性質

\(A_i\) を \(\mathbb{F}_2\) の 20 次元ベクトル空間の元とみなすことにします。すると、線形代数に関する一般的な議論から、次が成り立つことがわかります。

• 非負整数列 \((A_1,\dots,A_N)\) に対して、ある非負整数の集合 \(\{A'_1, \dots,A'_K\}\) であって、次を共に満たすものが存在する
  • \(\{A'_1,\dots,A'_K\}\) の空でないどの部分集合も、XOR が \(0\) にならない
  • \(\{A'_1,\dots,A'_K\}\) の部分集合であって XOR が \(X\) になるものが存在する \(\Longleftrightarrow\) \((A_1,\dots,A_N)\) の部分集合であって XOR が \(X\) になるものが存在する

この条件を満たす \(\{A'_1, \dots,A'_K\}\) を \((A_1,\dots,A_N)\) の (\(\mathbb{F}_2\) ベクトル空間での) 基底といいます。基底の大きさ \(K\) は基底の取り方に依存せず \((A_1,\dots,A_N)\) のみから一意に定まります。また、\(K\) はベクトル空間の次数以下になります。

さらにこのとき、次が成り立ちます。

\(f(X)\) を、\((A_1,\dots,A_N)\) の部分集合で、 XOR の値が \(X\) となるものの個数とし、\(\{A'_1, \dots,A'_K\}\) を \((A_1,\dots,A_N)\) の基底とする。このとき、

\(f(X)=\begin{cases} 2^{N-K} & \{A'_1, \dots,A'_K\} \text{の部分集合で、XORが } X \text{になるものが存在する場合}\\ 0 & そうでない場合\\ \end{cases}\)

となります。

基底の計算

ベクトル列が与えられたとき、基底は一般に掃き出し法(wikipedia)により求めることができます。特に \(\mathbb{F}_2\) ベクトル空間の場合は、ベクトルを整数として持つことで、掃き出し法の各ステップの計算をビット演算で行うことができます。

問題の解法

\(A_i,B_i\) の最大 bit 数を \(L\) とします。

• 掃き出し法により基底を求める
  • \(O(NL)\) 時間
• 基底を元に、作ることができる XOR の値全てを愚直に計算する
  • \(O(2^L)\) 時間
• \(A\) の XOR として作ることができる各値 \(X\) について、\(S-X\) が \(B\) の XOR として作ることができるか判定する
  • \(O(L2^L)\) 時間または hash setにより expected \(O(2^L)\) 時間

実装例 (C++)

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

vector<int> make_basis(vector<int> A){
  vector<int> e(20);
  for(int a: A){
    for(int i=0; i<20; i++){
      if((a>>i)&1){
        a ^= e[i];
      }
    }
    if(a){
      int k = 32 - __builtin_clz(a) -1;
      for(int i=0; i<20; i++){
        if((e[i]>>k)&1){
          e[i] ^= a;
        }
      }
      e[k] = a;
    }
  }

  vector<int> basis;
  for(int x: e){
    if(x){
      basis.push_back(x);
    }
  }
  return basis;
}

int main(){
  int n, s;
  cin >> n >> s;
  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];

  vector<int> AA({0});
  for(int a: make_basis(A)){
    int n = AA.size();
    for(int i=0; i<n; i++){
      AA.push_back(AA[i]^a);
    }
  }
  vector<int> BB({0});
  for(int b: make_basis(B)){
    int n = BB.size();
    for(int i=0; i<n; i++){
      BB.push_back(BB[i]^b);
    }
  }
  unordered_set<int>BBset(BB.begin(),BB.end());

  int ans = 0;
  for(int a: AA){
    if(BBset.contains(s-a)){
      ans++;
    }
  }

  cout << ans * ((1LL<<n)/AA.size()) * ((1LL<<n)/BB.size()) << endl;
}

実装例 (Python)

def make_basis(A):
  e = [0] * 20
  for a in A:
    for i, v in enumerate(e):
      if (a>>i)&1:
        a ^= v
    if a:
      k = a.bit_length()-1
      for i in range(20):
        if (e[i]>>k)&1:
          e[i] ^= a
      e[k] = a
  return [x for x in e if x]

N, S = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

AA = [0]
for a in make_basis(A):
  AA.extend([x^a for x in AA])
BB = set([0])
for b in make_basis(B):
  BB.update([x^b for x in BB])

ans = 0
for a in AA:
  if S-a in BB:
    ans += 1

print(ans * (2**N//len(AA)) * (2**N//len(BB)))