概念
线性基是一个满足 原数组里的数异或得到的数字集等于其线性基里的数异或可得到的数字集 的最小数字集
一般来说，值域为 \(W\) 的数组的线性基的大小为 \(\log{W}\)
一些有用的性质
- 原数列里的数都可以通过线性基里的数异或表示出来
- 线性基里任意一个子集的异或和都不为 \(0\)
- 一个数列可能有多个线性基，但是线性基里数的数量一定唯一，而且是满足性质一的基础上最少的
实现
注：以下代码中的 p[i] 表示线性基数组， cnt 为线性基大小， zero 为原数组能否异或出 \(0\) ， \(2^{MB}\) 为值域
插入
从高到低枚举 \(x\) 在二进制下的每一位，判断 \(p_i\) 这个位置是否有数，没有就插入并退出，否则将 \(x\) 异或上 \(p_i\) 继续
如果没有成功插入这个数，那么枚举到的每一个线性基中的数异或起来就可以得到这个数，即无需插入，满足性质2
否则表示不出来，就插入
（注意到插入显然满足线性基第 \(i\) 位上的数二进制下最高位也为第 \(i\) 位
inline bool insert(ll x) {
for (int i = MB; ~i; --i)
if (x & (1ll << i)) {
if (p[i])
x ^= p[i];
else {
++cnt, p[i] = x;
return true;
}
}
zero = true;
return false;
}
查询一个元素能否被原数组异或出来
由性质1可得，我们只要用线性基里的数尝试异或即可
注意到插入时失败当且仅当原线性基可以表示出这个数
类比插入操作编写即可
inline bool query(ll x) {
for (int i = MB; ~i; --i)
if (x & (1ll << i)) {
if (p[i])
x ^= p[i];
else
return false;
}
return true;
}
查询异或最大值
按位贪心即可
inline ll querymax() {
ll res = 0;
for (int i = MB; ~i; --i)
if ((res ^ p[i]) > res)
res ^= p[i];
return res;
}
查询异或最小值
异或的最小值一般就是线性基里的最小元素，因为插入这个元素的时候我们总是尽量让它的高位全消掉才来插入这一位
但是原数组可能存在异或为 \(0\) 的数，特判一下即可
inline ll querymin() {
if (zero)
return 0;
for (int i = 0; i <= MB; ++i)
if (p[i])
return p[i];
}
查询异或 \(k\) 小值
首先考虑，如果每一位的选择都不会影响下一位的异或值，那就可以直接从高到低按位去选择就行了
但是线性基时不满足这个性质，我们考虑重新构造一个线性基
我们尽量把原来的线性基只留下最高位的 \(1\)， 从而使得线性基中的数的异或值不会相互影响
理想状态下，这个线性基值这样的
\[p_0 = (0001)_2 \\ p_1 = (0010)_2 \\ p_2 = (0100)_2 \\ p_3 = (1000)_2 \]但是总有一些非理想情况，比如这样
\[p_0 = (0001)_2 \\ p_1 = (0000)_2 \\ p_2 = (0101)_2 \\ p_3 = (1000)_2 \]但是它仍然满足线性基中的数的异或值不会相互影响， 我们将其导入 \(d\) 数组中，新线性基的大小为 tot
那么不难写出查询异或 \(k\) 小值的代码了（记得特判 \(0\)
inline void rebuild() {
for (int i = 63; ~i; --i)
for (int j = i - 1; ~j; --j)
if (p[i] & (1ll << j))
p[i] ^= p[j];
tot = 0;
for (int i = 0; i <= MB; ++i)
if (p[i])
d[tot++] = p[i];
}
inline ll kth(ll k) {
if (zero)
--k;
if (k >= (1ll << tot))
return -1;
ll res = 0;
for (int i = tot; ~i; --i)
if (k & (1ll << i))
res ^= d[i];
return res;
}