线性基

luckydrawbox · 2021-08-22 01:54:47 · 个人记录

有一个整数集合 S=a_1,a_2,…,a_n，它的一个子集合 S'=a_{k_1},a_{k_2},…,a_{k_m}，如果它满足原集合的每个数 a_i=c_{i,1}a_{k_1}+c_{i,2}a_{k_2}+…+c_{i,m}a_{k_m}，其中 c_{i,j} 为整数，且 m 最小，则称 S' 为 S 的线性基。

long long xxj[SIZE],tmp[SIZE];
bool flag;
void XXJ_insert(long long x){
    for(int i=SIZE;i>=0;i--)
        if(x&((long long)1<<i))
            if(!xxj[i]){
                xxj[i]=x;
                return;
            }
            else
                x^=xxj[i];
    flag=1;
}
bool XXJ_check(long long x){
    for(int i=SIZE;i>=0;i--)
        if(x&((long long)1<<i))
            if(!xxj[i])
                return 0;
            else
                x^=xxj[i];
    return 1;
}
long long XXJ_qmax(){
    long long res=0;
    for(int i=SIZE;i>=0;i--)
        res=max(res,res^xxj[i]);
    return res;
}
long long XXJ_qmin(){
    if(flag)
        return 0;
    for(int i=0;i<=SIZE;i++)
        if(xxj[i])
            return xxj[i];
}
long long XXJ_query(long long k){
    long long res=0;
    int cnt=0;
    k-=flag;
    if(!k)
        return 0;
    for(int i=0;i<=SIZE;i++){
        for(int j=i-1;j>=0;j--)
            if(xxj[i]&((long long)1<<j))
                xxj[i]^=xxj[j];
        if(xxj[i])
            tmp[cnt++]=xxj[i];
    }
    if(k>=((long long)1<<cnt))
        return -1;
    for(int i=0;i<cnt;i++)
        if(k&((long long)1<<i))
            res^=tmp[i];
    return res;
}

其中 SIZE 是所有数中二进制下最大的位数。

操作

时间复杂度都在 O(SIZE) 左右。