本篇对应源码见仓库
solutions/xcpc/algorithm/xor/basis/。
原理
概念
异或空间线性基的概念：一个集合能得到的==非零异或和==的结果，能被==元素个数尽量少==的集合
不多不少的得到，那么就说这个元素个数尽量少的集合，是这个集合的==异或空间线性基==。
注意：只关注去重的非零异或和能否全部得到，而不关心每种异或和的个数。
几个基础结论
- 对于原集合，任意的 ,用 a ^ b 替换 a 或 b 的一个数，不会影响原数组的非零异或和的组成
- 对于原集合，如果
a ^ b == 0，那么去除 a, b 其中一个，不会影响原数组的非零异或和的组成 - 对于原集合，如果可以异或出 0，那么在求出异或空间线性基后，需要单独标记一下原数组可以异或出 0，因为异或空间线性基不关注 0 的产生
- 那么如何判断原集合可以异或出 0 呢？
- 其实就是如果最终得到的线性基数组的非零元素个数比原集合大小更小的话，就说明原集合可以异或出 0，证明：根据第二条结论，线性基数组非零元素个数小的原因就是原集合通过两个或多个元素异或为 0 而舍弃了一个元素导致的
贪心法实现
- 通过贪心法实现得到的异或空间线性基能够构成不同的异或值（非零）的个数是 ，其中 是线性基的大小（原数组必须至少选一个数的情况下）
- 能够得到：
- 线性基大小
- 异或和个数
- 异或和是否有 0
- 最大异或和
- 最小异或和
示例代码
struct basis {
static const int LOG = 63;
vector<ll> b;
bool zero;
basis() {
b.resize(LOG + 1);
zero = false;
}
void insert(ll x) {
ferd(i, LOG, 0) {
if(x >> i & 1) {
if(!b[i]) {
b[i] = x;
break;
}
x ^= b[i];
}
}
zero = true;
}
ll query_max(ll x = 0) {
ferd(i, LOG, 0) {
if((x ^ b[i]) > x) x ^= b[i];
}
return x;
}
ll query_min() {
fer(i, 0, LOG + 1) {
if(b[i]) return b[i];
}
return 0;
}
bool check(ll x) {
ferd(i, LOG, 0) {
if(x >> i & 1) {
if(!b[i]) return false;
x ^= b[i];
}
}
return true;
}
};高斯消元法实现
-
能够得到：
- 是标准形式的异或空间线性基
- 能得到普通消元（贪心实现）能得到的信息
- 第 k 小的异或和
-
高斯消元得到的线性基（存在
B中），是逆序存储的 -
如何得到第 k 小的异或和：
- 将 k 转换为二进制，得到的每一位对应线性基中是否取该位的元素（逆序存储的线性基）
- 比如 k = 10，二进制为 1010，表示取线性基中（非零）倒数第 1 位和倒数第 3 位的元素异或
示例代码
int len;
vector<ll> B;
void gauss(vector<ll> &a) {
len = 1;
zero = false;
B.assign(all(a));
int n = a.size() - 1;
ferd(i, LOG, 0) {
if(len > n) break;
fer(j, len, n + 1) {
if(B[j] & (1LL << i)) {
swap(B[j], B[len]);
break;
}
}
if(B[len] & (1LL << i)) {
fer(j, 1, n + 1) {
if(j != len && B[j] & (1LL << i)) {
B[j] ^= B[len];
}
}
len++;
}
}
len--;
zero = len != n;
}
ll getKthMin(ll k) {
if(zero && k == 1) return 0;
if(zero) k--;
if(k >= (1LL << len)) return -1;
ll ans = 0;
for(int i = len, j = 0; i >= 1; i--, j++) {
if(k & (1LL << j)) {
ans ^= B[i];
}
}
return ans;
}模板
struct basis {
static const int LOG = 63;
vector<ll> b;
bool zero;
basis() {
b.resize(LOG + 1);
zero = false;
}
basis(vector<ll> &a) {
b.resize(LOG + 1);
gauss(a);
}
void insert(ll x) {
ferd(i, LOG, 0) {
if(x >> i & 1) {
if(!b[i]) {
b[i] = x;
break;
}
x ^= b[i];
}
}
zero = true;
}
ll query_max(ll x = 0) {
ferd(i, LOG, 0) {
if((x ^ b[i]) > x) x ^= b[i];
}
return x;
}
ll query_min() {
fer(i, 0, LOG + 1) {
if(b[i]) return b[i];
}
return 0;
}
bool check(ll x) {
ferd(i, LOG, 0) {
if(x >> i & 1) {
if(!b[i]) return false;
x ^= b[i];
}
}
return true;
}
int len;
vector<ll> B;
void gauss(vector<ll> &a) {
len = 1;
zero = false;
B.assign(all(a));
int n = a.size() - 1;
ferd(i, LOG, 0) {
if(len > n) break;
fer(j, len, n + 1) {
if(B[j] & (1LL << i)) {
swap(B[j], B[len]);
break;
}
}
if(B[len] & (1LL << i)) {
fer(j, 1, n + 1) {
if(j != len && B[j] & (1LL << i)) {
B[j] ^= B[len];
}
}
len++;
}
}
len--;
zero = len != n;
}
ll getKthMin(ll k) {
if(zero && k == 1) return 0;
if(zero) k--;
if(k >= (1LL << len)) return -1;
ll ans = 0;
for(int i = len, j = 0; i >= 1; i--, j++) {
if(k & (1LL << j)) {
ans ^= B[i];
}
}
return ans;
}
};