xor_basis.hpp¶
维护整数集合的 \(\mathrm{GF}(2)\) 线性基；用于最大子集异或、可表示性、秩和第 \(k\) 小异或。
\[
\displaystyle \operatorname{span}_{\mathbb F_2}(B)=\left\{\bigoplus_{b\in S}b:S\subseteq B\right\}
\]
Complexity: Time: \(O(B)\) insertion/query and \(O(B^{2})\) merge/intersection. Space: \(O(B)\).
AC 记录：intersection_of_f2_vector_spaces。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(B) insertion/query and O(B^2) merge/intersection.
/// Space: O(B).
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <vector>
namespace noya {
/// @brief Reduced linear basis over GF(2) for an unsigned integer type.
template <class UInt, int bts = std::numeric_limits<UInt>::digits>
struct xor_basis {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < bts && bts <= std::numeric_limits<UInt>::digits);
std::array<UInt, bts> bas{};
int dim = 0;
/// @brief Insert a value fitting bts bits; return false if already in the span.
bool insert(UInt val) {
if constexpr (bts < std::numeric_limits<UInt>::digits)
assert((val >> bts) == 0);
for (int bit = bts - 1; bit >= 0; bit--) {
if (((val >> bit) & UInt(1)) == 0) {
continue;
}
if (bas[bit] != 0) {
val ^= bas[bit];
continue;
}
bas[bit] = val;
for (int lo = 0; lo < bit; lo++) {
if ((bas[bit] >> lo) & UInt(1)) {
bas[bit] ^= bas[lo];
}
}
for (int hig = bit + 1; hig < bts; hig++) {
if ((bas[hig] >> bit) & UInt(1)) {
bas[hig] ^= bas[bit];
}
}
dim++;
return true;
}
return false;
}
/// @brief Return whether value belongs to the represented xor span.
bool contains(UInt val) const {
for (int bit = bts - 1; bit >= 0; bit--) {
if ((val >> bit) & UInt(1)) {
val ^= bas[bit];
}
}
return val == 0;
}
/// @brief Maximize seed xor x over all represented values x.
UInt max_xor(UInt see = 0) const {
for (int bit = bts - 1; bit >= 0; bit--) {
if ((see ^ bas[bit]) > see) {
see ^= bas[bit];
}
}
return see;
}
/// @brief Minimize seed xor x over all represented values x.
UInt min_xor(UInt see) const {
for (int bit = bts - 1; bit >= 0; bit--) {
if ((see ^ bas[bit]) < see) {
see ^= bas[bit];
}
}
return see;
}
/// @brief Return the k-th smallest distinct value in the span, including
/// zero.
UInt kth_smallest(std::uint64_t k) const {
if (dim < 64) {
assert(k < (std::uint64_t(1) << dim));
}
UInt res = 0;
int idx = 0;
for (int bit = 0; bit < bts; bit++) {
if (bas[bit] != 0) {
if (idx < 64 && ((k >> idx) & 1)) {
res ^= bas[bit];
}
idx++;
}
}
return res;
}
/// @brief Insert every basis vector from another span.
void merge(const xor_basis &oth) {
for (UInt val : oth.bas) {
if (val != 0) {
insert(val);
}
}
}
};
/// @brief Return a basis of the intersection of two xor spans. Both input
/// lists must be independent, with values fitting bts bits. Eliminate the
/// first space, then the second, carrying each vector's contribution from the
/// first space. A vector reduced to zero yields a vector in both spaces.
template <class UInt, int bts = std::numeric_limits<UInt>::digits>
std::vector<UInt> xor_space_intersection(const std::vector<UInt> &a,
const std::vector<UInt> &b) {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < bts && bts <= std::numeric_limits<UInt>::digits);
xor_basis<UInt, bts> lc, rc;
for (UInt val : a) assert(lc.insert(val));
for (UInt val : b) assert(rc.insert(val));
std::array<UInt, bts> bas{}, src{};
auto ins = [&](UInt x, UInt y) {
for (int i = bts - 1; i >= 0; --i) {
if (((x >> i) & UInt(1)) == 0) continue;
if (bas[i]) {
x ^= bas[i];
y ^= src[i];
} else {
bas[i] = x;
src[i] = y;
return UInt(0);
}
}
return y;
};
for (UInt x : a) ins(x, x);
std::vector<UInt> res;
res.reserve(std::min(a.size(), b.size()));
for (UInt x : b) {
UInt y = ins(x, UInt(0));
if (y) res.push_back(y);
}
return res;
}
} // namespace noya
// NOYA_XOR_BASIS_HPP
#ifndef NOYA_XOR_BASIS_HPP
#define NOYA_XOR_BASIS_HPP 1
/// @complexity Time: O(B) insertion/query and O(B^2) merge/intersection.
/// Space: O(B).
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <vector>
namespace noya {
/// @brief Reduced linear basis over GF(2) for an unsigned integer type.
template <class UInt, int bts = std::numeric_limits<UInt>::digits>
struct xor_basis {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < bts && bts <= std::numeric_limits<UInt>::digits);
std::array<UInt, bts> bas{};
int dim = 0;
/// @brief Insert a value fitting bts bits; return false if already in the span.
bool insert(UInt val) {
if constexpr (bts < std::numeric_limits<UInt>::digits)
assert((val >> bts) == 0);
for (int bit = bts - 1; bit >= 0; bit--) {
if (((val >> bit) & UInt(1)) == 0) {
continue;
}
if (bas[bit] != 0) {
val ^= bas[bit];
continue;
}
bas[bit] = val;
for (int lo = 0; lo < bit; lo++) {
if ((bas[bit] >> lo) & UInt(1)) {
bas[bit] ^= bas[lo];
}
}
for (int hig = bit + 1; hig < bts; hig++) {
if ((bas[hig] >> bit) & UInt(1)) {
bas[hig] ^= bas[bit];
}
}
dim++;
return true;
}
return false;
}
/// @brief Return whether value belongs to the represented xor span.
bool contains(UInt val) const {
for (int bit = bts - 1; bit >= 0; bit--) {
if ((val >> bit) & UInt(1)) {
val ^= bas[bit];
}
}
return val == 0;
}
/// @brief Maximize seed xor x over all represented values x.
UInt max_xor(UInt see = 0) const {
for (int bit = bts - 1; bit >= 0; bit--) {
if ((see ^ bas[bit]) > see) {
see ^= bas[bit];
}
}
return see;
}
/// @brief Minimize seed xor x over all represented values x.
UInt min_xor(UInt see) const {
for (int bit = bts - 1; bit >= 0; bit--) {
if ((see ^ bas[bit]) < see) {
see ^= bas[bit];
}
}
return see;
}
/// @brief Return the k-th smallest distinct value in the span, including
/// zero.
UInt kth_smallest(std::uint64_t k) const {
if (dim < 64) {
assert(k < (std::uint64_t(1) << dim));
}
UInt res = 0;
int idx = 0;
for (int bit = 0; bit < bts; bit++) {
if (bas[bit] != 0) {
if (idx < 64 && ((k >> idx) & 1)) {
res ^= bas[bit];
}
idx++;
}
}
return res;
}
/// @brief Insert every basis vector from another span.
void merge(const xor_basis &oth) {
for (UInt val : oth.bas) {
if (val != 0) {
insert(val);
}
}
}
};
/// @brief Return a basis of the intersection of two xor spans. Both input
/// lists must be independent, with values fitting bts bits. Eliminate the
/// first space, then the second, carrying each vector's contribution from the
/// first space. A vector reduced to zero yields a vector in both spaces.
template <class UInt, int bts = std::numeric_limits<UInt>::digits>
std::vector<UInt> xor_space_intersection(const std::vector<UInt> &a,
const std::vector<UInt> &b) {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < bts && bts <= std::numeric_limits<UInt>::digits);
xor_basis<UInt, bts> lc, rc;
for (UInt val : a) assert(lc.insert(val));
for (UInt val : b) assert(rc.insert(val));
std::array<UInt, bts> bas{}, src{};
auto ins = [&](UInt x, UInt y) {
for (int i = bts - 1; i >= 0; --i) {
if (((x >> i) & UInt(1)) == 0) continue;
if (bas[i]) {
x ^= bas[i];
y ^= src[i];
} else {
bas[i] = x;
src[i] = y;
return UInt(0);
}
}
return y;
};
for (UInt x : a) ins(x, x);
std::vector<UInt> res;
res.reserve(std::min(a.size(), b.size()));
for (UInt x : b) {
UInt y = ins(x, UInt(0));
if (y) res.push_back(y);
}
return res;
}
} // namespace noya
#endif // NOYA_XOR_BASIS_HPP
/// @complexity Time: O(B) insertion/query and O(B^2) merge/intersection.
/// Space: O(B).
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <vector>
namespace noya {
/// @brief Reduced linear basis over GF(2) for an unsigned integer type.
template <class UInt, int bts = std::numeric_limits<UInt>::digits>
struct xor_basis {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < bts && bts <= std::numeric_limits<UInt>::digits);
std::array<UInt, bts> bas{};
int dim = 0;
/// @brief Insert a value fitting bts bits; return false if already in the span.
bool insert(UInt val) {
if constexpr (bts < std::numeric_limits<UInt>::digits)
assert((val >> bts) == 0);
for (int bit = bts - 1; bit >= 0; bit--) {
if (((val >> bit) & UInt(1)) == 0) {
continue;
}
if (bas[bit] != 0) {
val ^= bas[bit];
continue;
}
bas[bit] = val;
for (int lo = 0; lo < bit; lo++) {
if ((bas[bit] >> lo) & UInt(1)) {
bas[bit] ^= bas[lo];
}
}
for (int hig = bit + 1; hig < bts; hig++) {
if ((bas[hig] >> bit) & UInt(1)) {
bas[hig] ^= bas[bit];
}
}
dim++;
return true;
}
return false;
}
/// @brief Return whether value belongs to the represented xor span.
bool contains(UInt val) const {
for (int bit = bts - 1; bit >= 0; bit--) {
if ((val >> bit) & UInt(1)) {
val ^= bas[bit];
}
}
return val == 0;
}
/// @brief Maximize seed xor x over all represented values x.
UInt max_xor(UInt see = 0) const {
for (int bit = bts - 1; bit >= 0; bit--) {
if ((see ^ bas[bit]) > see) {
see ^= bas[bit];
}
}
return see;
}
/// @brief Minimize seed xor x over all represented values x.
UInt min_xor(UInt see) const {
for (int bit = bts - 1; bit >= 0; bit--) {
if ((see ^ bas[bit]) < see) {
see ^= bas[bit];
}
}
return see;
}
/// @brief Return the k-th smallest distinct value in the span, including
/// zero.
UInt kth_smallest(std::uint64_t k) const {
if (dim < 64) {
assert(k < (std::uint64_t(1) << dim));
}
UInt res = 0;
int idx = 0;
for (int bit = 0; bit < bts; bit++) {
if (bas[bit] != 0) {
if (idx < 64 && ((k >> idx) & 1)) {
res ^= bas[bit];
}
idx++;
}
}
return res;
}
/// @brief Insert every basis vector from another span.
void merge(const xor_basis &oth) {
for (UInt val : oth.bas) {
if (val != 0) {
insert(val);
}
}
}
};
/// @brief Return a basis of the intersection of two xor spans. Both input
/// lists must be independent, with values fitting bts bits. Eliminate the
/// first space, then the second, carrying each vector's contribution from the
/// first space. A vector reduced to zero yields a vector in both spaces.
template <class UInt, int bts = std::numeric_limits<UInt>::digits>
std::vector<UInt> xor_space_intersection(const std::vector<UInt> &a,
const std::vector<UInt> &b) {
static_assert(std::is_integral_v<UInt> && std::is_unsigned_v<UInt>);
static_assert(0 < bts && bts <= std::numeric_limits<UInt>::digits);
xor_basis<UInt, bts> lc, rc;
for (UInt val : a) assert(lc.insert(val));
for (UInt val : b) assert(rc.insert(val));
std::array<UInt, bts> bas{}, src{};
auto ins = [&](UInt x, UInt y) {
for (int i = bts - 1; i >= 0; --i) {
if (((x >> i) & UInt(1)) == 0) continue;
if (bas[i]) {
x ^= bas[i];
y ^= src[i];
} else {
bas[i] = x;
src[i] = y;
return UInt(0);
}
}
return y;
};
for (UInt x : a) ins(x, x);
std::vector<UInt> res;
res.reserve(std::min(a.size(), b.size()));
for (UInt x : b) {
UInt y = ins(x, UInt(0));
if (y) res.push_back(y);
}
return res;
}
} // namespace noya
// NOYA_XOR_BASIS_HPP