非負整数 \(x\) を二進法表記した際の 1 の数を \(\mathrm{popcount}(x)\) で表します。また、 \(A\) の要素の最大bit長を \(M\) とします。

最後に残る値の条件+最大値の求め方

\(i=1,2,\dots,N\) に対して \(A_i=2^{i-1}\) のとき、最後に残る値 \(last\) としてありうる値を考察すれば十分です。

まず \(1\) 回操作すると \(A\) の要素の \(\mathrm{popcount}(A_i)\) は偶数になり、\(\mathrm{popcount}\) が偶数である整数同士の\(\mathrm{XOR}\) の \(\mathrm{popcount}\) は偶数であるため、以降どのように操作しても \(A\) の要素の \(\mathrm{popcount}\) は偶数です。とくに \(\mathrm{popcount}(last)\) は偶数になります。

さて、では \(\mathrm{popcount}\) が偶数である整数はすべて \(last\) としてありうるでしょうか？ 結論から述べると

• \(N=2\) または \(N \bmod 4 \neq 2\) のとき、\(last\) としてありうる値は \(2^N\) 未満の非負整数のうち、 \(\mathrm{popcount}(last)\) が偶数であるものから \(0\) をのぞいたものですべてである
• \(N\neq 2\) かつ \(N \bmod 4 = 2\) のとき、\(last\) としてありうる値は \(2^N\) 未満の非負整数のうち、 \(\mathrm{popcount}(last)\) が偶数であるものから \(0, 2^N-1\) を除いたものですべてある

が成り立ちます。

これが成り立つことを認めたうえで、最後に残る値の最大値の求め方を考えます。まず \(1\) 番目のケースについては \(A_i\) のうち偶数個の \(\mathrm{XOR}\) で表せるという条件だけ考えればよく、これは \(A_1 \oplus A_2, A_1 \oplus A_3,\ \dots, A_1 \oplus A_N\) の\(\mathrm{XOR}\) で表せることと同値であるため、掃き出し法により基底を求めた後、上の桁から貪欲に最大化すればいいです。

\(2\) 番目のケースについてはまず \(A_1 \oplus A_i\) が一次独立でない場合は \(A_1 \oplus A_i\) の\(\mathrm{XOR}\) で表せる最大の整数は \(A_1 \oplus A_i\) をすべて用いなくても表せるため、上記のケースと同じ求め方でいいです。

\(A_1 \oplus A_i\) が一次独立である場合はまず\(A_1 \oplus A_i\) の\(\mathrm{XOR}\) で表せる最大の整数をもとめ、これが \(A_i\) すべての \(\mathrm{XOR}\) になっているかを確認します。すべての \(\mathrm{XOR}\) になっている場合は例えば\(\mathrm{XOR}\) に用いないものを全探索して改めて計算すればいいです。

以上より\(\mathrm{XOR}\) に用いないものを全探索する場合でも \(O(N^2M)\) 時間で最大値を計算することができます。

上記の事実の証明

\(N=2\) のときは明らかです。続けて \(n\) 未満の\(N\) に対して成り立つと仮定して \(N=n\) のとき成り立つことを示します。\(A\) の要素はいつでも並び替えられることを考えると \(2^{2k}-1\ (k=1,2,\dots)\) だけ考えれば十分です。

まず \(k\) が偶数の場合ですが、この場合は \(A\) を並び替えずに操作を行えば \(A=(2^0+2^1,2^1+2^2,\dots,2^{N-2}+2^{N-1})\) となり、最後に残る値を \(A_1,A_3,\dots,A_{2k-1}\) の \(k\) 個の \(\mathrm{XOR}\) にできるかが問題です。これは \(2 \leq k\) であるため、\(k \neq N-1\) であること、 \(k\) が偶数であることから、帰納法の仮定より可能であることが分かります。

次に \(k\) が奇数の場合ですが、この場合 \(2k < N\) であるため、 \(A\) の先頭 \(2k+1\) 項を \(2^0,2^1,\dots,2^{2k-2},2^{N-1},2^{2k-1}\) とすると、操作後の \(A\) においては 最後に残る値を \(A_1,A_3,\dots,A_{2k+1}\) の \(k+1\) 個の \(\mathrm{XOR}\) にできるかが問題です。これは \(k+1\) が偶数であることと、 \(A_2\) など選ばない要素が存在することから可能です。

以上より示されました。