自闭线性基模板

粘一下自己觉得好的模板

这个没学.jpg

题目链接

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef long long LL;
const int maxn=1e4+7;
struct L_B{
    LL d[61],p[61];
    int cnt;
    L_B(){
        memset(d,0,sizeof(d));
        memset(p,0,sizeof(p));
        cnt=0;
    }
    bool insert(LL val){
        for(int i=60;i>=0;i--){
            if(val&(1LL<<i)){
                if(!d[i]){
                    d[i]=val;
                    break;
                }
                else val^=d[i];
            }
        }
        return val>0;
    }
    LL query_max(){
        LL ret=0;
        for(int i=60;i>=0;i--){
            if(ret^d[i]>ret)
                ret^=d[i];
        }
        return ret;
    }
    LL query_min(){
        for(int i=0;i<=60;i++)
            if(d[i])
            return d[i];
        return 0;
    }
    void rebuild(){
        for(int i=60;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<=60;i++)
            if(d[i])
            p[cnt++]=d[i];
    }
    LL kthquery(LL k){///第k小个异或值
        int ret=0;
        if(k>=(1LL<<cnt))
            return -1;
        for(int i=60;i>=0;i--)
            if(k&(1LL<<i))
            ret^=p[i];
        return ret;
    }
};
LL t,n,m,ce,a,b[maxn];
bool flag;
int main(){
    scanf("%lld",&t);
    ce=1;
    while(t--){
        L_B in;
        flag=true;
        scanf("%lld",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a);
            if(!in.insert(a))flag=false;
        }
        in.rebuild();
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
            scanf("%lld",&b[i]);
        printf("Case #%lld:
",ce++);
        for(int i=1;i<=m;i++){
            if(flag)printf("%lld
",in.kthquery(b[i]));
            else printf("%lld
",in.kthquery(b[i]-1));
        }
    }
    return 0;
}