XOR の基底　事実・できることまとめ

間違っている部分やもっと簡単にできる部分などがあれば教えていただけると助かります。

この記事での記法など

XOR 演算子は $\oplus$ で書く。
非負整数の（有限）集合 $S$ に対して全体の XOR $\displaystyle \bigoplus _ {s \in S} s$ を $\mathrm{XOR}(S)$ とも書く。
非負整数の（有限）集合 $S$ に対して $X(S) = \{ \mathrm{XOR}(S) \mid T \subseteq S \}$ （何個か選んで作れる XOR 全体の集合）と書く。
$S$ を $\mathbb{F} _ 2$ 行列とみたときの基底（XOR 基底）の $1$ つを $B(S)$ と書く。
$S$ の要素はワードサイズに収まることを仮定する。ワードサイズを $w$ と書く。

本題

[1] 作れる XOR の種類数

$|X(S)| = 2 ^ {|B(S)|}$

[2] XOR を作る方法の数

$c(x) := \# \{ T \subseteq S \mid \mathrm{XOR}(T) = x \}$ とする。

$x \notin X(S)$ のとき、 $c(x) = 0$
$x \in X(S)$ のとき、 $c(x) = 2 ^ {|S| - |B(S)|}$

つまり、作れる XOR はどれも、作る方法の数が同じである。*1

F - Limited Xor Subset

No.2672 Subset Xor Sum - yukicoder

[3] 作れる XOR のうち、ある bit が立っているものの個数

その bit が立っている要素が $S$ にない場合、明らかに $0$
そうでない場合、その bit が立っているものと立っていないものは半々である。つまり、 $\# \{ x \in X(S) \mid \mathrm{test}(x, j) = 0 \} = \# \{ x \in X(S) \mid \mathrm{test}(x, j) = 1 \}$ である（ $x$ の $j$ bit 目を $\mathrm{test}(x, j)$ と表した）。
- 理由： $B(S)$ から選ばれる要素のうち、 $j$ bit 目が立っているものの個数の偶奇で分かれる。 $j$ bit 目が立っている要素を $1$ つ固定し、それを選ぶ・選ばないを flip することで全単射が作れる。

[4] chmin で XOR 基底を求めるアルゴリズム（いわゆる noshi 基底）

xor の掃き出しすごい簡単に出来るんですね

vector<int> basis;
for(int e : a){
for(int b : basis)
chmin(e, e ^ b);
if(e)
basis.push_back(e);
}

これで数列 a の基底が basis に入る
— 熨斗袋 (@noshi91) 2019年11月30日

このアルゴリズムを実行すると、msb*2 が distinct な基底が得られる。行列の言葉でいうと、（行を降順ソートすれば）階段行列になる。 $S$ の要素 $1$ つを処理するのに $O(w)$ 時間。

[5] 作れる XOR のうち $k$ 番目に小さいもの

[4] のアルゴリズムを少し変形すると、msb が distinct なだけでなく

msb は他の要素で立っていない（すなわち、 $b_i, b_j \in B(S), b_i \neq b_j$ ならば $\mathrm{test}(b_j, \mathrm{msb}(b_i)) = 0$ ）

を満たす基底が得られる（具体的なアルゴリズムはこの節の一番下にある問題の解説を参照）。行列の言葉でいうと、（行を降順ソートすれば）簡約行列になる。基底を計算するパートの計算量は [4] と同じ。

この基底をソートする（昇順に $b_0, b_1, \ldots, b_{m-1}$ とする）。すると、各 $b_i$ を選ぶか選ばないかを $01$ で表したものが $k$ の $2$ 進表記と対応する。すなわち、 $X(S)$ の要素を昇順に $x_0, x_1, \ldots, x _ {2 ^ m - 1}$ とすると、 $\displaystyle k = \sum _ {i = 0} ^ {m-1} c_i 2 ^ i \: (c _ i \in \{ 0, 1 \})$ のとき $\displaystyle x_k = \bigoplus _ {i = 0} ^ {m-1} c_i b_i$ となる。クエリ $O(w)$ 時間。

verify に使える・より詳細な解説が書いてある：G - Partial Xor Enumeration

[6] 作れる XOR のうち $v$ 以下で最大のもの（lower_bound や upper_bound のようなもの）

単純な二分探索で自明に $O(w ^ 2)$ 時間になるが、もっと高速になる。

[5] の基底をとる。基底を降順に見ていき、「選んでも $v$ を超えないなら選ぶ」ことを繰り返す。クエリ $O(w)$ 時間。

[7] 奇数個・偶数個選んで作れる XOR

今あるどの bit よりも上の余っている bit を $1$ つ選び、全部の値で立てておく。その bit が $0$ なら偶数個、 $1$ なら奇数個選んだといえる。 $X(S)$ を昇順に並べたとき、 $[0, 2 ^ {|B(S)|-1})$ 番目はこの bit が $0$ に、 $[2 ^ {|B(S)|-1}, 2 ^ {|B(S)|})$ 番目はこの bit が $1$ になる（[3] の事実も参照）。
$X _ {\mathrm{ev}}(S) := \{ \mathrm{XOR}(T) \mid T \subseteq S, |T| \equiv 0 \pmod 2\}$ （偶数個選んで作れる XOR の集合）と書く。 $S = \{ s _ i \} _ {0 \leq i \lt n}$ に対して $S' := \{ s _ 0 \oplus s _ i \} _ {1 \leq i \lt n}$ とすると、 $X(S') = X _ {\mathrm{ev}}(S)$ となる。

No.803 Very Limited Xor Subset - yukicoder

ARC のネタバレ注意

E - Rearrange and Adjacent XOR

[8] 作れる XOR のうち、 $x$ との XOR が $k$ 番目に小さいもの

今あるどの bit よりも上の余っている bit を $1$ つ選び、 $x$ のその bit を立てたものを $x'$ とする。 $S' := S \cup \{ x'\}$ を考えると、 $X(S')$ のうち先程新たに立てた bit が立っているもの、すなわち昇順で $[2 ^ {|B(S')|-1}, 2 ^ {|B(S')|})$ 番目のものが対応物（[3] の事実も参照）。
最大だけなら、後で扱う問題の解説に書いてある方法で求まる：[4] または [5] の基底を降順に見て、 $\mathrm{chmax}(x, x \oplus b _ i)$ を繰り返す。
任意の $k$ 番目で同様のことができるかは不明。

[9] 作れる XOR のうち、 $x$ との XOR が $v$ 以下で最大のもの

[8] 1. と [6] を組み合わせるとできる。

例題

G - Xor Cards

非負整数列 $(s _ i) _ {0 \leq i \lt n}$ と $(t _ i) _ {0 \leq i \lt n}$ が与えられる。 $I \subseteq \{ 0, 1, \ldots, n-1 \}$ を $I \neq \emptyset, \displaystyle \left( \bigoplus _ {i \in I} s _ i \right) \leq v$ のもとで選べるとき、 $\displaystyle \bigoplus _ {i \in I} t _ i$ の最大値を求めよ（あるいは、そのような選び方はないと判定せよ）。 $n \leq 1000, s _ i, t _ i, v \lt 2 ^ {30}$

（記号をこの記事用に変えています）

いったん $I = \emptyset$ を許して考える。

$u _ i := s _ i \cdot 2 ^ {30} + t _ i$ 、 $U := \{ u _ i\} _ {0 \leq i \lt n}$ とすると、求めるものは

$X(U)$ の $(v + 1) \cdot 2 ^ {30}$ 未満の要素のうち下 $30$ bit が最大のもの

となる。 $(v + 1) \cdot 2 ^ {30}$ 未満となる境界を [6] の方法で求める。 $r _ 0$ 番目が $(v + 1) \cdot 2 ^ {30}$ 未満で最大であるとすると、条件を満たす選び方に対応する $2$ 進数が、区間 $[0, r _ 0 ]$ になっている。つまり、境界を求めるのに使った [5] の基底の下 $30$ bit を取り直して $( t' _ i ) _ {0 \leq i \lt |B(U)|}$ とすると、求めるものは

$I' \subseteq \{ 0, 1, \ldots, |B(U)|-1 \}$ を、対応する $2$ 進数が区間 $[0, r _ 0 ]$ にあるように選ぶときの $\displaystyle \bigoplus _ {i \in I'} t' _ i$ の最大値

となる。（ここで $|B(U)| \leq 60$ であることが計算量的に効いてくる。）（ここで先程許した $I = \emptyset$ を考える。 $I = \emptyset$ 以外で条件を満たせないのは、 $r _ 0 = 0$ で、 $I' = \emptyset$ に対応する $I$ が $I = \emptyset$ の自明な $1$ 通りしかない場合。[2] より、 $n = |B(U)|$ かどうかで判定できる。）

$f(j, r, x) := ( t' _ i ) _ {0 \leq i \leq j}$ から、対応する $2$ 進数が区間 $[0, r ]$ にある選び方をしたとき、選んだ整数と $x$ の総 XOR の最大値とする。答は $f(|B(U)|-1, r _ 0, 0)$ である。 $j$ 番目を選ぶかどうかで場合分けして再帰する。

$\mathrm{test}(r, j) = 0$ のとき
- $j$ 番目を選んでしまうと $r$ より大きくなるので選べない。 $f(j-1, r, x)$ へ。
$\mathrm{test}(r, j) = 1$ のとき
- $j$ 番目を選ばないとき
  - 区間 $[0, 2 ^ j - 1 ]$ に対応。つまり $( t' _ i ) _ {0 \leq i \leq j-1}$ から好きに選んだときの選んだ整数と $x$ の総 XOR の最大値となる。これは [8] なので解ける。
- $j$ 番目を選ぶとき
  - 区間 $[2 ^ j, r ]$ に対応。つまり $t _ j$ を必ず選ぶとした上で、 $( t _ i ) _ {0 \leq i \leq j-1}$ から区間 $[0, r - 2 ^ j ]$ にある選び方をしたときの選んだ整数と $x$ の総 XOR の最大値となる。 $f(j-1, r - 2 ^ j, x \oplus t _ j)$ へ。