线性基求第k小异或值

题目链接
题意：给由 n 个数组成的一个可重集 S，每次给定一个数 k，求一个集合 \(T \subseteq S\)，
使得集合 T 在 S 的所有非空子集的不同的异或和中，
其异或和 \(T_1 \mathbin{\text{xor}} T_2 \mathbin{\text{xor}} \ldots \mathbin{\text{xor}}T_{|T|}\)是第 k 小的。

/*

1.照例建立线性基
2.使得线性基中有且只有base[i]的第i位为1
3.记录所有有值的base[] 从低位到高位记为0~cnt，共cnt + 1个 （注：闭区间
这时线性基可以构成的数有(1 << cnt) + 1个，如果cnt + 1 < n的话 说明可以取零 这时可以构成的数有(1 << (cnt + 1))个
4.取 第k小 时
如果k大于可以构成的数的总数 那么无解
否则res是所有base[i] ((k - 1)的第i位为1) 的异或和 

*/

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 55;
int n, m;

struct BASE{
    long long w[N];
    int cnt;
    void init(){
        memset(w, 0, sizeof(w));
    }
    void ins(long long x){
        for(int i = 50; i >= 0; --i){
            if((x >> i) & 1) 
                if(w[i]) x ^= w[i];
                else {w[i] = x; break;}
        }
    }
    void build(){
        for(int i = 50; i >= 0; --i){
            if(!w[i]) continue;
            for(int j = i + 1; j <= 50; ++j){
                if((w[j] >> i) & 1){
                    w[j] ^= w[i];
                }
            }
        }
        //for(int i = 0; i <= 5; ++i) printf("%d %lld\n", i, w[i]);
        for(int i = 0; i <= 50; ++i){
            //printf("%d %lld\n", i, w[i]);
            if(w[i]){
                w[cnt++] = w[i];
            //  printf("%d %lld\n", cnt - 1, w[cnt - 1]);
            }
        }
        --cnt;
    }
    long long query(long long x){
        long long res = 0;
        for(int i = cnt; i >= 0; --i){
            if((x >> i) & 1) res ^= w[i];
        }
        return res;
    }
}base;

int main() {
    base.init();
    scanf("%d", &n);
    long long x;
    for(int i = 1; i <= n; ++i){
        scanf("%lld", &x);
        base.ins(x);
    }
    base.build();
    scanf("%d", &m);
    for(int i = 1; i <= m; ++i){
        scanf("%lld", &x);
        if(n != base.cnt + 1) --x;//注意是非空子集 所以特判可否取零 
        if(x >= (1ll << (base.cnt + 1))) printf("-1\n"); //这种情况下无法取到 
        else printf("%lld\n", base.query(x));
    }
    return 0;    
} 

线性基求第k小异或值

原文：https://www.cnblogs.com/hjmmm/p/10529952.html