异或线性基
基可以看做是一个空间的坐标轴，例如二维坐标系上每一个点都可以表示为[1,0],[0,1]的表示即
异或线性基则是一组数中的基，他们之间有以下性质
线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。
线性基是满足性质 1 的最小的集合。
线性基没有异或和为 0 的子集。
线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。
线性基中每个元素的二进制最高位互不相同。
显然，这如果存在一组数组成一个集合，并且这个集合是最小的，可以异或出原数组的所有数，并且这组线性基是线性无关的，即任何一个数都无法被任意的数线性表示出来，那么这组数就是原数组的线性基。
如何求线性基呢？
我们可以考虑一个数添加的过程
- 从高位j扫描当前的数x，如果a[j]位置上已经存在了一个基，那么用这个基来异或上x，消除掉x当前位的1，无需考虑后面的位(这里可以仔细想想为什么)
2.如果x被异或为0，说明已存在的基可以线性表示出x
3.如果找到一个位j，此时a[j]位置上没有基，那么就令a[j] = x(此时的x)已经被处理过了，即[j+1,MAXL]上的位全为0了 代码实现
1
2
3
4
5
6
7
8
9
10
11
| inline void insert(long long x) {
for (int i = 60; i + 1; i--) {
if (!(x >> i))
continue;
if (!p[i]) {
p[i] = x;
break;
}
x ^= p[i];
}
}
|
作用
- 求出一组数的最大异或子集:
最大异或就是将每个基地异或起来
- 求出第k大异或值
将k进行二进制拆分，然后如果j位上有1则异或上aj
- 求出最小值
k=1的时候
- 判断某个数能否被异或出来
通过将该数进行二进制拆分，有1的地方异或上该位上的基底
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| struct LinearBasis
{
long long a[MAXL + 1];
LinearBasis()
{
std::fill(a, a + MAXL + 1, 0);
}
void clear(){
std::fill(a, a + MAXL + 1, 0);
}
ll MaxXor(){
ll res = 0;
for(int j=MAXL;j>=0;j--){
if(a[j])res^=a[j];
}
return res;
}
void insert(long long t)
{
for (int j = MAXL; j >= 0; j--)
{
if (!(t & (1ll << j))) continue;
if (a[j]) t ^= a[j];
else
{
a[j] = t;
return;
}
}
}
}L;
|