原题连接
更好的阅读体验

题目描述

给定你由N个整数构成的整数序列，你可以从中选取一些（甚至一个）进行异或（XOR）运算，从而得到很多不同的结果。

请问，所有能得到的不同的结果中第k小的结果是多少。

输入格式
第一行包含整数T，表示共有T组测试数据。

对于每组测试数据，第一行包含整数N。

第二行包含N个整数(均在1至$10^{18}$之间)，表示完整的整数序列。

第三行包含整数Q，表示询问的次数。

第四行包含Q个整数$k_1,k_2,…,k_Q$,表示Q个询问对应的k。

输出格式
对于每组测试数据，第一行输出“Case #C:”，其中C为顺序编号（从1开始）。

接下来Q行描述Q次询问的结果，每行输出一个整数，表示第i次询问中第$k_i$小的结果。

如果能得到的不同结果的总数少于$k_i$，则输出“-1”。

数据范围
$1 \le N,Q \le 10000$,
$1 \le k_i \le 10^{18}$

注意:只选取一个数字进行运算，则结果为该数字本身。

样例

输入样例：
2
2
1 2
4
1 2 3 4
3
1 2 3
5
1 2 3 4 5
输出样例：
Case #1:
1
2
3
-1
Case #2:
0
1
2
3
-1

高斯消元+异或空间

这道题目依旧是万恶的高斯消元和万恶的异或空间.

高斯消元找到一组线性无关组,消出对角矩阵后,对于k二进制拆分,对于每列只有有一个1的，显然可以用k的二进制数直接异或得到第k大,对于一列由多个1的，由于二进制性质，由于2的幂+1次方比2的(1到幂)的和要大，所以不影响大小.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define fic(i,a,b) for(int i=a;i>=b;i--)
#define int unsigned long long
int a[10010],n, m, t, T;
signed main() 
{
    ios::sync_with_stdio(false);
    cin>>T;
    fir(tt,1,T)
    {
        cin>>n;
        fir(i,1,n)
            cin>>a[i];
        bool ok=0;
        t=n;
        fir(i,1,n)
        {
            fir(j,i+1,n)
                if (a[j]>a[i]) 
                    swap(a[i],a[j]);
            if (a[i]==0) 
            {
                ok=1;
                t=i-1;
                break;
            }
            fic(k,63,0)
                if (a[i] >> k & 1) 
                {
                    fir(j,1,n)
                        if (i != j && (a[j] >> k & 1)) 
                            a[j] ^= a[i];
                    break;
                }
        }
        cin>>m;
        cout<<"Case #"<<tt<<":"<<endl;
        while (m--) 
        {
            int k, ans=0;
            cin>>k;
            if (ok) 
                k--;
            if (k>=(1llu)<<t) 
                cout<<-1<<endl;
            else 
            {
                fic(i,t-1,0)
                {
                //    cout<<i<<" "<<t-1<<endl;
                    if(i>t-1)
                        break;
                    if (k>>i & 1) 
                        ans^=a[t-i];
                }
                cout<<ans<<endl;
            }
        }
    }
}