こんにちは、Soohです。
競プロでたまに出てくる掃き出し法関連のお話でxor掃き出しというのがあります。
Gauss-Jordanをxorで書いても良いのですが、もっとお手頃な方法があると話題になりました。
コードだけを見ていてもよく分からず、どうしてこれで良いのかを説明している資料なども見当たらなかったので、解説を書くことにしました。
前提として、「xorにおける基底とは何か」を知っていることとします。
知らないよって方はこちらで勉強すると良いです。
#実装
数列 $\{A_n\}$ から xor の基底を取り出す操作です。
vector<int> base;
for(int v : A){
for(int e : base){
v = min(v, v ^ e);
}
if(v > 0) base.push_back(v);
}
はい、この時点で何が起きているか分かった天才の方はブラウザバックして頂いて結構です。
僕には少し難しかったようなので、細かく見ていくことにします。
#どうして...
ここで先に主張をしたいと思います。
上のコードにおける 6 行目時点での $v$ を $v'$と置きます。
任意の $ i $ について以下が成立する。
「$v'$ が $i$ 個目の基底として追加されたとする。この最上位 bit が $d_i$ 桁目にあった時、$(i <,)
,j$ 番目に基底として追加されるものについては $d_i$ 桁目が必ず $ 0 $ になる。」
言い換えると、以下の図のようになるということです。
これは帰納法によって証明できます。
baseのサイズが 0 の時、明らかに成立.
baseのサイズが k の時、各最上位bitが$\{d_1, d_2, ..., d_{k}\}$の順で base にあるとおく.
ただし、$ i \neq j \iff d_i \neq d_j$ とする.
今ある基底の分しか $ v \oplus e $ を取らないので、 $ 1 \le i \le k $ 回目のmin(v, v^e)が終わった時の $ v $ を $ v_i $ と書く.
また $i$ 回目の操作をする場合、取り出される基底が持つ最上位 bit は $ d_i $ であることに注意.
$v$ の最上位は $b_p $ 桁目だとする.
- $ b_p \ge min(\{d_1, ..., d_{k}\})$ の時
$i $ 回目の操作のについて
$v_{i - 1}$ の $ d_i $ 桁目に bit が立っていれば、$ v_i = v_{i - 1} \oplus e_i $
そうでなければ、 $v_i = v_{i - 1}$
従って、この操作を終えた直後は $v_i$ の $ d_i $ 桁目は $ 0 $ になっている.
帰納法の仮定から、 この後の操作に用いる基底で $ d_i $ 桁目が立っているようなものは存在しないので、$ v_k $ の $ d_i $ 桁目まで $0$ のままである.
つまり $ v_k $ では、任意の $i$ について $ d_i $ 桁目に bit が立っておらず、これが基底に追加されたとしても条件を満たす.
- $ b_p < min(\{d_1, ..., d_{k}\})$ の時
今ある基底との xor をすると、値が大きくなってしまう.
従って、xor を取った値と交換するという操作は起きえず、このまま基底となる.
明らかに、任意の$ i $ について $v_k$ の $ d_i $ 桁目には bit が立っていない.
この時、$ v_k $ は条件を満たし、$ b_p $ を最上位bit として基底に加わる.
以上から先程の主張が正しいことが分かりました。
#基底を網羅できているか？ (8/18 20:00 追記)
これは背理法によって示すことができます。
全ての $A_i$ について処理を終えた時の base を考えます。
base に入らなかった $ A_i$ のうち、ある $i$ が存在して $A_i$ が任意の $base_j$ と線形独立であると仮定します。
base に入らなかったということは、コードの 6 行目の時点で $ v = 0 $ だったことを意味するので、これは矛盾です。
#まとめ
ここまで来たらもうお分かりですよね？
基底を並び替えると、標準形と似た感じの行列になっています。
線型独立(?)なものを集めるだけだった場合には、この操作だけで十分なことが分かります。
とても綺麗なアルゴリズムですね。
皆さんも楽しい xor 掃き出し生活をお送りください！