適当な整数 \(k\) に対し、答えを \(2^k\) 未満に抑えることができるかどうか考えます。

これは、入力された \(A_i\) の下位 \(k\) bit を取り除いて得られる数の次元 (=XOR を可算と見たときのベクトル空間の次元) が \(2\) 以下か否かを見ればよいです。

これで、答えの値の最上位 bit が求まります。 これを \(2^t\) の位とします。 （答えが \(0\) になるケースはすぐに分かるので省いています）

下位 \(t+1\) bit を取り除いた数の集合は、\(0\) 以外の数を \(2\) つ以上含みます。 これは背理法でわかります。 \(1\) つ以下だった場合、答えを \(2^t\) 未満に抑えることができます（考える bit を \(1\) つ増やしても次元は高々 \(1\) しか増えないため）。これは \(t\) の取り方に矛盾します。

下位 \(t+1\) bit を取り除いた数の集合に入る \(0\) 以外の数が、\((X,Y)\) あるいは \((X,Y,X \oplus Y)\) だとします。 ここで、前者も後者の特殊ケース (\(X \oplus Y\) に対応する値が \(0\) 個ある) とみなすことにします。

ここで、各 \(A_i\) について、その値のグループが分かります。 グループとは、下位 \(t+1\) bit を取り除いたあとの値が \(0,X,Y,X \oplus Y\) のどれであるかを表すものです。 ここでは便宜的に、順にグループ \(0,1,2,3\) と呼ぶことにします。

同じグループに入っている値は、下位 \({t+1}\) bit が受ける変更がすべて同じになります。 ここで、明らかにグループ \(0\) は値の変更を受けません。 またグループ \(1,2,3\) が受ける変更を \(p,q,r\) とすると、\(p \oplus q =r\) になります。 よって、\(p,q,r\) を適切に決め、最終的な \(A_i\) の最大値を最小化する問題を解けばよいです。

各 \(0 \leq p <2^t\) について、その \(p\) を使うことでグループ \(1\) 内の要素の最大値がいくつになるかを求めておきます。 これは、binary-trie を使うことで、\(O((2^t+N) t)\) 時間で計算できます。

同様に、各 \(q,r\) についても、それを使った際のグループ \(2,3\) 内の最大値を求めておきます。 あとは、\(p \oplus q =r\) の下でこれらの最大値を最小化すればよいです。 これは答えを\(2\) 分探索することで解けます。 答えの目標を決め打つと、使える \(p,q,r\) が分かるため、これらが上の等式を満たすことがあるか判定すればよいです。 XOR convolution を行うことで \(O(2^t t)\) 時間で判定できます。

以上をまとめると、この問題は \(O((2^LL+N)L)\) 時間で解けます。 ただし、\(L\) は \(\max(A_i)<2^L\) を満たす数です。

実装例