线性基是向量空间的一组基，通常可以解决有关异或的一些题目。

定义

在了解线性基之前，需要知道什么是异或和，张成，线性相关

异或和

无符号整数\(Z\)集合，全部元素异或起来\(xor(Z) = Z_1\oplus Z_2 \oplus Z_3\oplus\cdots\oplus Z_n\)

张成

设\(T\subseteq Z\)，所有的子集T的异或和组成的集合称为集合\(Z\)的张成，记作\(span(Z)\)

线性相关

对于一个集合\(Z\)，如果存在一个元素\(Z_i\)，使得，\(Z\)在去除这个元素之后也存在\(Z_i \in span(Z^{’})\)关系，则称集合\(Z\)线性相关。（线性相关的的集合去除掉某个元素集合的张成不变）
反之不存在这样的元素\(Z_i\)则就是线性无关

线性基

\(B\)若是\(S\)的线性基应该满足

  1. \(S \subseteq span(B)\) \(S\)是\(B\)的张成的子集
  2. \(B\)是线性无关的

\(B\)里面元素的个数就是线性基的长度
线性基的基本性质:

  1. 线性基不唯一
  2. 线性基没有异或和为 \(0\) 的子集。
  3. 线性基是满足性质 \(5\) 的最小的集合。
  4. 线性基中每个元素的二进制最高位互不相同。
  5. 线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。
  6. 线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。

代码实现

操作

  1. 求任意子集\(\oplus\)最小值: 等于最小的主元
  2. 求任意子集\(\oplus\)最大值: 第二种：贪心 构造
  3. 查询\(x\)是否在值域中：将它\(insert\) 如果失败则在值域中
  4. 查询\(x\)是否在值域中: 如果\(x\)能插入线性基，则x不能被当前线性基\(\oplus\)出来
  5. 查询第\(k\)小的值: 把\(k\)进行二进制分解，把1对应位置的主元\(\oplus\)起来 注意这里第\(0\)小就是\(0\)
  6. 求任意子集与\(x\)进行\(\oplus\)的最大值：从高到低贪心，若\(xor\)上\(a[j]\)能变大就更新(\(ans = max(ans,ans\oplus a[j]\)))

构造

  • 低位

现在已经插入的一个数放到了\(a[i]\)，其在更低的二进位\(j\)上为\(1\)，并且\(a[j]\)已经被赋过值了，更新\(a[i] = a[i]\oplus a[j]\)

  • 高位

我们还需要使用插入的数\(a[i]\)来更新高位的\(a[j]\)（\(a[j] = a[j]\oplus a[i]\)）从大到小枚举\(j\)即可

void ins(ll x)
{
	for (int i = 63; ~i; i--)
	{
		if (x >> i & 1)
		{
			if (a[i])
			{
				x ^= a[i];
			}
			else
			{
				a[i] = x;
				//低位
				for (int j = i - 1; ~j; j--)
				{
					if (a[j] and (a[i] >> j & 1))
					{
						a[i] ^= a[j];
					}
				}
				//高位
				for (int j = 63; j > i; j--)
				{
					if (a[j] >> i & 1)
					{
						a[j] ^= a[i];
					}
				}
				return;
			}
		}
	}
	flag = 1;
}

检验存在

  • 一个数能被某个线性基表达出来的话根据异或的性质就会变成\(0\)
bool check(ll x)
{
	for (int i = 63; ~i; i--)
	{
		if (x>>1&1)
		{
			if (!a[i])return false;
			else x ^= a[i];
		}
	}
}

查询异或最小值

  • 直接输出线性基里面的最小值
    \(flag\) 代表是某个已经存在于线性基里面的元素，这样就可以被异或为\(0\)，这样的最小值为\(0\)，所以要特判一下。
ll que_min()
{
	if (flag)return 0;
	for (int i = 0; i <= 63; i++)
	{
		if (a[i])return a[i];
	}
}

查询异或最大值

\(tips\)

  • 若是查询异或上某数的最大值就把初始值改一下即可

原理从高到底遍历线性基，当前考虑到了\(i\),若当前\(ans\)此位置上的数（二进制）为\(0\)，这样我们就可以将其异或起来\(ans = ans \oplus a[i]\)
否则就不操作

ll que_max()
{
	ll ans = 0;
	for (int i = 63; ~i; i--)
	{
		ans = max(ans, ans ^ a[i]);
	}
	return ans;
}

求解第\(K\)小

把\(k\)进行二进制分解，第\(i\)位为\(1\)就更新答案

ll rank_K(int k)
{
	ll ans = 0;
	for (int i = 0; i < n; i++)
	{
		if (k >> i & 1)
		{
			ans ^= a[i];
		}
	}
	return ans;
}

:name