线性基学习笔记+模板总结
引入：
一组线性无关的向量可以作为一组基底，用这个基底可以表示空间中的全部向量，而且这个基地的个数是确定的，他们线性无关，加入空间中的其他向量之后，就变得线性相关了。
线性基：
考虑这样的线性基性质（类比我们前面关于基的介绍）：
- 1.原序列里面的任意一个数都可以由线性基里面的一些数异或得到。
- 2.线性基里面的任意一些数异或起来都不能得到0。
- 3.线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的。
一些说明和证明
性质一
首先线性基是如何构造的呢？
我们设有一个数组d，表示序列a的线性基，下标从0开始算。对于序列里面的每一个数，我们尝试将它插入到线性基里面去，具体如何插入这里给出伪代码(x(2)表示x的二进制为)
for i=63 to 0
if(x(2)的第i+1位为1)
{
if(d[i]为0)
{
d[i]=x;
break;
}
else x=x^d[i];
}
有了构造方法，我们就可以知道性质一原理了。如果原序列中的数字不能由线性基异或表示，则与插入方式矛盾。例如异或之后不为0，则插入了d[i]，那么原本的x一定可以由d[i]和线性基中的数异或得到。
x ^ d[a]^....=d[i]
d[i]^d[a]^....=x
如果一个数字不能插入的线性基，那么插入最后是得到0，说明线性基中的一些数与它异或可以得到0，说明这些数异或就可以表示它了（x^y=0,说明x==y）
性质二
性质二反证
如果d[a]d[b]d[c]=0,那么d[a]^d[b]=d[c],说明d[c]可以由d[a]和d[b]表示，在插入中就不会插入d[c]了。
性质三
性质三比较显然，符合基的基本定义，即基中元素个数是确定的，加入其他元素就会线性相关，所以元素个数也是最少的。
acm中的应用
- 最大异或和
- 第 k大异或和/异或和是第几大
- 求所有异或值的和
算法模板
struct Linear_Basis
{
LL b[63],nb[63],tot;
void init()
{
tot=0;
memset(b,0,sizeof(b));
memset(nb,0,sizeof(nb));
}
bool ins(LL x)
{
for(int i=62;i>=0;i--)
if (x&(1LL<<i))
{
if (!b[i]) {b[i]=x;break;}
x^=b[i];
}
return x>0;
}
LL Max(LL x)
{
LL res=x;
for(int i=62;i>=0;i--)
res=max(res,res^b[i]);
return res;
}
LL Min(LL x)
{
LL res=x;
for(int i=0;i<=62;i++)
if (b[i]) res^=b[i];
return res;
}
void rebuild()
{
for(int i=62;i>=0;i--)
for(int j=i-1;j>=0;j--)
if (b[i]&(1LL<<j)) b[i]^=b[j];
for(int i=0;i<=62;i++)
if (b[i]) nb[tot++]=b[i];
}
LL Kth_Max(LL k)
{
LL res=0;
for(int i=62;i>=0;i--)
if (k&(1LL<<i)) res^=nb[i];
return res;
}
}LB;
void work()//处理线性基
{
for(int i=1;i<=60;i++)
for(int j=1;j<=i;j++)
if(d[i]&(1<<(j-1)))d[i]^=d[j-1];
}
ll k_th(ll k)
{
if(k==1&&tot<n)return 0;//特判一下，假如k=1，并且原来的序列可以异或出0，就要返回0，tot表示线性基中的元素个数，n表示序列长度
if(tot<n)k--;//类似上面，去掉0的情况，因为线性基中只能异或出不为0的解
work();
ll ans=0;
for(int i=0;i<=60;i++)
if(d[i]!=0)
{
if(k%2==1)ans^=d[i];
k/=2;
}
}