你说我一个连线性基都不会的人怎么可能走的远,我跟你说我也是这么想的,但是你先别急。
一、线性基
OI 中常用全部的就是 \(2\) 进制下的异或线性基。
线性基就是可以把一个集合里的数转化成一组基,使得这组基里所有 xor 出来的结果于原集合 xor 出来的结果完全一致。
这是一个线性基模板:
struct linear_basis_awa {
ll bs[64];
int cnt;
inline void init () {
for (int i = 0;i < 64; ++ i) bs[i] = 0;
cnt = 0;
}
inline void ins (ll x) {
if (!x) return ;
for (int i = 62;i >= 0; -- i) {
if (x & (1ll << i)) {
if (bs[i]) x ^= bs[i];
else {
cnt ++;
bs[i] = x;
break;
}
}
}
}
inline ll query_maxxor (ll x) {
ll res = x;
for (int i = 62;i >= 0; -- i) {
if ((res ^ bs[i]) > res) res ^= bs[i];
}
return res;
}
inline void merge_bas (linear_basis_awa O) {
for (int i = 0;i < 64; ++ i) ins (O.bs[i]);
}
inline void operator = (linear_basis_awa O) {
for (int i = 0;i < 64; ++ i) bs[i] = O.bs[i];
cnt = O.cnt;
}
};
其中这里的 \(bs_{w}\) 是最高位为 \(2^w\) 的基向量。
线性基的插入
如果 \(x\) 这个数内包含 \(2^w\) 这一位,如果基中已经有,那么直接异或掉 \(2^w\),否则那就直接加入 \(x\),然后结束,时间复杂度 \(O(\log w)\)。
线性基求最大 xor 和
对于 query_maxxor (int v)
函数的解释:查询 \(\displaystyle \max_{S \subseteq \text{base}} \left[\left(\bigoplus_{x \in S} x\right) \oplus v\right]\);做法:贪心,如果 \(2^x\) 这一位异或下来是 \(1\),那么一定要比后面所有位都是 \(1\) 产生的贡献之和(\(2^x - 1\))还要大,所以我们从高位往低位贪心肯定是最优的,时间复杂度 \(O(\log w)\)。
线性基 xor 值计数
因为线性基里的数都是线性无关的,所以任意一个子集(不含 \(0\))xor 出来的值都互不相同,如果含 \(0\) 总共就是 \(2^{cnt}\) 种情况,其中 \(cnt\) 是基中非 \(0\) 的数的数量。
线性基合并
直接将一个线性基里的数暴力插入到另一个线性基里即可,时间复杂度 \(O(\log^2 w)\)。
标签:cnt,xor,int,void,笔记,学习,bs,线性 From: https://www.cnblogs.com/RB16B/p/17632205.html