本文主要是介绍线性基（处理集合异或的强力工具），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
看了好多篇关于线性基的博客，只是说明了怎么求线性基，但是大都没有说明为什么这样求线性基。
定义：
有一个集合 S = {a1,a2...,an}，T的满足下面条件的一个最小子集A = {a1,a2,....,ak}
A的所有子集的异或和的值域与T的所有子集的异或和的值域相同，那么A就是T的线性基。
预备知识：
1、张成：S的所有子集，其异或和的所有可能的结果组成的集合，为S的张成，记作span(S)。
2、线性相关：对于一个集合S，如果存在一个元素Sj，去除这个元素后得到的集合S'的张成span(S')中包含Sj，即SJ∈span(S')，则称集合S是线性相关的。如果不存在这样的Sj，那么集合S就是线性无关的。
3、线性基：有了上面两个名词，我们还可以这样定义线性基。
（1）A ⊆ span(S)
（2）A是线性无关的
则集合A是集合S的线性基。
性质：
1、A是一个集合的线性基，那么它的任何真子集都不可能是线性基；
2、S中所有的向量都可以按唯一的方式表达为 A 中元素的线性组合（也就是异或和）。
构造：
我们令集合中的数为a1,a2,....,an，b[ ]数组用来存储线性基里面的数。（下面的二进制的位数下标从0开始）
第一种情况：找到ai的最高位，假如是第j位，如果b[j]还没有数，即b[j] = 0，那么现在b数组中的数的张成肯定不包含ai，那么我们就可以b[j] = a[i]，然后利用已经在线性基里的最高位小于j的把b[j]二进制中的1给消掉，具体就是 b[j] ^= b[k] ( k < j && b[j]的第k位为1 && b[k] != 0) ,然后用同样的方法把大于j的也消掉。
第二种情况：找到ai的最高位，假如是第j位，如果b[j]已经有数，就判断现在线性基的张成span(a1,a2...,ai-1)包不包含ai，如果包含，那么ai就没有必要加进线性基。怎么判断呢，我们如果ai的第j位为1且b[j] != 0，那么我们就把ai的值异或上b[j]，依次往后判断，直到ai当前的最高位对应的b[j] == 0，就可以把ai加入线性基，执行上面第一种情况的操作，或者ai为0，就丢掉ai。
代码如下：
void create()
{for(int i=1;i<=n;i++){for(int j=60;j>=0;j--){if((1LL<<j)&a[i]){if(b[j] != 0)a[i] ^= b[j];else{b[j] = a[i];for(int k=j-1;k>=0;k--)if(((1LL<<k)&b[j]) && b[k])b[j] ^= b[k];for(int k=j+1;k<=60;k++)if(((1LL<<j)&b[k]))b[k] ^= b[j];break;}}}}
}这段代码是维护一个对角矩阵，加入一行之后，先用下面的行消自己，然后再用自己去消上面的行。
我们来演示一下这个过程：
加入n = 5，a = {7,1,3,4,5}
初始矩阵：
0 0 0
0 0 0
0 0 0
插入7之后：
1 1 1
0 0 0
0 0 0
插入3之后，为了维护对角矩阵，把7的低位消掉：
1 0 0
0 1 1
0 0 0
插入1之后，把1上面的行的低位都消掉：
1 0 0
0 1 0
0 0 1
然后就发现后面那几个数都已经包含在b数组的张成里了，加不进去了。
上述过程是把线性基维护成一个对角矩阵，其实我们还有一种代码量比较少的线性基的构造方法，就是只把矩阵消成上三角矩阵，这样的话同样可以知道哪一位存在于线性基内。
线性基的操作：
我们把线性基封装成一个结构体，这样使用起来方便一点：
struct LineBasis
{LL b[66];LL p[66];int cnt;int max_b = 62;LineBasis(){memset(b,0,sizeof(b));memset(p,0,sizeof(p));cnt = 0;}
}这里的b数组就是用于存线性基里的数，这个cnt是记录线性基里面有多少个数。
那么这个cnt有什么作用呢，2的cnt次幂就是这个线性基所有子集异或和能构成的不同元素的个数（这里包括零）。
max_b是最大那个数二进制的长度
下面介绍他的各个函数：
1、插入
上面虽然展示了一种线性基的构造方法，那个方法可以提现出线性基的性质，但是下面我们用它比较方便的写法：
bool Insert(LL val){for(int i=max_b;i>=0;i--){if((1LL<<i)&val){if(b[i] == 0){b[i] = val;break;}val ^= b[i];}}if(val > 0)cnt++;return val > 0;}2、合并：
把一个线性基里的元素一个一个的Insert到另一个里面，就完成了合并。
LineBasis Merge(LineBasis n1,LineBasis n2){LineBasis ret = n1;for(int i=0;i<=max_b;i++)if(n2.b[i])ret.Insert(n2.b[i]);return ret;}线性基的用途：
1、求一组数所有组合能构成的不同异或和的个数：
求出这组数的线性基，线性基里数的个数为cnt，答案就为2的cnt次幂
hihocoder1723 子树统计
2、存在性：
查询x是否存在于异或集合中，跟上面构造方法的思想相似，从高位到低位扫描x位1的二进制位，扫到第i位时，x ^= b[i]，如果最后x变为0，则存在，否则不存在。
3、最大值：
求异或集合中的最大值
如果消成对角矩阵的话，直接把线性基中的所有元素异或起来即可。但是对于上三角矩阵，异或之前判断一下是否能变大。
还可以求一个数x与集合中某些数异或的最大值，只用把初值设为x就行了，单纯求最大值时最初始值设为0.
LL QueryMax(LL x){LL ans = x;for(int i=max_b;i>=0;i--)if((ans^b[i]) > ans)ans ^= b[i];return ans;}4、最小值：
最小值就是最低位上的线性基。
LL QueryMin(){for(int i=0;i<=max_b;i++)if(b[i])return b[i];return 0;}5、k小值
这时候用构造出的上三角矩阵就不能解决这个问题了，我们要把上三角矩阵变换成对角矩阵，然后再把不为零的都按顺序拿出来。这时候矩阵已经变成对角矩阵（至少是行最简形矩阵），我们异或上某一行的值，答案就会变大一点。我们可以想象，从一个数组 a = {8,4,2,1}中选出几个，求能组成第k小的值是多少，利用二进制的性质，如果k的二进制第i位为1，我们就加上数组里第i大的数。这里的异或上一个值也会变大一点，所以可以用同样的思想。具体看下面代码
void rebuild(){for(int i=max_b;i>=0;i--)for(int j=i-1;j>=0;j--)if(b[i]&(1LL<<j))b[i] ^= b[j];cnt = 0;for(int i=0;i<=max_b;i++)if(b[i])p[cnt++] = b[i];}LL kthquery(LL k){LL ans = 0;if(k>=(1LL<<cnt))return -1;for(int i=max_b;i>=0;i--)if(k&(1LL<<i))ans ^= p[i];return ans;}总的模板：
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long longusing namespace std;struct LineBasis
{LL b[66];LL p[66];int cnt;int max_b = 62;LineBasis(){memset(b,0,sizeof(b));memset(p,0,sizeof(p));cnt = 0;}bool Insert(LL val){for(int i=max_b;i>=0;i--){if((1LL<<i)&val){if(b[i] == 0){b[i] = val;break;}val ^= b[i];}}if(val > 0)cnt++;return val > 0;}LineBasis Merge(LineBasis n1,LineBasis n2){LineBasis ret = n1;for(int i=0;i<=max_b;i++)if(n2.b[i])ret.Insert(n2.b[i]);return ret;}LL QueryMax(LL x){LL ans = x;for(int i=max_b;i>=0;i--)if((ans^b[i]) > ans)ans ^= b[i];return ans;}LL QueryMin(){for(int i=0;i<=max_b;i++)if(b[i])return b[i];return 0;}void rebuild(){for(int i=max_b;i>=0;i--)for(int j=i-1;j>=0;j--)if(b[i]&(1LL<<j))b[i] ^= b[j];cnt = 0;for(int i=0;i<=max_b;i++)if(b[i])p[cnt++] = b[i];}LL kthquery(LL k){LL ans = 0;if(k>=(1LL<<cnt))return -1;for(int i=max_b;i>=0;i--)if(k&(1LL<<i))ans ^= p[i];return ans;}
};int a[11000];
int main(void)
{int n,i,j;LineBasis s;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a[i]);s.Insert(a[i]);}return 0;
}/*
5
7 1 4 3 5
*/如有错误，欢迎指出。
这篇关于线性基（处理集合异或的强力工具）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
