XOR Basis
(library/numerical/xor-basis.hpp)

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Include: #include "library/numerical/xor-basis.hpp"

XOR Basis

Functions

• full_reduce(b): Full Gaussian elimination on everything.
• reduce(b): Just reduces enough to work.
• add(b, x): Adds $x$ to a basis $b$.

Resources

• Benq

Verified with

• verify/codeforces/codeforces-1299D.test.cpp

Code

#pragma once

void full_reduce(std::vector<int>& b) {
	int n = (int)b.size();
	for (int i = n - 1; i >= 0; i--) {
		for (int j = i - 1; j >= 0; j--) {
			b[j] = std::min(b[j], b[j] ^ b[i]);
		}
	}
}

template <class T> T reduce(std::vector<T>& b, T x) {
	for (auto& t : b) {
		x = std::min(x, x ^ t);
	}
	return x;
}

template <class T> bool add(std::vector<T>& b, T x) {
	if (!(x = reduce(b, x))) return false;
	int ind = 0;
	while (ind < (int)b.size() && b[ind] > x) ind++;
	b.insert(b.begin() + ind, x);
	return true;
}

void full_reduce(std::vector<int>& b) {
	int n = (int)b.size();
	for (int i = n - 1; i >= 0; i--) {
		for (int j = i - 1; j >= 0; j--) {
			b[j] = std::min(b[j], b[j] ^ b[i]);
		}
	}
}

template <class T> T reduce(std::vector<T>& b, T x) {
	for (auto& t : b) {
		x = std::min(x, x ^ t);
	}
	return x;
}

template <class T> bool add(std::vector<T>& b, T x) {
	if (!(x = reduce(b, x))) return false;
	int ind = 0;
	while (ind < (int)b.size() && b[ind] > x) ind++;
	b.insert(b.begin() + ind, x);
	return true;
}

Back to top page