说在前面
前天，atcodering……看到一道题：给出一大堆异或关系，然后连边，求生成树。
我当时就懵了，这咋做啊？随便猜了一个结论，然后 wa+tle 炸飞了。
赛后，讨论：这不是线性基吗？
然后就有了这篇笔记。
线性基
这是什么
首先，线性基是线性的，是线性代数的，线性基是一个描述一个集合的异或性质的集合。具有如下性质：
- 线性基值域与原集合相同；
- 原集合中的所有数都可以由线性基异或得到；
- 线性基是满足上述条件集合中，大小最小的一个。
举个例子：数列 (1,2,9,10,17) 的一个合法线性基就是 ({1,2,9,17})。
线性基有许多喜闻乐见的性质：
性质 ( ext{I})：线性基中，不存在子集使子集内所有数异或和为 (0)。
这个性质非常重要，关系到后面线性基的构造和应用。
考虑反证：如果存在，那么一定可以删掉一个元素。同时，这个元素的等价就是原子集中剩下的元素异或和。与线性基的最小性矛盾。
还是刚刚那个例子：如果出现了 ({1,2,9,10}) 这样的线性基，可以发现整体异或和为 (0)。
此时，我们可以将 (10) 删掉，原来包含 (10) 的式子就用 (1operatorname{xor} 2operatorname{xor} 9) 代替。
由于异或自己为零，异或零为本身，则这样的替换一定是合法的。
性质 ( ext{II})：线性基中数两两不同。
这就是性质 ( ext{I}) 的简单推论了。
性质 ( ext{III})：存在线性基，使得不存在两个数二进制最高位位置相同。
这也是一个很重要的性质，因为 OI 中使用的线性基大多满足这个性质，这样可以根据二进制最高位来存储。
显然，如果有两个数二进制最高位位置相同，那么可以使其中一个成为两者的异或和。这样可以使二进制最高位位置变小，由于整数的离散性，必然可以在有限步内完成操作，即一定存在。
我们不妨把这样的线性基成为「最优线性基」，下文的线性基若无特别说明均指最优线性基。
性质 ( ext{IV})：线性基大小至多为 (leftlceillog_2 max{S} ight ceil)
因为每一位都至多有一个，所以显然。这是线性基的空间复杂度。
如何构造
构造线性基是一个很重要的过程。一般采用动态构造，即插入线性基。可以分解成如下两个步骤：
- 检查该数能否由现有线性基得到；
- 如果否，则将其插入线性基。
还记得「最优线性基」的性质吗？每个最高位至多一个数。那么，我们只需要从高到低遍历线性基，如果目前要插入的数 (x) 最高位存在数，则将 (x) 赋成两数异或和，如果遍历完了（最低位也被异或掉了，显然此时 (x=0)），则说明 (x) 可以由线性基得到。
否则，如果在某一时刻，(x) 最高位所对应的数为空，则易证线性基无法得到 (x)，直接将 (x) 插入该位即可。
代码非常简洁：
int f[n];
void ins(int x)
{
for (int i = n-1; i >= 0; i--)
if ((x >> i))
{
if (f[i] == 0)
{
f[i] = x;
return 0;
}
x ^= f[i];
}
}
由此可见线性基的复杂度是 (mathcal{O}(nlog n))，非常喜闻乐见。
有什么用
一句话：很有用。线性基可以解决很多整数异或问题。
异或最大问题
给定 (n) 个数，求这 (n) 个数经过异或计算后能得到的最大值。
我们可以先构造这 (n) 个数的线性基。显然这些数的异或就等价于线性基的异或。
那么，怎样通过线性基求得异或最大值呢？考虑贪心。从高往低扫，如果当前值可以使异或值变大就选择，否则不选。
显然，如果我们选择了这个让异或值变小的数，假设其最高位位置为 (x), 则易证此时异或值的第 (x) 位肯定为 (0)。
根据「最小线性基」的性质，后面所有的数均不能使这一位的异或值为 (0)。所以不选就是最好的选择（突然好有哲理.jpg）。
代码比构造还简洁，这里就不放了，不妨顺带做一做板子题？
例题
AtCoder zone2021_f：Encounter and Farewell
题目链接：https://atcoder.jp/contests/zone2021/tasks/zone2021_f。
给定 (N) 个节点（从 (0) 开始编号）和一个大小为 (M) 的集合 (A)，如果两个节点 (i)，(j) 满足 (ioperatorname{xor} jin A)，则这两个节点之间没有连边，反之则有边。判断是否连通，如果是，求一棵生成树；否则输出 -1。
首先我们将不可行集 (A) 转变成可行集。然后我们可以发现一个结论：每次选择一个数 (x)，加入所有满足 (ioperatorname{xor} j=x) 的边，则连通块数量就会减半。
但是，经过进一步的观察，我们发现，当同时加入 (x)，(y) 时，再加入 (xoperatorname{xor}y) 就无效了。显然对于原来的 (i)，先加入的 (x)，(y) 会产生如下路径：(i ightarrow ioperatorname{xor} x ightarrow ioperatorname{xor}xoperatorname{xor}y)，如果再加入 (xoperatorname{xor} y) 就重复了。
所以我们考虑构造可行集的线性基，如果线性基内的数使得连通块数减到 (1) 就是合法的，然后就可以用形如 Kruskal 的方法随便生成一棵生成树即可。
当然这道题证明结论需要线性基，实际上可以暴力，但我不会。
Code：https://atcoder.jp/contests/zone2021/submissions/22257625。