Let \(\mathrm{popcount}(x)\) denote the number of 1s in the binary representation of a non-negative integer \(x\). Also, let \(M\) be the maximum bit length of the elements in \(A\).

Condition for the last remaining value, and how to find the maximum Value

It is sufficient to consider the possible values for the last remaining value \(last\) when \(A_i=2^{i-1}\) for \(i=1,2,\dots,N\).

First, after one operation, the \(\mathrm{popcount}(A_i)\) of each element in \(A\) will be even. Since the \(\mathrm{XOR}\) of two integers with even \(\mathrm{popcount}\) has an even \(\mathrm{popcount}\), the \(\mathrm{popcount}\) of the elements in \(A\) remains even no matter how the subsequent operations are performed. In particular, \(\mathrm{popcount}(last)\) is even.

Now, can all integers with even \(\mathrm{popcount}\) be \(last\)? The conclusion is:

• When \(N=2\) or \(N \bmod 4 \neq 2\), \(last\) can only be non-negative integers less than \(2^N\) with even \(\mathrm{popcount}\) except \(0\).
• When \(N\neq 2\) and \(N \bmod 4 = 2\), \(last\) can only be non-negative integers less than \(2^N\) with even \(\mathrm{popcount}\) except \(0\) and \(2^N-1\).

Assuming this holds, let’s consider how to find the maximum value for the last remaining value. For the first case, we only need to consider the condition that it can be represented by the \(\mathrm{XOR}\) of an even number of \(A_i\)’s. This is equivalent to being representable as the \(\mathrm{XOR}\) of \(A_1 \oplus A_2, A_1 \oplus A_3,\ \dots, A_1 \oplus A_N\). Therefore, we can find a basis using Gaussian elimination and greedily maximize the value from the higher bits.

For the second case, if \(A_1 \oplus A_i\) are not linearly independent, the maximum integer representable as the \(\mathrm{XOR}\) of \(A_1 \oplus A_i\) can be represented without using all of them, so we can find it in the same way as the above case.

If \(A_1 \oplus A_i\) are linearly independent, we first find the maximum integer representable by the \(\mathrm{XOR}\) as \(A_1 \oplus A_i\) and check if it is the \(\mathrm{XOR}\) of all \(A_i\). If it is, we can, for example, try again by brute-forcing the one not used in the \(\mathrm{XOR}\).

Thus, the maximum value can be calculated in \(O(N^2M)\) time, even when brute-forcing the one not used in the \(\mathrm{XOR}\).

Proof of the above facts

The case \(N=2\) is clear. Next, assuming it holds for \(N\) less than \(n\), we will show that it holds for \(N=n\). Considering that the elements of \(A\) can always be rearranged, it is sufficient to consider only \(2^{2k}-1\ (k=1,2,\dots)\).

First, when \(k\) is even, if we perform the operations without rearranging \(A\), we will have \(A=(2^0+2^1,2^1+2^2,\dots,2^{N-2}+2^{N-1})\). The problem is whether the last remaining value can be the \(\mathrm{XOR}\) of the \(k\) elements \(A_1,A_3,\dots,A_{2k-1}\). Since \(2 \leq k\), from \(k \neq N-1\) and the evenness of \(k\), we can see that the induction hypothesis makes it possible.

Next, when \(k\) is odd, since \(2k < N\), if we let \(2^0,2^1,\dots,2^{2k-2},2^{N-1},2^{2k-1}\) be the first \(2k+1\) terms of \(A\), the problem is whether the last remaining value can be the \(\mathrm{XOR}\) of the \(k+1\) elements \(A_1,A_3,\dots,A_{2k+1}\) in the \(A\) after the operation. This is possible because \(k+1\) is even and some elements like \(A_2\) are not chosen.

Therefore, the claim is proved.