linalg/xor_basis_i64.cpp

• View this file on GitHub
• Last update: 2026-02-08 17:49:55+08:00

Verified with

• test/yuki_2895.test.cpp

Code

struct xor_basis {
  static constexpr int W = 64;

  using i64 = int64_t;

  int nxt = 0;
  i64 B[W] = {}, ids[W] = {};

  pair<bool, i64> insert(i64 x) {
    i64 v = 0;
    for(int i = 0; i < W; i++) {
      if (x >> i & 1) {
        if (!B[i]) {
          B[i] = x, ids[i] = v | (1ll << (nxt++));
          return pair(true, 0);
        }
        x ^= B[i], v ^= ids[i];
      }
    }
    return pair(false, v);
  }

  pair<bool, i64> query(i64 x) {
    i64 v = 0;
    for(int i = 0; i < W; i++)
      if (B[i] and (x >> i & 1))
        x ^= B[i], v ^= ids[i];
    return pair(x == 0, x == 0 ? v : 0);
  }
};

#line 1 "linalg/xor_basis_i64.cpp"
struct xor_basis {
  static constexpr int W = 64;

  using i64 = int64_t;

  int nxt = 0;
  i64 B[W] = {}, ids[W] = {};

  pair<bool, i64> insert(i64 x) {
    i64 v = 0;
    for(int i = 0; i < W; i++) {
      if (x >> i & 1) {
        if (!B[i]) {
          B[i] = x, ids[i] = v | (1ll << (nxt++));
          return pair(true, 0);
        }
        x ^= B[i], v ^= ids[i];
      }
    }
    return pair(false, v);
  }

  pair<bool, i64> query(i64 x) {
    i64 v = 0;
    for(int i = 0; i < W; i++)
      if (B[i] and (x >> i & 1))
        x ^= B[i], v ^= ids[i];
    return pair(x == 0, x == 0 ? v : 0);
  }
};

Back to top page