Part 0：前置知识
线性空间是一个关于以下两个运算封闭的向量集合：
- 向量加法 \(a+b\)。
- 标量乘法 \(k*a\)。
给定一个向量集合 \(A=\{a_1,a_2,\dots,a_k\}\)，若向量 \(b\) 能由 \(a_1,a_2,\dots,a_k\) 经过向量加法和标量乘法运算得出，则称向量 \(b\) 能被向量 \(a_1,a_2,\dots,a_k\) 表出。\(a_1,a_2,\dots,a_k\) 能表出的所有向量构成一个线性空间，称作 \(A\) 的张成空间，记作 \(\operatorname{span}(A)\)。\(A\) 被称作这个线性空间的生成子集。
任意选出线性空间的若干个向量，如果其中存在一个向量能被其它向量表出，则称这些向量线性相关，否则称这些向量线性无关。
线性无关的生成子集被称为线性空间的基底，简称基。基的另一种定义是线性空间的极大线性无关子集。一个线性空间的所有基包含的向量个数都相等，这个数被称为向量空间的维数。
Part 1：OI 中的线性基
在 OI 中，线性基一般用于解决与异或有关的问题。
异或可以看作 \(\bmod 2\) 意义下的向量加法。因此不难直接将原有的定义推广到异或上。
规定：记 \(k\) 为二进制位长，\(cnt\) 为线性基中基底的个数。
基的构建
从矩阵的角度理解，对于一个 \(n\times m\) 的矩阵，把每一行看作长度为 \(m\) 的行向量。将矩阵看作“系数矩阵”进行高斯消元，得到一个简化阶梯形矩阵。显然，简化阶梯形矩阵的所有非零行向量线性无关。而消元过程又不改变行向量的张成空间。于是，简化阶梯形矩阵的所有非零行向量就是该线性空间的一个基。
现在给定二进制数集合 \(V\)，求 \(\operatorname{span}(V)\) 的一组解。
我们集合 \(V\) 写成一个 \(|V|\) 行 \(k\) 列的 \(01\) 矩阵，高斯消元即可。
市面上常见的线性基写法采用增量法，逐个加入向量，若能被之前的基表出则不加入。复杂度 \(\mathcal{O}(|V|k)\)。（其实本质上一样）。
struct Linear_Base
{
LL e[S];
Linear_Base(){memset(e,0,sizeof(e));}
void insert(LL x)
{
for(int i=61; i>=0; i--)
if(x&(1LL<<i))
{
if(e[i])
x^=e[i];
else
return e[i]=x,void();
}
}
}
张成空间判定问题
给出一个线性无关的二进制数集合 \(B\)，询问 \(a\) 是否在 \(\operatorname{span}(B)\) 中。
\(a\in \operatorname{span}(B)\) 等价于 \(a,B\) 线性相关。类似基的构建一样将 \(a,B\) 放在一起消元即可判断。
最大子集异或值
要求实现一个函数 \(\operatorname{query}(x)\)，表示查询 \(x\) 与线性基的最大异或和。那么最大子集异或值就是 \(\operatorname{query}(0)\)。
从高位到低位考虑基，若异或后变大，则异或。
由贪心可证明正确性。
LL query(LL x)
{
for(int i=51; i>=0; i--)
if((x^e[i])>x)
x^=e[i];
return x;
}
\(k\) 小子集异或和
若原有的集合 \(V\) 是线性无关的，则异或不到 \(0\)，能得到异或值的个数是 \(2^{cnt}-1\) 。（有时允许选空集则无需考虑）。
反之，能得到 \(0\)，则为 \(2^{cnt}\) 个。
特判一下 \(0\)，然后重构线性基，将三角基消成对角基，即令 \(e_i\) 的 \(0\sim i-1,i+1\sim k-1\) 都为 \(0\)。并从小到大排序记为 \(b_0,b_1,\dots,b_{cnt}\)。
将 \(k\) 按二进制展开，若第 \(i\) 位为 \(1\)，则答案异或上 \(b_i\)。证明同按位贪心。
void rebuild()
{
int tot=0;
for(int i=0; i<=61; i++)
{
if(!e[i])
continue;
for(int j=i-1; j>=0; j--)
if(e[i]&(1LL<<j))
e[i]^=e[j];
tmp[tot++]=e[i];
}
}
LL ask(LL k)
{
if(k>=(1LL<<cnt))
return -1;
LL res=0;
for(int i=cnt-1; i>=0; i--)
if(k&(1LL<<i))
res^=tmp[i];
return res;
}
线性基合并
由于线性基只有 \(\mathcal{O}(k)\) 个元素，所以暴力插入即可，时间复杂度 \(\mathcal{O}(k^2)\)。
例题
P3265 [JLOI2015] 装备购买
就是求一个价钱最小的极大线性无关子集。同 kruskal 一样按价钱从小到大加入，求解线性基即可。
P4301 [CQOI2013] 新Nim游戏
先手想要找到一个极大的集合，使后手面对这个集合时，无法找到一个子集满足异或和为 \(0\)。因此，这个集合一定是线性无关的 。
P3292 [SCOI2016] 幸运数字
对每个节点 \(x\) 维护 \(g_{x,i}\) 表示从 \(x\) 向上走 \(2^i\) 步所到达的所有节点（不包括 \(x\)）的线性基。由于可重复贡献直接树上 RMQ 即可。
P4839 P 哥的桶
使用线段树维护线性基合并。复杂度 \(\mathcal{O}(n\log n\log ^2 V)\)。
标签：矩阵,异或,子集,线性,operatorname,向量,小记 From： https://www.cnblogs.com/xishanmeigao/p/18040384