线性基

刚认识这个东西，还以为有多么高大上呢

定义#

{% label OI-Wiki版 blue %}

称线性空间 的一个极大线性无关组为 的一组 Hamel 基 或 线性基，简称 基。 规定线性空间 的基为空集。 另外，将 的 维数 记作 , 定义为基的元素个数。

{% label 更通俗易懂一点的版本 blue %}

线性基是一个数的集合，并且每个序列都拥有至少一个线性基，取线性基中若干个数异或起来可以得到原序列中的任何一个数。

性质#

1. 原序列里面的任意一个数都可以由线性基里面的一些数异或得到
2. 线性基里面的任意一些数异或起来都不能得到
3. 线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的

操作#

构造（插入一些数并判断）#

令插入的数为,考虑进制下的最高位

• 若线性基的第位为,则直接在该位插入,退出；
• 若线性基的第位已经有值，则，重复以上操作直到

如果退出时,则此时线性基已经可以表示原先的了；反之，则说明为了表示，插入了一个新元素。

可以证明，时间空间复杂度均为

void insert(long long x){
    for(int i = max_bit;~i;i--){
        if(x&(1LL<<i)){//注意，如果max_bit大于31，一定要写成1ll
            if(!a[i]){a[i]=x;return;}
            else x^=a[i];
        }
    }
    flag=true;//表示当前树数已经能够被线性基表示，也就是说有两个一样的数
    //若下方不涉及最值运算，可不记录
}
bool check(long long x){
    for(int i = max_bit;~i;i--){
        if(x&(1LL<<i)){
            if(!a[i]) return false;
            else x^=a[i];
        }
    }
    return true;
}

异或最值#

最小值#

考虑插入的过程，的二进制最高位必定单调降低，所以不可能插入两个二进制最高位相同的数。而此时，线性基中最小值异或上其他数，必定会增大。所以，直接输出线性基中的最小值即可。

long long qmin(){
    long long ans=0;
    if(flag) return 0;
    for(int i = 0;i<=max_bit;i++){
        if(a[i]) return a[i];
    }
}

最大值#

从高到低遍历线性基，考虑到第位时，如果当前答案的第位为，就将异或上，否则不做操作。这样，每次操作后的答案不会变劣，得到最终答案。

long long qmax(){
    long long ans=0;
    for(int i = max_bit;~i;i--){
        ans=max(ans,ans^a[i]);
    }
    return ans;
}

第小值#

{% label 注意，这里的第k小值是指异或出来的数的第k小 red %}

• 对于每一个,枚举,如果的第位为，那么
• 若的第位为，就异或上处理后的线性基中第个元素。

long long k_th(long long k){
    long long res=0,cnt=0;
    k-=flag;if(!k) return 0;
    for(int i = 0;i<=max_bit;i++){
        for(int j=i-1;~j;j--){
            if(a[i]&(1LL<<j))a[i]^=a[j];
        }
        if(a[i])tmp[cnt++]=a[i];
    }
    if(k>=(1LL<<cnt)) return -1;
    for(int i = 0;i<cnt;i++){
        if(k&(1LL<<i))res^=tmp[i];
    }
    return res;
}