XOR-Basis

Implementation

XOR Basis

// XOR Basis {{{
struct Basis {
  vector<int> B;
  int reduce(int x) {
    for (auto b : B) x = min(x, x^b);
    return x;
  }
  void insert(int x) {
    int r = reduce(x);
    if (r) B.push_back(r);
  }
};
//}}}

Explanation

On USACO Guide you can find a great presentation by Benq, as well as various problems.