Educational Codeforces Round 58 G. (Zero XOR Subset)-less
お題箱より。
問題概要
長さ の数列
が与えられる。これをいくつかの区間（連続部分列）に分割する。この分割は以下の条件を満たす必要がある。
このような分割が可能であれば最大いくつの区間に分割できるかを求めよ。不可能であれば -1 を出力せよ。
制約
解法
XOR演算を記号 で表すことにします。また「区間和」や「累積和」などの用語は、XORで計算したものを指すことにします。
区間和を考える上では先頭からの累積和を取るのが有用です。まず先頭からの累積和 を計算します。ただし
とします。
ある分割方法が本問題の条件を満たすための必要十分条件を、この累積和を用いて表現することが目標です。例えば以下の図のようにインデックス で4つの連続部分列に区切った分割を考えます。
このときそれぞれの区間和は となります。このうち1つ以上を選んでXORを取ったものが
にならないことが本問題の条件で、これはまさに線形代数における「一次独立性」です。整数を2進数表記して
の要素からなるベクトルと考え、足し算の代わりにXOR演算を用いる、いわゆる
上の線形代数と呼ばれるものを考えます。
この一次独立性は、「ある要素を、別の要素にXORで足す」という操作をしても変わりません（参考）。この性質から、 が一次独立であることは
が一次独立であることと同値です。
より一般的に言えば、インデックス で
個の区間に区切るような分割が本問題の条件を満たすことと、
が一次独立であることは同値です。すなわちこの問題は「累積和
の中から、
を必ず選び、さらに他の要素を0個以上選ぶ。それらは一次独立である必要がある。最大でいくつの要素を選べるか？」という問題に帰着できます。
これは、もし であればどのように選んでも一次独立にできないので
-1 を出力。そうでない場合は掃き出し法によって一次独立な要素の最大個数（＝それらを基底として張られる線形空間の次元数）を求めることができます。
先ほど帰着した問題に素直に従うと、 をまず基底に加えて、それから他の要素を追加していく掃き出し法によって解くことができます。ただ実際は、次元数は基底の候補をどの順番で処理するかに依存しないので好きな順番で追加して大丈夫です。
