学步园

在n个数中选任意多个（不为0）进行xor，求结果中的第k小

高斯消元后就可以确定自由元，对自由元0\1选取就可以快速确定第k小。

有几个较为特殊的处理，首先是不能不选，因此0的选取要根据自由元的数量是否达到上限来判断，然后是对于非自由元必须跟着自由元变化，因此消元的时候要从头到尾消完，最后是必须从高位开始消元，否则的话，最高位如果不是自由元的话，就无法从高到低位来取0\1来逼近第k小数

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int n,t,q;
long long a[200000],k;
int main()
{
	freopen("input.txt","r",stdin);
	freopen("ansput.txt","w",stdout);
    scanf("%d\n",&t);
    for (int test=1;t;t--,test++) {
        printf("Case #%d:\n",test);
        scanf("%d\n",&n);
        for (int i=1;i<=n;i++) scanf("%I64d",&a[i]);
        int j=1;
        for (int i=60;i>=0;i--) {
            int k;
            for (k=j;(k<=n) && (!((a[k]>>i)&1));k++) ;
            if (k<=n) {
                a[0]=a[j],a[j]=a[k],a[k]=a[0];
                for (k=1;k<=n;k++)
                    if ((k!=j) && (a[k]>>i)&1) a[k]^=a[j];
                j++;
            }
        }
        int flag=1;
        j--;
        for (int i=1;i<=n;i++)
            if (!a[i]) flag=0;
//        cout<<flag<<endl;
//        for (int i=1;i<=n;i++) printf("%I64d ",a[i]);printf("\n");
        scanf("%d\n",&q);
        for (int i=1;i<=q;i++) {
            scanf("%I64d",&k);
            k+=flag;
            if (k>(1LL<<(j))) {
                printf("-1\n");
                continue;
            }
            long long ans=0;
            for (int p=1;p<=j;p++)
                if (k>(1LL<<(j-p))) {
                    k-=(1LL<<(j-p));
                    ans^=a[p];
                }
            printf("%I64d\n",ans);
        }
    }
	return 0;
}