简介
设数集$T$，$T$的线性基为最小的一个集合$S$，$S$与$T$通过异或运算能产生的集合相同，也就是$S$是$T$的线性无关极大子集
性质
- 线性基的异或集合中每个元素的异或方案唯一
- 线性基二进制最高位互不相同
维护
插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void insert(long long x)
{
for (int i = 60; i >= 0; i--)
{
if ((1ll << i) & x)
{
if (v[i])
{
x = x ^ v[i];
}
else
{
v[i] = x;
return;
}
}
}
}
|
合并
将一个线性基暴力插入到另一个线性基
查询一个数能否被这个线性基表示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| bool query(long long x)
{
for (int i = 60; i >= 0; i--)
{
if ((1ll << i) & x)
{
if (v[i])
{
x = x ^ v[i];
}
else
{
return false;
}
}
}
return true;
}
|
最大值
1
2
3
4
5
6
7
8
| ans = 0;
for (int i = 51; i >= 0; i--)
{
if ((ans ^ v[i]) > ans)
{
ans = ans ^ v[i];
}
}
|
第k小值
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
| void build()
{
for (int i = 0; i <= 60; i++)
{
for (int j = i - 1; j >= 0; j--)
{
if ((1ll << j) & v[i])
{
v[i] ^= v[j];
}
}
}
last = 0;
for (int i = 0; i <= 60; i++)
{
if (v[i])
{
vv[last] = v[i];
last++;
}
}
}
long long query(long long k)
{
if (k >= (1ll << last))
{
return (long long)-1;
}
long long ans = 0;
for (int i = 0; i < last; i++)
{
if ((1ll << i) & k)
{
ans = ans ^ vv[i];
}
}
return ans;
}
|
参考
https://blog.csdn.net/qaq__qaq/article/details/53812883