线性基主要是解决一个集合中子集的异或和问题。

可以用来求子集异或和的第k大或者是否能异或出某个数。

时间复杂度 $O\left(nlogn\right)O(nlogn)$O(nlogn)

Tips：由于线性基里很多操作涉及到二进制的位移，切记用 1ll<<x 而不是 1<<x 。前者返回 long long类型，后者返回 int 类型。

模板如下：

const int N=1e6+10;
const int LOG_N=60;
int n,pos,d[LOG_N+5],a[N],th[LOG_N+5];
bool is;
void init(){
    is=false;
    pos=0;
    for(int i=0;i<=LOG_N;i++) {
        d[i]=0;
        th[i]=0;
    }
}

// 建立对应数组，d[x]为二进制下最高位是x
void build(){
    sort(a,a+n,greater<int>());
    for(int i=0;i<n;i++){
        int x=a[i];
        for(int j=LOG_N;j>=0;j--){
            if(x&(1ll<<j)){
                if(d[j]==0){
                    d[j]=x;
                    break;
                }else{
                    x^=d[j];
                }
            }
        }
        if(x==0) is=true;
    }
}

// 异或化简，求第k大必须步骤
void rebuild(){
    for(int i=LOG_N;i>=0;i--){
        for(int j=i-1;j>=0;j--){
            if(d[i]&(1ll<<j)){
                d[i]^=d[j];
            }
        }
    }
    for(int i=0;i<=LOG_N;i++){
        if(d[i]) th[pos++]=d[i];
    }
}

// 查询异或子集第k大，如果能异或出0，相当于查异或子集第k-1大
int query(int k){
    if(is) k--;
    if(k>=(1ll<<pos)) return -1;
    int now=0;
    int shu=0;
    while(k){
        if(k&1) shu^=th[now];
        now++;
        k>>=1;
    }
    return shu;
}