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

執筆のきっかけ

最近のAtcoder 407のD問題でXORの基礎的な知識と計算方法がわからなかったため、
久々のPerf爆伸びチャンスを逃してしまいました

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

XORBasisは？

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

list = [a1, a2, a3, ...., an]

のような数列リストがあるとしましょう。

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

例えば、

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番目のアイデアです

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

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

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

例

lst = [1, 3, 5, 7, 9]
basis = [] # 基底を保存するlist

上述したBasisの基底を求めるコードは

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

    if now:
        basis.append(now)

このようになります

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

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

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

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

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

例えば、

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

XORMaximum

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

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

計算は簡単で

ans = 0

for i in sorted(basis, reverse= True):
    ans = max(ans, ans ^ i)

これで終わりです！！

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

疑問

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

例えば、

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

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に慣れたい！と気軽く始めましたが、数字を二進化させ、それをベクトルとして考える思考の流れが驚きでした

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

みんなさんよかったら復習としてこの問題に挑戦してみましょう！