pekempey's blog

998244853

ABC141 F Xor Sum 3

https://atcoder.jp/contests/abc141/tasks/abc141_f

If the number of ones on i-th bit is odd, 2^i is always added to the answer no matter how we classified them. Therefore, we can use an usual approach for finding lexicographically maximum. We can determine whether some bit can become one or not by using system of linear equations. We may solve this equation 60 times at worst, but which is fast enough.

If you are familiar with linear algebra, you can find more elegant solution, which written in the editorial. The following code is based on the editorial.

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()

using namespace std;
using ll = long long;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N; cin >> N;
  vector<ll> A(N); rep(i, N) cin >> A[i];
  ll ans = 0;
  rep(i, 60) {
    int s = 0;
    rep(j, N) s ^= A[j] >> i & 1;
    if (s == 1) {
      ans += 1LL << i;
      rep(j, N) A[j] &= ~(1LL << i);
    }
  }
  vector<ll> bases;
  sort(range(A), greater<>());
  for (ll x : A) {
    for (ll y : bases) x = min(x, x ^ y);
    if (x != 0) bases.push_back(x);
  }
  ll s = 0;
  for (ll x : bases) s = max(s, s ^ x);
  cout << ans + s * 2 << endl;
}