前提
- 線形独立、線形従属を理解していること
線形空間、基底、行列のrankについて知ってるとなお良いです。
本記事ではxor基底についてコスパよく理解させることが目標です。
もっと厳密に学びたい方はこちらなど。
問題
この問題に沿ってxor基底を学びます。
数列Aの要素を組み合わせてXORを計算し、できあがるものを集合にします。集合で小さい順にL番目からR番目まで列挙するという問題です。
解法の方針とXOR基底
L, Rについてはこういう問題にありがちな上のビットから順番に考える二分探索を使いますが、本記事では述べないことにします。
実は、できあがる集合のサイズは2のべき乗となります。これは少し非自明かもしれません。
少し例を見てみます。
a, b, c, dという要素がAの中にあったとします。いったん重複や順番を考慮しないまま列挙すると、0, a, b, c, d, a xor b, b xor c, c xor d, d xor a, a xor b xor c, a xor b xor d, a xor c xor d, b xor c xor d, a xor b xor c xor dの16種類です。
d=b xor cのときを考えてみましょう。例えば、a xor dはa xor b xor cで表せますし、a xor b xor dは、d=b xor c→c=b xor dから、a xor cと表せます。このように、d (b, c, dのうちどれか1つ)は数列中にないのと同じと考えることができます。
線形代数とXOR基底
線形独立・線形従属を思い出してみましょう。d=b xor c、a=b xor c xor d、b=cなどのように、数列中の値が他の値のxorだけで表現できてしまうとき、線形従属であると言えます(たぶん)
同様に、ある空間の基底は、それぞれが空間の別の基底で表せないものです。3次元空間だと、(0, 0, 1), (0, 1, 0)の実数倍の和で(1, 0, 0)で表せないですよね。
a, b, cが基底であるとします。このとき、a xor b, b, cを基底にするとかしても問題ないです。xorの組み合わせでできあがる集合は変わりません。集合の各要素の表し方は複数存在せず、基底が決まればただ1つ存在します。私は、ベクトルA, B, Cが線形独立であって、A+B, B, CだとかA, B, C-B-Aを基底にしてよいことは、行列式だとかrankを求めるときの行基本変形と同じだと思っています。ただし、A+B, -A-B, Cとかは基底にできません、1個ずつ実数倍の加減算(本問題だとxor)の計算をしてできあがるものならば良いと考えられます。
集合の各要素の表し方は複数存在せず、という部分について、複数存在する、つまり重複があると、その分集合のサイズは減ります。しかし、重複がないことで、とりあえず重複を考慮せず列挙してみた2の(基底の個数)乗個の要素は小さい順に並び替えるだけでそのまま集合として成立します。
XOR基底の実装方針
実装するとき、基底はrankを求める操作のような形(上三角行列？)で表します 基底として、11010, 01101, 00011のようにすると、上のビットから考えて、xorするかどうかを考えることができます。基底ごとに、xorするかどうかとなり、2の3乗であることがわかります。
