线性基

线性基是竞赛中常用来解决子集异或一类题目的算法
和高斯消元好像有那么一点联系

前备知识: 异或和、张成、线性相关

用一堆线性无关的最小集合 可以表示出原集合中的任何一个数

insert

bool insert(LL x){
    for(int i = 63;i >= 0;i -- ){
        if((x >> i & 1) == 0) continue;
        if(f[i]) x ^= f[i];
        else{ f[i] = x; return true; }
    }
    return false;
}

性质

1. 求任意子集xor最大值: 第二种：贪心 构造
2. 求任意子集xor最小值: 等于最小的主元
3. 查询x是否在值域中: 如果x能插入线性基，则x不能被当前线性基xor出来
4. 查询第k小的值: 把k进行二进制分解，把1对应位置的主元xor起来 注意这里第0小就是0
5. 求任意子集与x进行xor的最大值：从高->低贪心，若xor上a[j]能变大就xor
6. 查询x是否在值域中：将它insert 如果失败则在值域中
7. 线性基不唯一

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 105;

typedef long long LL;

LL f[N];
bool flag;
int cnt;

bool insert(LL x){
    for(int i = 63;i >= 0;i -- ){
        if((x >> i & 1) == 0) continue;
        if(f[i]) x ^= f[i];
        else{ f[i] = x; return true; }
    }

    return false;
}
void build(){
    for(int i = 0;i <= 63;i ++ ){
        for(int j = i + 1;j <= 63;j ++ ){
            if(f[j] >> i & 1) f[j] ^= f[i];
        }
    }
    cnt = 0;
    for(int i = 0;i <= 63;i ++ ){
        if(f[i]) f[cnt ++ ] = f[i];
    }
}
LL query(LL k){
    int i = 0;
    LL res = 0;
    while(k){
        if(k & 1) res = res ^ f[i];
        i ++ ;
        k >>= 1;
    }

    return res;
}
int main(){
    int T; scanf("%d", &T);
    int cases = 1;
    while(T -- ){
        flag = false, cnt = 0;
        memset(f, 0, sizeof f);
        int n; scanf("%d", &n);
        for(int i = 1;i <= n;i ++ ){
            LL x; cin >> x;
            // 插入不成功 则线性相关 flag = true
            if(!insert(x)) flag = true;
        }

        build();

        printf("Case #%d:\n", cases ++ );
        int Q; cin >> Q;
        while(Q -- ){
            LL k; cin >> k;
            if(flag) k -- ;
            if(k >= (LL)1 << cnt) puts("-1");
            else printf("%lld\n", query(k));
        }
    }

    return 0;
}