「図解解説」XORBasisとXor Maximization

※ 本記事は、XOR Basis を初めて知った方向けに、筆者自身が理解した流れをもとに整理したメモです。なるべく分かりやすく書いたつもりですが、もし分かりにくい箇所があればコメントいただけると嬉しいです！
## 執筆のきっかけ

最近のAtcoder 407の[D問題](https://atcoder.jp/contests/abc407/tasks/abc407_d)でXORの基礎的な知識と計算方法がわからなかったため、
久々のPerf爆伸びチャンスを逃してしまいました

それが悔しすぎて、韓国のオンラインジャッジサイトでXORに関するアルゴリズムを調べてる中、XORBasisの`数字を二進化し、その二進化した数字をベクトルとして扱う`アイデアが印象的かつ日本語で解説する記事がなかったため、（ただ見落とした可能性もあるが）記事を執筆することになりました！

## XORBasisは？

まず、XorBasisを使う問題の例から始めます

```python
list = [a1, a2, a3, ...., an]
```
のような数列リストがあるとしましょう。

このリストで作れる部分集合は`(2 ^ n) - 1`通りあります！（空集合は含まない）
その部分集合の要素間のXOR結果の中、MAX値を探す問題です！

例えば、
```python
list = [1, 2]
max(1, 2, 1 XOR 2) = 3

list = [1, 2, 3]
max(1, 2, 3, 1 XOR 2, 1 XOR 3, 2 XOR 3, 1 XOR 2 XOR 3) = 3
```
のように答えを求めることが可能ですが、部分集合が`(2 ^ n) - 1`通りなので
探索必要な集合だけでもうO(2 ^ n)、、、、計算量がやばいです

ここで、二進数は0101101010....のように数字`n`を`floor(log n) + 1`個の数字列で表現することが可能です！

この数字列を`floor(log n) + 1`次元のベクトルとして扱うのか1番目のアイデアです

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3911207/8b44c261-3cf1-4405-a1fc-1efedea38b7f.png)

このアイデアから、`XORを最大にする問題`を`ベクトルのXOR結合で作れるベクトル中で最大値を求める問題`に変更できます

次は、入力されたベクトルの基底(basis)を求めます。
問題の目的が`ベクトルのXOR結合で作れるベクトル中で最大値を求める問題`であるため、一次独立な基底のベクトルのみを保存して、ベクトルの最大値を求める際に使います

ここで、説明が曖昧でよくわからない！と思う人がいっぱいいると考えるので、例を挙げて説明します。

## 例

```python
lst = [1, 3, 5, 7, 9]
basis = [] # 基底を保存するlist
```
上述したBasisの基底を求めるコードは

```python
for i in range(lst):
	now = lst[i]
    for bas in basis:
        now = min(now ^ bas, now)

    if now:
        basis.append(now)
```
このようになります

これだけでは理解しづらいと考えるのでコードの仕組みを解説します！

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3911207/ab3b52d3-e933-453e-bdf6-65284c84ee0b.png)

このように`basis`が埋まったいきます！

この操作を線形代数的な観点から見ると

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3911207/79e4f0d0-0079-449b-be92-3194b26c0b50.png)


このように基底化します！

これを見て「あ！ガウスの消去法と同じ！」だと思うかもしれませんが、それとはちょっと違います

例えば、

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3911207/6b8cb51f-53d9-4abd-a1ff-9ca15c025428.png)


このように、ガウス消去法とはちょっと違う結果が得られますので注意してください。

## XORMaximum

これで二進数をベクトルとして扱って、XOR計算に独立な基底ベクトルを求めました！

それでは、これをどう用いたら`XORMaximum`を求めるのかについて解説します！！

計算は簡単で

```python
ans = 0

for i in sorted(basis, reverse= True):
    ans = max(ans, ans ^ i)
```
これで終わりです！！

XORの結果は大きい数字からきめられるので、大きい要素から最大値を更新する`貪欲法`が正当になります。

## 疑問

ここで、ちょっと疑問がありました

例えば、

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3911207/6364a2cc-bb82-4b91-9a45-a16ef3272101.png)


この場合、[1, 2, 4, 8]という基底ベクトルが生成されまして、XORmaximumの計算は

```python
ans = 0

for i in sorted(basis, reverse= True):
    ans = max(ans, ans ^ i)
'''
i = 0, ans = max(0, 0 ^ 8) => 8
i = 1, ans = max(8, 8 ^ 4) => 12
i = 2, ans = max(12, 12 ^ 2) => 14
i = 3, ans = max(14, 14 ^ 1) => 15

よって最大値 = 15
となるが、

basis = [1, 2, 4, 8]は
lst = [1, 3, 5, 7, 9] = [a1, a2, a3, a4, a5]から見ると

basis = [a1, a1 XOR a2, a1 XOR a3, a1 XOR a5]になるから

ans = a1 XOR (a1 XOR a2) XOR (a1 XOR a3) XOR (a1 XOR a5)になるけど、、、

これだったら部分数列にならなくねぇ？

例えば、この結果では
数列[a1, a1, a2, a1, a3, a1, a5]のXOR和になってしまうから
lst = [a1, a2, a3, a4, a5]の部分集合にはならない！！
'''
```
という疑問がありました

## 疑問解決

上の疑問はXORの特徴を考えると解決できます！

まずXORは`a XOR a = 0`と`a XOR b XOR c = (a XOR c) XOR b`２つの特徴があります

よって、上の例だったら`数列[a1, a1, a2, a1, a3, a1, a5]`のXOR結果は

`a1 XOR a1 XOR a2 XOR a1 XOR a3 XOR a1 XOR a5`  =>

`(a1 XOR a1) XOR (a1 XOR a1) XOR a2 XOR a3 XOR a5` =>

`a2 XOR a3 XOR a5`

となるので結局部分集合になります！

よって、基底の計算結果で同じ要素が複数出ても問題ないです！！

## 感想

最初はただXORSumに慣れたい！と気軽く始めましたが、数字を二進化させ、それをベクトルとして考える思考の流れが驚きでした

やっぱり、アルゴリズムの勉って自分が思ったこともない考え方を学べることができて、すごく楽しいと考えました！

みんなさんよかったら復習として[この問題](https://www.acmicpc.net/problem/11191)に挑戦してみましょう！