前置知识：
（今天刚知道的
#acm：异或满足结合律，交换律，x ^ x = 0；
#线性代数关于最大无关组的基本知识
——-我是正文——
给定一个数组a1,a2,a3,a4,a5..
数组a的线性基b为b1,b2,b3
线性基就是线性代数里面的最大无关组，所以满足最大无关组的性质
性质一：比如线性基可以表示一组数里的所有元素，也就是说，可以用线性基的组合去凑出其他元素
bi必定可以写成
的形式，其中Xi是系数，且表达方式是唯一的。
性质二：再比如线性基里面挑选任意元素，必定不能组合出0
这是因为若a1 ^ a2 ^ a3 ^ .. an=0
根据XOR的性质有：当且仅当x ^ x =0，那么x就可以写成: a1 ^ a2 … ^ ai = ai+1 ^ ai+2 … ^ an = x
那么x就有两种表示方式，这和表达方式是唯一的矛盾。
性质三:一个数列可能有多个线性基，但是线性基里数的数量一定唯一，而且是满足性质一的基础上最少的
这跟一组数可能有若干个最大无关组，但是数量肯定是确定的，并且是最少的是一样的，可以用线性代数的角度理解。
—–摘自某谷，从XOR的角度理解
除了这种普通的性质以外，线性基还满足：
每个数的最高位在的位置互不相同，这就是说:
1 0 0 0 1 0
1 1 0 1 0
1 0 0 1
是合理的（先不管满不满足其他，但是:
1 0 0 0 1 0
1 0 1 0 1
1 1 0 1 0
就不可以，因为有两个元素的最高位相同了。
先介绍数x的插入过程：
// 将一个数插入线性基
void ins(ll x){
for(ll i=62;i>=0;i--){
if(x&(1ll<<i)){
if(!p[i]) {p[i]=x,cnt++;break;}
else x^=p[i];
}
}
}
考虑：如果x能够被线性表出，那么x会表达成a1 ^ a2 ^ a3 ^ a4 = 0
那我们就去模拟这个线性表出的过程，如果不能被线性表出，也就是说在某一位有p[i]==0，那我们就加入，and 给它break掉了啦
观察x的插入过程，如果最高位相同，x会被^掉，所以当前位不可能有两个1。
（这里的理解自己觉得会有点问题，有bug请指正
—–讲解一下代码~
check一个数能否被线性表出：
ll aks(ll x){
for(ll i=62;i>=0;i--)
if(x&(1ll<<i)) x^=p[i];
return x==0;
}
（细心的读者可以发现和上面，ins(x)的代码是很像的~
3.
求异或和最大值，原理是基于贪心，因为
所以从高到低位枚举，当前能选的话尽量选
// 按位贪心，高位的权重一定是大于(小于它的所有位的和 )
ll askmx(){
ll ans=0;
for(ll i=62;i>=0;i--)
if((ans^p[i])>ans) ans^=p[i];
return ans;
}
查询第k小:
首先rebuild一个数组，把上面处理出来的线性基再进行一个操作，使得尽量是这种形式:
1 0 0 0 0
1 0 0 0
1 0
如何变成这种形式？
对于p[i],如果 : p[i]&(1<<j ) ，就是说如果我们处理出的线性基p[i]在第j位（j-1）上有1，那么就可以把
p[i] -> p[i]^p[j]，把当前位上的1消掉，你可能奇怪为什么这么处理完还满足上面所述的种种性质?
可以这么yy：其实对于p[i]来说，我们看重的是它的第i位（所以这也是为什么我们枚举j从i-1开始），那么其他位：
假设p[i]在经过一系列操作，异或上x1,x2,x3…xn后变成了p[i]’,我们使用p[i]‘来代替p[i]一定是对的，还更方便
这是因为你还可以再把p[i]’异或上x1,x2,x3…xn给它变回去
处理出这样的d数组后，如何查询第k小？
首先讨论边界（肯定不能大于1<<2的（线性基个数））
然后：
ll ans=0;
for(ll i=62;i>=0;i--)
if(k&(1ll<<i)) ans^=d[i];
return ans;
哇，为什么是对的？？？为什么？？？虽然直觉看起来很真（划掉）
这段证明说的是两数之间的比较其实比的是从高到低第一个不同的位的大小（有点像字典序）
所以当异或上第i位（有值的第i位，也就是不为0）后，前面i-1个如何组合，也无法比当前的大
那前面的组合就是2的i次方，第j位同理…
这样枚举一遍后（正序逆序都可以，因为二进制拆分是唯一的），我们得到的数前面有:
2的a0次方+2的a1次方+2的a2次方….（就是k的二进制拆分啦）~
void rebuild(){
cnt=0;top=0;
for(ll i=62;i>=0;i--)
for(ll j=i-1;j>=0;j--)
if(p[i]&(1ll<<j)) p[i]^=p[j];
for(int i=0;i<=62;i++) if(p[i]) d[cnt++]=p[i];
}
ll kth(ll k){
if(k>=(1ll<<cnt)) return -1;
ll ans=0;
for(ll i=62;i>=0;i--)
if(k&(1ll<<i)) ans^=d[i];
return ans;
}
完整模板：
瓶颈是n²，所以数据可以开到5000
(也许高斯消元可以做得更好，但是还没学x
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll top,p[100],d[100],cnt;
// 将一个数插入线性基
void ins(ll x){
for(ll i=62;i>=0;i--){
if(x&(1ll<<i)){
if(!p[i]) {p[i]=x,cnt++;break;}
else x^=p[i];
}
}
}
//查询一个元素是否可以被异或出来
ll aks(ll x){
for(ll i=62;i>=0;i--)
if(x&(1ll<<i)) x^=p[i];
return x==0;
}
// 按位贪心，高位的权重一定是大于(小于它的所有位的和 )
ll askmx(){
ll ans=0;
for(ll i=62;i>=0;i--)
if((ans^p[i])>ans) ans^=p[i];
return ans;
}
//查询异或第k小
void rebuild(){
cnt=0;top=0;
for(ll i=62;i>=0;i--)
for(ll j=i-1;j>=0;j--)
if(p[i]&(1ll<<j)) p[i]^=p[j];
for(int i=0;i<=62;i++) if(p[i]) d[cnt++]=p[i];
}
ll kth(ll k){
if(k>=(1ll<<cnt)) return -1;
ll ans=0;
for(ll i=62;i>=0;i--)
if(k&(1ll<<i)) ans^=d[i];
return ans;
}
int n;
ll a[100];
int main(){
cin>>n;
for(int i=1;i<=n;i++) {cin>>a[i];ins(a[i]);}
cout<<askmx()<<endl;
}
原文地址：http://www.cnblogs.com/liyishui2003/p/16823176.html
