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

它可以用于求解一个集合内的最大异或和，而且效率极高，是O(N log MaxNum)的时间复杂度。

什么是线性基？

对于一个数组\(a_{1},a_{2},a_{3},\cdots a_{n}\)，我们可以用\(x_{1},x_{2},\cdots ,x_{log max\left ( a_{i}\right )}\)来记录第一个二进制下最高位出现在第\(i\)位的数字，并通过这个\(x\)数组，来求出这个数组中的最大异或和。

通俗一点的讲法就是由一个集合构造出来的另一个集合，它有以下几个性质：

线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。

线性基是满足性质 1 的最小的集合。

线性基没有异或和为 0 的子集。

线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。

线性基中每个元素的二进制最高位互不相同。

构造线性基模板（不懂原理上个模板）：

 

 1 void Guass() {
 2     for (int i=1;i<=sz;i++) {
 3         for (int j=62;j>=0;j--) {
 4             if ((A[i]>>j)&1) {
 5                 if (!P[j]) {P[j]=A[i]; break;}
 6                 else A[i]^=P[j];
 7             }
 8         }
 9     }
10     for (int j=0;j<=62;j++) if (P[j]) r++;
11 }

 

版权声明：本文为wsy107316原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/wsy107316/p/13356614.html