Xét thao tác đổi chỗ ~2~ số ~a_i~ và ~b_i~, ta thấy ~f(a)~ sẽ trở thành ~f(a) \oplus a_i \oplus b_i~, còn ~f(b)~ trở thành ~f(b) \oplus a_i \oplus b_i~. Nói cách khác, ~f(a)~ và ~f(b)~ sẽ được ~\text{xor}~ với cùng một số.

Xét ~f(a)~ và ~f(b)~ theo thứ tự bit giảm dần, ta thấy, nếu bit thứ ~i~ của ~f(a)~ và ~f(b)~ khác nhau, thì sau khi thực hiện các thao tác đổi chỗ, hai bit này vẫn sẽ khác nhau.

Ngược lại, nếu bit thứ ~i~ của ~f(a)~ và ~f(b)~ giống nhau, để ~f(a) + f(b)~ đạt giá trị nhỏ nhất, ta sẽ muốn bit thứ ~i~ của ~f(a)~ và ~f(b)~ cùng bằng ~0~. Ta sẽ kiểm tra điều kiện này bằng khử Gauss.

Code mẫu:

Code mẫu

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

const int N = 2e5 + 1;

bool gauss(vector<bitset<N>> a, int m) {
  int k = a.size();
  for (int c = 0, r = 0; c < m && r < k; ++c) {
    for (int i = r; i < k; ++i) {
      if (a[i][c]) {
        swap(a[r], a[i]);
        break;
      }
    }
    if (!a[r][c]) {
      continue;
    }
    for (int i = 0; i < k; ++i) {
      if (i != r && a[i][c]) {
        a[i] ^= a[r];
      }
    }
    ++r;
  }

  for (int i = 0; i < k; ++i) {
    if (a[i][m]) {
      a[i][m] = 0;
      if (a[i].none()) {
        return 0;
      }
    }
  }

  return 1;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  long long xa = 0, xb = 0;
  vector<long long> a(n), b(n);
  for (long long &v : a) {
    cin >> v;
    xa ^= v;
  }
  for (long long &v : b) {
    cin >> v;
    xb ^= v;
  }
  for (int i = 0; i < n; ++i) {
    a[i] ^= b[i];
  }

  long long ans = 0;
  vector<bitset<N>> t;
  for (int i = 61; i >= 0; --i) {
    int fa = (xa >> i) & 1, fb = (xb >> i) & 1;
    if (fa != fb) {
      ans += 1ll << i;
      continue;
    }
    bitset<N> bs;
    for (int j = 0; j < n; ++j) {
      bs[j] = (a[j] >> i) & 1;
    }
    bs[n] = fa;
    t.push_back(bs);
    if (!gauss(t, n)) {
      ans += 1ll << (i + 1);
      t.back()[n].flip();
    }
  }

  cout << ans;
}