线性基
摸一手线性基
由于线性代数没学好，所以就先不讲线性基的线代部分。
定义
线性基是从一个数集（大小为 \(N\)）构造出的另一个数集（大小为 \(\log _2N\)）。满足线性基中的元素任意异或起来和原数集中元素任意异或起来，两者值域相同。个人理解在异或运算下，线性基是原数集的简化。
比如对于一个数集 \(\{1,2,3\}\) ，它的线性基是 \(\{1,3\}\) 或 \(\{1,2\}\) 或 \(\{2,3\}\)。
构造
我们先来考虑构造，因为有些性质容易由根据构造过程得出。
根据定义，线性基只需要满足线性基的元素任意异或能够得到原数集的任意元素。因为只要能得到原数集的所有数了，那么原数集能通过异或表达的数，线性基也一定能表达。
所以，我们的目的就是构造出一个能表达出原数列中每个数的线性基。我们考虑根据原数集，以增量构造法来构造。
首先，我们将线性基的元素按位排序，即线性基 \(P_1,P_2,P_3\cdots\) 分别表示线性基中元素二进制最高位是第 \(1,2,3\cdots\) 位的元素。每一位只需要一个数。
然后，我们遍历原序列 \(A\)，按以下操作将 \(a_i\) “插入”线性基
-
考虑 \(a_i\) 的二进制最高位 \(i\)，
-
若 \(P_i=0\)，则令 \(P_i\) 为 \(a_i\) 并结束操作。
否则令 \(a_i\) 为 \(a_i\bigotimes P_i\)，返回操作1.
如果退出操作时 \(a_i=0\) 那么说明 \(a_i\) 已经可以被线性基内元素表达出来；
否则则说明线性基中新插入了一个元素。
代码实现
void getp(){//m是原数列大小，n是数的二进制的大小限制
for(int i=1;i<=m;i++)
for(int j=n;j>=0;j--)
if(a[i]&(1ll<
性质
好了，我们来讨论以下线性基的良好性质。
性质1
线性基中的元素任意异或起来和原数集中元素任意异或起来，两者值域相同。
等价于线性基的元素任意异或能够得到原数集的任意元素。
证明：对于一个原数集中的数 \(a_i\)，如果它返回时是 \(0\) ，说明已经可以被操作中异或过的 \(P_j\) 表达出来了，如果不是，那么新加入的这个元素可以和插入之前异或过的那些 \(P_j\) 表达出来 \(a_i\)。
性质2
线性基中元素任意子集的异或和不为 \(0\)。
证明：以子集大小为 \(3\) 为例，假设存在 \(P_1\bigotimes P_2\bigotimes P_3=0\)，那么 \(P_1\bigotimes P_2=P_3\)，而我们由线性基的构造过程可知，这样的 \(P_3\) 是不可能被加入线性基的，故该性质得证。
性质3
一个数集的线性基可能有多个，它们元素不同但大小相同。
并且线性基在满足性质1的条件下大小是最小的。
首先考虑证第一句话。
首先如果所有的原数集元素都成功插入线性基了，显然满足性质3。
如果存在一个元素 \(x\) 没有插入，那么以大小为 \(3\) 的子集为例，存在 \(P_i\bigotimes P_j\bigotimes P_k=x\)，我们如果改变插的顺序就会发现：
\(P_i\bigotimes P_j\bigotimes x=P_k\)
\(P_i\bigotimes x\bigotimes P_k=P_j\)
原本是 \(x\) 插不进去，现在是 \(P_k\) 或 \(P_j\) 插不进去，换言之一个插进去了另一个就会出来。所以线性基的大小是一定的，但元素可能不同。
再考虑第二句话。
考虑线性基的构造过程，因为线性基每个元素都是为了能够表示出原数集中某元素才被添加的，也就是说每个元素都是必要的，所以这样的线性基的元素缺一不可，也就是大小最小。
性质4
任意能被原数集异或表达出来的数在线性基中的异或方式一定。
换言之，就是线性基任意子集异或结果不同。
考虑反证：仍然以大小为 \(3\) 的子集为例，假设存在 \(P_1\bigotimes P_2\bigotimes P_3=P_4\bigotimes P_5\bigotimes P_6\)，那么就有\(P_1\bigotimes P_2\bigotimes P_3\bigotimes P_4\bigotimes P_5\bigotimes P_6=0\)，这与性质2矛盾，故性质4得证。
应用
应用1
查询一个元素能否被一个数集中的元素异或得到。
我们把数集的线性基跑出来，考虑构造线性基的过程，让这个数模拟一遍就可以通过结束后是否为 \(0\) 判断了。
应用2
在一个数集任取子集异或，求最大异或和。
我们只需要从高位到低位贪心地选择就好了，因为线性基中元素最高位都不同，所以只需要考虑最高位最大。
应用3
在一个数集任取子集异或，求最小异或和。
首先跑出线性基，然后我们发现线性基中最小的元素不管异或上其他的哪一个都会变大，所以答案就是线性基中的最小值。
但还有要特判的情况，如果在构造线性基时有返回 \(0\) 的情况，就说明原数集存在异或和为 \(0\) 情况，这种情况直接输出 \(0\)。
应用4
在一个数集任取子集异或和，求第 \(K\) 小异或和。
准确地说，是在所有能异或出的数字中第 \(K\) 小的那一个。
看起来是前两个的加强版，但是好像做不到在前两个的基础上继续做了，所以先写做法，然后理解。