学习线性基相关

在线性空间中，线性基是一组线性无关的向量组，且在其所在的向量空间中是一个极大线性无关向量组

我们在算法里，可以看作是若干个数的集合

在一个序列中，取其线性基中的任意几个数，可以得到原来序列的任何一个数

线性基中的数都是唯一的

如何构造线性基

贪心的方法

从高位往低位扫，设a[x]为第x位上是1的数，当前要加入的数为p

如果a[x]不存在，则p加入到该位上

如果a[x]存在，则p需异或一遍a[x]，使得p的第x位不是1

从高位往低位扫，可以保证它是类似阶梯型的

void insert(int x)
{
	for(int i=63;i>=0;i--)
	{
		if(!(x>>i))continue;
		if(!p[i])
		{
			p[i]=x;
			break;
		}
		x^=p[i];
	}
}

重构线性基

重构线性基的目的在于查找第k小的异或和

我们依次给第i位的i-1到0异或上对应的a，则可以得到1,10,100，这样子方便我们获得第k小的异或和

但是注意了，这种重构后的线性基无法通过异或获得0，所以如果原来的异或和可以得到0，则需特判一下

void rebuild()
{
	tot=0;
	for(int i=0;i<=63;i++)
	{
		for(int j=i-1;j>=0;j--)
		{
			if((p[i]>>j)&1)p[i]^=p[j];
		}
		if(p[i])d[tot++]=p[i];
	}
}

int get_min(int k)
{
	if(tot!=n)k--;//去掉异或出来是0的情况
	if(k>=(1<<tot))return -1;
	int res=0;
	for(int i=0;i<tot;i++)if((k>>i)&1)res^=d[i];
	return res;
}