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^2) reduced insertion and O(B) membership/min/max query. Space: O(B).
AC 记录：intersection_of_f2_vector_spaces。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(B^2) reduced insertion and O(B) membership/min/max query.
/// Space: O(B).
#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; return false if it is already in the span.
bool insert(UInt val) {
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 ((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. A homogeneous
/// system is built for U*a = V*b, with one equation per value bit. Gaussian
/// elimination produces a nullspace basis; projecting its U-coordinates gives
/// an independent basis of the intersection because both input lists are
/// required to be independent.
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);
const int ls = int(a.size());
const int vc = ls + int(b.size());
assert(vc <= 64);
xor_basis<UInt, bts> lc;
xor_basis<UInt, bts> rc;
for (UInt val : a) {
assert(lc.insert(val));
}
for (UInt val : b) {
assert(rc.insert(val));
}
std::array<std::uint64_t, bts> equ{};
for (int var = 0; var < vc; var++) {
UInt val = var < ls ? a[var] : b[var - ls];
for (int bit = 0; bit < bts; bit++) {
if ((val >> bit) & UInt(1)) {
equ[bit] |= std::uint64_t(1) << var;
}
}
}
std::array<int, 64> pr{};
pr.fill(-1);
int ran = 0;
for (int col = 0; col < vc; col++) {
int piv = ran;
while (piv < bts && ((equ[piv] >> col) & 1) == 0) {
piv++;
}
if (piv == bts) {
continue;
}
std::swap(equ[ran], equ[piv]);
pr[col] = ran;
for (int row = 0; row < bts; row++) {
if (row != ran && ((equ[row] >> col) & 1)) {
equ[row] ^= equ[ran];
}
}
ran++;
}
std::vector<UInt> res;
for (int fc = 0; fc < vc; fc++) {
if (pr[fc] != -1) {
continue;
}
std::uint64_t cf = std::uint64_t(1) << fc;
for (int col = 0; col < vc; col++) {
int row = pr[col];
if (row != -1 && ((equ[row] >> fc) & 1)) {
cf |= std::uint64_t(1) << col;
}
}
UInt val = 0;
for (int idx = 0; idx < ls; idx++) {
if ((cf >> idx) & 1) {
val ^= a[idx];
}
}
res.push_back(val);
}
return res;
}
} // namespace noya
#ifndef NOYA_XOR_BASIS_HPP
#define NOYA_XOR_BASIS_HPP 1
/// @complexity Time: O(B^2) reduced insertion and O(B) membership/min/max query.
/// Space: O(B).
#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; return false if it is already in the span.
bool insert(UInt val) {
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 ((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. A homogeneous
/// system is built for U*a = V*b, with one equation per value bit. Gaussian
/// elimination produces a nullspace basis; projecting its U-coordinates gives
/// an independent basis of the intersection because both input lists are
/// required to be independent.
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);
const int ls = int(a.size());
const int vc = ls + int(b.size());
assert(vc <= 64);
xor_basis<UInt, bts> lc;
xor_basis<UInt, bts> rc;
for (UInt val : a) {
assert(lc.insert(val));
}
for (UInt val : b) {
assert(rc.insert(val));
}
std::array<std::uint64_t, bts> equ{};
for (int var = 0; var < vc; var++) {
UInt val = var < ls ? a[var] : b[var - ls];
for (int bit = 0; bit < bts; bit++) {
if ((val >> bit) & UInt(1)) {
equ[bit] |= std::uint64_t(1) << var;
}
}
}
std::array<int, 64> pr{};
pr.fill(-1);
int ran = 0;
for (int col = 0; col < vc; col++) {
int piv = ran;
while (piv < bts && ((equ[piv] >> col) & 1) == 0) {
piv++;
}
if (piv == bts) {
continue;
}
std::swap(equ[ran], equ[piv]);
pr[col] = ran;
for (int row = 0; row < bts; row++) {
if (row != ran && ((equ[row] >> col) & 1)) {
equ[row] ^= equ[ran];
}
}
ran++;
}
std::vector<UInt> res;
for (int fc = 0; fc < vc; fc++) {
if (pr[fc] != -1) {
continue;
}
std::uint64_t cf = std::uint64_t(1) << fc;
for (int col = 0; col < vc; col++) {
int row = pr[col];
if (row != -1 && ((equ[row] >> fc) & 1)) {
cf |= std::uint64_t(1) << col;
}
}
UInt val = 0;
for (int idx = 0; idx < ls; idx++) {
if ((cf >> idx) & 1) {
val ^= a[idx];
}
}
res.push_back(val);
}
return res;
}
} // namespace noya
#endif // NOYA_XOR_BASIS_HPP
#include <array>
#include <cassert>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <vector>
/// @complexity Time: O(B^2) reduced insertion and O(B) membership/min/max query.
/// Space: O(B).
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; return false if it is already in the span.
bool insert(UInt val) {
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 ((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. A homogeneous
/// system is built for U*a = V*b, with one equation per value bit. Gaussian
/// elimination produces a nullspace basis; projecting its U-coordinates gives
/// an independent basis of the intersection because both input lists are
/// required to be independent.
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);
const int ls = int(a.size());
const int vc = ls + int(b.size());
assert(vc <= 64);
xor_basis<UInt, bts> lc;
xor_basis<UInt, bts> rc;
for (UInt val : a) {
assert(lc.insert(val));
}
for (UInt val : b) {
assert(rc.insert(val));
}
std::array<std::uint64_t, bts> equ{};
for (int var = 0; var < vc; var++) {
UInt val = var < ls ? a[var] : b[var - ls];
for (int bit = 0; bit < bts; bit++) {
if ((val >> bit) & UInt(1)) {
equ[bit] |= std::uint64_t(1) << var;
}
}
}
std::array<int, 64> pr{};
pr.fill(-1);
int ran = 0;
for (int col = 0; col < vc; col++) {
int piv = ran;
while (piv < bts && ((equ[piv] >> col) & 1) == 0) {
piv++;
}
if (piv == bts) {
continue;
}
std::swap(equ[ran], equ[piv]);
pr[col] = ran;
for (int row = 0; row < bts; row++) {
if (row != ran && ((equ[row] >> col) & 1)) {
equ[row] ^= equ[ran];
}
}
ran++;
}
std::vector<UInt> res;
for (int fc = 0; fc < vc; fc++) {
if (pr[fc] != -1) {
continue;
}
std::uint64_t cf = std::uint64_t(1) << fc;
for (int col = 0; col < vc; col++) {
int row = pr[col];
if (row != -1 && ((equ[row] >> fc) & 1)) {
cf |= std::uint64_t(1) << col;
}
}
UInt val = 0;
for (int idx = 0; idx < ls; idx++) {
if ((cf >> idx) & 1) {
val ^= a[idx];
}
}
res.push_back(val);
}
return res;
}
} // namespace noya