定义：
线性基是向量空间的一组基，通常可以解决有关异或的一些题目。是一个数的集合，并且每个序列都拥有至少一个线性基，取线性基中若干个数异或起来可以得到原序列中的任何一个数。
<font color=red,size=4>线性基的值域与原数组的值域相同，此处的值域是指任意数异或所能得到的值。
性质：
1.原序列里面的任意一个数都可以由线性基里面的一些数异或得到；
2.线性基里面的任意一些数异或起来都不能得到 (0)；
3.线性基里面的数的个数唯一，并且在保持性质 (1) 的前提下，数的个数是最少的；
线性基的构造：
比如一列数：(2,9,10,17)，(d[i]) 表示线性基中的元素，即二进制表示中最高位为第 (i) 位的数，唯一。
各自二进制表示为：
(2 o 00010)
(9 o 01001)
(10 o 01010)
(17 o 10001)
即：
我们从二进制位的最高位开始：
第 (4) 位：
只有 (17) 一个，把 (17) 加入线性基中；
第 (3) 位：
先找到 (10) ，将其加入，然后有发现了 (9)，因为 (d[3]) 是唯一的，所以不能将 (9) 加入。但是我们可以将 (9) 用 (9igotimes 10=3) 来表示，这样当我们需要 (9) 时，可以用 (3igotimes 10) 得到。
这样原矩阵就变成：
第 (2) 位：
全部为 (0)，跳过。
第 (1) 位：
先发现 (3) ，加入。所以 (2) 不能直接加入，同样变换为 (2igotimes 3=1)。
第 (0) 位：
只有 (1)，加入。
所以
完成改造。
代码实现：
void insert(long long x) {
for (int i = 66; i>=0; i--) {
if (!(x >> i)) // x的第i位是0
continue;
if (!d[i]) {
d[i] = x;
break;
}
x ^= d[i];
}
}
性质证明：
性质1：
其实改造过程就可以证明。
如果把一个数插入，那么这个数肯定能被表示；
如果不插入，那么这个数一定会用其他数异或后插入。
如果 (x) 不能成功插入线性基，一定是因为当前线性基里面的一些数异或起来可以等于 (x)。
性质2：
由性质1。
性质3：
见参考博客1。
实际应用：
1.求最大值：
LOJ 113. 最大异或和
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[70],d[70];
void add(ll x)
{
for(int i=60;i>=0;i--)
{
if((x>>i)&1)
{
if(d[i]==0)
{
d[i]=x;
break;
}
x^=d[i];
}
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
ll ans=0;
for(int i=1;i<=n;i++)
add(a[i]);
for(int i=60;i>=0;i--)
{
if((ans^d[i])>ans)//异或的优先级低
ans^=d[i];
}
printf("%lld
",ans);
return 0;
}
2.判断一个数是否能被当前线性基中的元素异或得到
把它尝试插入进线性基里面去，假如可以插入，说明不能异或得到，假如插不进去，则说明可以异或得到
xor序列
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll d[35];
void add(ll x)
{
for(int i=32;i>=0;i--)
{
if((x>>i)&1)
{
if(d[i]==0)
{
d[i]=x;
break;
}
x^=d[i];
}
}
}
bool solve(ll num)
{
for(int i=32;i>=0;i--)
{
if((num>>i)&1)
{
if(d[i]==0)
return 0;
num^=d[i];
}
}
return 1;
}
int main()
{
int n,q;
ll a,x,y;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a);
add(a);
}
scanf("%d",&q);
while(q--)
{
scanf("%lld%lld",&x,&y);
if(solve(x^y))
printf("YES
");
else
printf("NO
");
}
return 0;
}