Zth's Blog

记录学习路上的点滴

0%

线性基

线性基模板

线性基

定义

根据oiwiki, 线性基是一个集合(整数序列)构造出的另一个集合, 这个新集合满足一下性质

  1. 线性基的元素相互异或能够得到所有原集合元素能够异或出来的值
  2. 线性基是满足性质1的最小的集合
  3. 线性基没有异或为$0$的子集
  4. 每个原集合能够异或出的元素在线性基中的异或方式是唯一的
  5. 线性基内每个元素的最高二进制位互不相同

求法

代码

我们采用插入数值的方法, 遍历原集合的每个元素尝试插入线性基中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
long long al[51]; // 线性基中最高二进制位为i的元素

void Insert(long long x)
{
for(int i = 50; i >= 0; i --)
{
if(! ((1LL << i) & x)) continue;

if(al[i])
x ^= al[i];
else
{
al[i] = x;

break;
}
}
}

证明

当我们要插入一个数$x$时, 考虑到性质3, 我们先尝试把$x$和已有的线性基元素异或看看时候能把$x$变为$0$, 也就是看$x$能不能由当前已有的线性基异或得到, 如过能够做到, 那$x$不需要被加入线性基; 否则, 由于我们在这一过程中尝试将$x$异或成$0$,$x$是在变化的, 如果从高到低遇到一位无法被异或掉, 考虑性质$1$, 我们要想异或出原来的$x$那就必须要把剩下的这个$x$加入线性基, 而这也恰好能满足性质5

对于性质1和性质4: 刚才我们已经证明了原集合中的每个元素都可以被线性基表示, 那么假设原集合为$X$, 线性基为$Y$, 有一个元素$S = X_{a_1} \oplus X_{a_2} \oplus … \oplus X_{a_k}$, 表示$S$是由原集合的$k$个元素异或得到的, 由于每个$X_i$都可以由线性基中的元素异或得到, 那我们统计这$k$个元素中每个线性基元素的使用次数, 将所有使用次数为奇数的线性基元素异或起来就得到了$S$

对于性质2, 由性质5可以自证

典型应用 + 代码

给$n$个元素, 求其中元素能异或出的最大值

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
#include <iostream>
#include <cstdio>

int n;
long long al[51];
long long ans;

void Insert(long long x)
{
for(int i = 50; i >= 0; i --)
{
if(! ((1LL << i) & x)) continue;

if(al[i])
x ^= al[i];
else
{
al[i] = x;

break;
}
}
}

int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
{
long long a;
scanf("%lld", &a);

Insert(a);
}

for(int i = 50; i >= 0; i --)
if((ans ^ al[i]) > ans)
ans ^= al[i];

printf("%lld\n", ans);

return 0;
}