ICPC2025ShanghaiG.cpp

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

struct Basis {
    i64 b[60];

    void ins(i64 x) {
        for (int i = 59; i >= 0; i--) {
            if (x >> i & 1) {
                if (!b[i]) {
                    b[i] = x;
                    return;
                }
                x ^= b[i];
            }
        }
    }

    bool has(i64 x, int p) {
        for (int i = 59; i >= p; i--) {
            if (x >> i & 1) {
                if (!b[i]) {
                    return false;
                }
                x ^= b[i];
            }
        }
        return true;
    }

    void clear() {
        memset(b, 0, sizeof b);
    }
} B;

void solve() {
    int n;
    cin >> n;
    vector<i64> a(n+1);
    vector<int> cnt(60);

    B.clear();

    i64 ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = 0; j < 60; j++) {
            cnt[j] += a[i] >> j & 1;
        }
        ans ^= a[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 60; j++) {
            if (cnt[j] % 2 == 1 && (a[i] >> j & 1)) {
                a[i] ^= 1ll << j;
            }
        }
        B.ins(a[i]);
    }

    i64 ans2 = 0;
    for (int j = 59; j >= 0; j--) {
        if (B.has(ans2 ^ (1ll << j), j)) {
            ans2 ^= 1ll << j;
        }
    }

    cout << max(ans, ans2) << '\n';
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}