线性基

2020-03-07

数据结构与算法

字数统计: 2k字 | 阅读时长≈ 8分钟

线性基的总结

线性基详解

线性基是什么

你可以理解为将一个序列处理完之后得到的产物，并且有如下性质（后面有证明）：

线性基的性质

原序列里面的任意一个数都可以由线性基里面的一些数异或得到
线性基里面的任意一些数异或起来都不能得到00
线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的

线性基的构造过程

那么它是怎么构造的呢？

我们设有一个数组dd，表示序列aa的线性基，下标从00开始算。对于序列里面的每一个数，我们尝试将它插入到线性基里面去，具体如何插入这里给出伪代码（为了方便理解，我们设 x(2)x(2) 为xx的二进制数）：

1	复制for i=60 to 0
2	if(x(2)的第i+1位为1)
3	{
4	if(d[i]为0)
5	{
6	d[i]=x;
7	break;
8	}
9	else x=x^d[i];
10	}

据此，我们可以得到一个关于dd数组的性质：若d[i]d[i]不为00，则d[i]（2）d[i]（2）的第i+1i+1位为11，并且d[i]（2）d[i]（2）的最高位就是第i+1i+1位。
为了更好地进行线性基的讲解，我们要先知道关于异或的一个小性质：
如果满足aa ^ bb ^ c=0c=0 ，那么aa ^ b=cb=c，所以如果aa ^ b=cb=c，那么aa ^ c=bc=b
证明虽然简单但是这里就不给出了，不明白的读者手动模拟一下就明白了

线性基性质的证明

性质1

我们知道了线性基的构造方法后，其实就可以很容易想到如何证明性质1了，我们设原序列里面有一个数x，我们尝试用它来构造线性基，那么会有两种结果：1、不能成功插入线性基；2、成功插入线性基。

分类讨论一下：

不能成功插入线性基

什么时候不能插入进去呢？
显然就是它在尝试插入时异或若干个数之后变成了00
那么就有如下式子：
xx ^ d[a]d[a] ^ d[b]d[b] ^ d[c]d[c] ^…=0=0
根据上面的那个小性质，则有：
d[a]d[a] ^ d[b]d[b] ^ d[c]d[c] ^…=x=x
所以，如果xx不能成功插入线性基，一定是因为当前线性基里面的一些数异或起来可以等于xx。

可以成功插入线性基

我们假设xx插入到了线性基的第ii个位置，显然，它在插入前可能异或若干个数，那么就有：
xx ^ d[a]d[a] ^ d[b]d[b] ^ d[c]d[c] ^…=d[i]=d[i]
d[i]d[i] ^ d[a]d[a] ^ d[b]d[b] ^ d[c]d[c] ^…=x=x
所以显然，xx此时也可以由线性基里面的若干个数异或得到。

综上，性质1得证

性质2

我们使用反证法
设d[a]d[a] ^ d[b]d[b] ^ d[c]=0d[c]=0（其中d[c]d[c]比d[a]d[a]和d[b]d[b]要更晚被插入线性基）
那么有d[a]d[a] ^ d[b]=d[c]d[b]=d[c]
∵d[c]∵d[c]可以由d[a]d[a] ^ d[b]d[b]得到
∴d[c]∴d[c]不可能插入线性基
故假设不成立，所以线性基中不存在有任何数异或起来可以得到00。

性质3

分类讨论一下

假如序列里面的所有元素都可以插入到线性基里面

显然如果是这种情况的话，不管是用什么顺序将序列里的数插入到线性基里，线性基中的元素一定与原序列元素数量相同。所以性质3成立。

假如序列里面的一些元素不能插入到线性基里面

我们设xx不能插入到线性基里面，那么一定满足形如d[a]d[a] ^ d[b]d[b] ^ d[c]=xd[c]=x的式子，那我们尝试将插入顺序改变，变成：d[a]d[a]、d[b]d[b]、xx、d[c]d[c]。那么显然，d[c]d[c]是不可能插入成功的，简单的证明：
∵d[a]∵d[a] ^ d[b]d[b] ^ d[c]=xd[c]=x
∴d[a]∴d[a] ^ d[b]d[b] ^ x=d[c]x=d[c]（根据上面那条异或性质）
原来是xx插入不进去，改变顺序后，d[c]d[c]插入不进去，也就是说，对于插入不进去的元素，改变插入顺序后，要么还是插入不进去，要么就是插入进去了，同时另一个原来插入的进去的元素插入不进去了，所以，可以插入进去的元素数量一定是固定的。
显然，如果你去掉线性基里面的任意一个数，都会使得原序列里的一些（或一个）数无法通过用线性基里的元素异或得到，所以，每一个元素都是必要的，换句话说，这里面没有多余的元素，所以，这个线性基的元素个数在保持性质1的前提下，一定是最少的。

模板

1	复制void add(ll x)
2	{
3	for(int i=50;i>=0;i--)
4	{
5	if(x&(1ll<<i))//注意，如果i大于31，前面的1的后面一定要加ll
6	{
7	if(d[i])x^=d[i];
8	else
9	{
10	d[i]=x;
11	break;//记得如果插入成功一定要退出
12	}
13	}
14	}
15	}

线性基的应用

求异或最大值

1	复制ll ans()
2	{
3	ll anss=0;
4	for(int i=50;i>=0;i--)//记得从线性基的最高位开始
5	if((anss^d[i])>anss)anss^=d[i];
6	return anss;
7	}

求异或最小值

显然的，最小值一定是最小的d[i]d[i]

求异或第 K 小值

完整的说，应该是——从一个序列中取任意个元素进行异或，求能异或出的所有数字中第kk小的那个。
首先，要对这个序列的线性基处理一下，对于每一个d[i]d[i]，枚举j=ito1j=ito1，如果d[i]（2）d[i]（2）的第jj位为11，那么d[i]d[i]异或d[j−1]d[j−1]。
那么处理完一个线性基之后，应该大致是长这个样子的（x表示0或1）：
1xxxx0xxx0x1xxxx0xxx0x
……1xxx0x……1xxx0x
………..1x………..1x
求解过程：将k先转成二进制，假如kk的第ii位为11，ansans就异或上线性基中第ii个元素（注意不是直接异或d[i−1]d[i−1]）。

1	复制void work()//处理线性基
2	{
3	for(int i=1;i<=60;i++)
4	for(int j=1;j<=i;j++)
5	if(d[i]&(1<<(j-1)))d[i]^=d[j-1];
6	}
7	ll k_th(ll k)
8	{
9	if(k==1&&tot<n)return 0;//特判一下，假如k=1，并且原来的序列可以异或出0，就要返回0，tot表示线性基中的元素个数，n表示序列长度
10	if(tot<n)k--;//类似上面，去掉0的情况，因为线性基中只能异或出不为0的解
11	work();
12	ll ans=0;
13	for(int i=0;i<=60;i++)
14	if(d[i]!=0)
15	{
16	if(k%2==1)ans^=d[i];
17	k/=2;
18	}
19	}

判断能否被当前线性基中元素异或得到

把它尝试插入进线性基里面去，假如可以插入，说明不能异或得到，假如插不进去，说明能异或得到

题集

参考博客

“https://blog.csdn.net/a_forever_dream/article/details/83654397"