线性基

概念定义

1.张成：从集合 \(S\) 中选出任意多个数异或和的可能的结果的集合，记作 \(span(S)\)

2.线性相关：对于一个集合 \(S\) ，若其中存在一元素 \(S_j\) 使除去该元素后得到的集合 \(S'\) 的张成 \(span(S')\) 中包含 \(S_j\) ，即其余数中若干个数的异或和为 \(S_j\) ，则称 \(S\) 线性相关，反之则称它线性无关

3.线性基：

我们称集合 \(B\) 为 集合 \(S\) 的线性基，当且仅当 \(S \subset span(B)\) ，即 \(S\) 为 \(B\) 的张成的子集；且 \(B\) 线性无关

\(|B|\)称为线性基的长度

\(B\) 是极小的满足线性基性质的集合，即 \(B\) 的任何真子集都不会是 \(S\) 的线性基

\(B\) 的任何元素都可以唯一表示为 \(S\) 中若干元素的异或和

构造

将 \(S\) 中每个元素转换为二进制，从高位往低位扫，对于 \(p\) 的第 \(x\) 位为 \(1\) 的，若 \(a_x\) 为 \(0\) ，令 \(a_x=p\) ，否则令 \(p=p\ xor\ a_x\) 并继续扫

//3812
for(int i=1;i<=n;++i)
{
	long long x=s[i];
	for(int j=50;j>=0;--j)
	{
		if(x&(1ll*1<

//3812
for(int i=50;i>=0;--i) if(ans<(ans^a[i])) ans^=a[i];