不妨考虑最后的结果可以成为哪些 \(a_i\) 的组合。为了方便分析，我们令 \(a_i = 2^{i - 1}\)。
进行一次操作后，所有 \(\text{popcount}(a_i)\) 都为偶数。所以一个 \(x \in [0, 2^n - 1]\) 能被生成出来的必要条件是 \(\text{popcount}(x)\) 为偶数。
然后通过打表可以发现：
- 对于 \(n = 2\) 或 \(n \bmod 4 \ne 2\)，任意一个 \(x \in [1, 2^n - 1]\) 且 \(\text{popcount}(x)\) 为偶数的 \(x\) 都能被生成出来。
- 对于 \(n \ne 2\) 且 \(n \bmod 4 = 2\)，任意一个 \(x \in [1, 2^n - 2]\) 且 \(\text{popcount}(x)\) 为偶数的 \(x\) 都能被生成出来。
考虑归纳证明。因为 \(a\) 中元素可以重排，所以不妨只考虑 \(2^{2k} - 1\)（\(k \ge 1\)）能否被生成出来：
- \(k\) 为偶数，做一次操作后序列变成 \(a = [2^0 + 2^1, 2^1 + 2^2, \ldots, 2^{n - 2} + 2^{n - 1}]\)。因为 \(k\) 为偶数，所以最后剩下的值可以为 \(a_1 \oplus a_3 \oplus \cdots \oplus a_{2k - 1}\)，所以成立。
- \(k\) 为奇数，不妨让一开始的 \(a\) 的前 \(k + 1\) 个元素为 \(2^0, 2^1, \ldots, 2^{2k - 2}, 2^{n - 1}, 2^{2k - 1}\)（要求 \(2k < n\)）。做一次操作后，因为 \(k + 1\) 为偶数且当 \(n - 1 > 2\) 时 \(k + 1 \ne n - 1\)，所以最后剩下的值可以是 \(a_1 \oplus a_3 \oplus \cdots \oplus a_{2k - 1} \oplus a_{2k}\)，所以成立。
于是现在问题变成了：选一个 \(a\) 中的包含偶数个元素的子集，最大化异或和，同时还可能有不能选全集的限制。
对于没有限制的情况，发现 \(a\) 中的任意一个包含偶数个元素的子集的异或和都可以表示成 \(a_1 \oplus a_2, a_1 \oplus a_3, \ldots, a_1 \oplus a_n\) 的一个子集的异或和。所以直接把这些数塞进一个线性基，然后查询即可。
对于有限制的情况，我们不妨钦定一个数不被选，删掉这个数，就转化成了没有限制的情况。
时间复杂度 \(O(n^2 \log V)\)。
code
// Problem: E - Rearrange and Adjacent XOR
// Contest: AtCoder - AtCoder Regular Contest 173
// URL: https://atcoder.jp/contests/arc173/tasks/arc173_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 110;
ll n, a[maxn];
struct Basis {
ll p[64];
inline void init() {
mems(p, 0);
}
inline void insert(ll x) {
for (int i = 59; ~i; --i) {
if (x & (1LL << i)) {
if (!p[i]) {
p[i] = x;
return;
}
x ^= p[i];
}
}
}
inline ll query() {
ll ans = 0;
for (int i = 59; ~i; --i) {
ans = max(ans, ans ^ p[i]);
}
return ans;
}
} B;
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
if (n == 2 || n % 4 != 2) {
for (int i = 2; i <= n; ++i) {
B.insert(a[1] ^ a[i]);
}
printf("%lld\n", B.query());
} else {
ll ans = 0;
for (int i = 2; i <= n; ++i) {
B.init();
for (int j = 2; j <= n; ++j) {
if (i == j) {
continue;
}
B.insert(a[1] ^ a[j]);
}
ans = max(ans, B.query());
}
printf("%lld\n", ans);
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}