CP-templates

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub Misuki743/CP-templates

:heavy_check_mark: linalg/xorBasis.cpp

Verified with

Code

// note: querying whether x can be represented as linear combination of some
//       vector with label >= lb

template<int size>
struct xorBasis {
  bitset<size> *basis[size] = {};
  int mxIdx[size] = {};
  void insert(bitset<size> x, int idx) {
    for(int i = 0; i < size; i++) {
      if (x[i]) {
        if (!basis[i]) {
          basis[i] = new bitset<size>(x);
          mxIdx[i] = idx;
          return;
        }
        if (mxIdx[i] < idx) {
          swap(*basis[i], x);
          swap(mxIdx[i], idx);
        }
        x ^= *basis[i];
      }
    }
  }
  bool query(bitset<size> x, int lb = -1) {
    int mn = INT_MAX;
    for(int i = 0; i < size; i++)
      if (basis[i] and x[i])
        x ^= *basis[i], mn = min(mn, mxIdx[i]);
    return x.none() and mn >= lb;
  }
  ~xorBasis() {
    for(int i = 0; i < size; i++)
      if (basis[i])
        delete basis[i];
  }
};
#line 1 "linalg/xorBasis.cpp"
// note: querying whether x can be represented as linear combination of some
//       vector with label >= lb

template<int size>
struct xorBasis {
  bitset<size> *basis[size] = {};
  int mxIdx[size] = {};
  void insert(bitset<size> x, int idx) {
    for(int i = 0; i < size; i++) {
      if (x[i]) {
        if (!basis[i]) {
          basis[i] = new bitset<size>(x);
          mxIdx[i] = idx;
          return;
        }
        if (mxIdx[i] < idx) {
          swap(*basis[i], x);
          swap(mxIdx[i], idx);
        }
        x ^= *basis[i];
      }
    }
  }
  bool query(bitset<size> x, int lb = -1) {
    int mn = INT_MAX;
    for(int i = 0; i < size; i++)
      if (basis[i] and x[i])
        x ^= *basis[i], mn = min(mn, mxIdx[i]);
    return x.none() and mn >= lb;
  }
  ~xorBasis() {
    for(int i = 0; i < size; i++)
      if (basis[i])
        delete basis[i];
  }
};
Back to top page