学习博客：https://blog.csdn.net/a_forever_dream/article/details/83654397
首先说说线性基是什么：
线性基，顾名思义，是一种线性的数，是一个序列按照某种方式处理之后得到的产物，并且有如下性质：
1.原序列里面的任意一个数都可以由线性基里面的一些数异或得到。
2.线性基里面的任意一些数异或起来都不能得到
3.线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的
下面看一下线性基的求法：
for(int i=34;i>=0;i--) { if(x&(1ll<<i))//这一位为1 { if(!basis[i])//还没有存过这一位 { basis[i]=x;break; } x^=basis[i]; } }
下面看一下线性基的一些常用的用法：
求最大值：求一个序列中，取若干个数，使得他们的异或和最大
首先构造出这个序列的线性基，然后从线性基的最高位开始，贪心的方法得到最大值
代码：
ll ans() { ll anss=0; for(int i=50;i>=0;i--)//记得从线性基的最高位开始 if((anss^d[i])>anss)anss^=d[i]; return anss; }
求最小值：最小值显然线性基中就是最小的一个元素，这就不用说了吧
求第K小的值：求一个序列中，取若干个数，使得他们的异或值在所有异或出来的数中第K小
首先要对线性基进行处理，对于每一个d[i]，枚举j=i~1，如果d[i](2)的第j位为1，那么d[i]异或d[j]
最终得到的线性基大概是这样的：
（x表示0或1）：
1xxxx0xxx0x
1xxx0x
1x
看代码：
void work()//处理线性基 { for(int i=1;i<=60;i++) for(int j=1;j<=i;j++) if(d[i]&(1<<(j-1)))d[i]^=d[j-1]; } ll k_th(ll k) { if(k==1&&tot<n)return 0;//特判一下，假如k=1，并且原来的序列可以异或出0，就要返回0，tot表示线性基中的元素个数，n表示序列长度 if(tot<n)k--;//类似上面，去掉0的情况，因为线性基中只能异或出不为0的解 work(); ll ans=0; for(int i=0;i<=60;i++) if(d[i]!=0) { if(k%2==1)ans^=d[i]; k/=2; } }
如何判断一个数是否能被当前线性基中的元素异或得到
把它尝试插入进线性基里面去，假如可以插入，说明不能异或得到，假如插不进去，说明不能异或得到 （原理然而上面已经讲了）