linalg/xor_basis_bitset.cpp

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

Verified with

• test/matrix_rank_mod_2.test.cpp
• test/yuki_2895_2.test.cpp

Code

template<int W>
struct xor_basis {
  int nxt = 0;
  bitset<W> *B[W] = {}, *ids[W] = {};

  pair<bool, bitset<W>> insert(bitset<W> x) {
    bitset<W> v = {};
    for(int i = 0; i < W; i++) {
      if (x[i]) {
        if (!B[i]) {
          v[nxt++] = true;
          B[i] = new bitset<W>(x);
          ids[i] = new bitset<W>(v);
          return pair(true, bitset<W>(0));
        }
        x ^= *B[i], v ^= *ids[i];
      }
    }
    return pair(false, v);
  }

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

#line 1 "linalg/xor_basis_bitset.cpp"
template<int W>
struct xor_basis {
  int nxt = 0;
  bitset<W> *B[W] = {}, *ids[W] = {};

  pair<bool, bitset<W>> insert(bitset<W> x) {
    bitset<W> v = {};
    for(int i = 0; i < W; i++) {
      if (x[i]) {
        if (!B[i]) {
          v[nxt++] = true;
          B[i] = new bitset<W>(x);
          ids[i] = new bitset<W>(v);
          return pair(true, bitset<W>(0));
        }
        x ^= *B[i], v ^= *ids[i];
      }
    }
    return pair(false, v);
  }

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

Back to top page