HDU 3949 XOR （异或消元）-蒲公英云

HDU 3949 XOR （异或消元）

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

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

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

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

第二行包含N个整数(均在1至1018

之间)，表示完整的整数序列。

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

第四行包含Q个整数k1,k2,…,kQ

,表示Q个询问对应的k。
输出格式

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

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

小的结果。

如果能得到的不同结果的总数少于ki

，则输出“-1”。
数据范围

1≤N,Q≤10000
,
1≤ki≤1018

输入样例：

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

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

分析：
参考博客：https://mp.csdn.net/mdeditor/100060669
https://www.cnblogs.com/andyqsmart/p/4957420.html

wa的心态不好了。
莫名其妙的wa。
x >> i & 1 和 x & (1LL <<ｉ)我一开始判断语句写的后面这个式子就wa，换成前面的式子就可以过了。求大佬救一下这里。

简单分析一下这个题把。
本题要求从N个数里面任意选取n个数异或得到第k大的值。
从N个数任意选取n个数所得到的可能值是一个线性空间。那么我们首先用高斯消元就可以把这个线性空间的基求出来。

现在，我们在考虑第k大。
eg：
5个数（一组基）：1 2 4 8 16
现在我们求此异或空间的第3大。3的二进制位011.
那么我们把基里面的第1个和第2个(即1和2)异或起来就是此线性空间的第3大。
其他，可类推。
同时，注意0是否是可取的情况。

#include"stdio.h"
#include"string.h"
#include"algorithm"
using namespace std;
typedef long long ll;
int T,N,Q,row;
ll a[10010],b[10010],max_num;
void init()
{
    scanf("%d",&N);
    for(int i = 1; i <= N; i ++)
        scanf("%lld",&a[i]);
    scanf("%d",&Q);
    for(int i = 1; i <= Q; i ++)
        scanf("%lld",&b[i]);
}
void Gauss()
{
    row = 1;
    for(int x = 63; x >= 0; x --)
    {
        int i;
        for(i = row; i <= N; i ++)
            if(a[i] & (1LL << x))
               break;
        if(i == N + 1) continue;
        swap(a[i],a[row]);
        for(int j = 1; j <= N; j ++)
            if(j != row && ((a[j] >> x & 1) == 1))
                a[j] ^= a[row];
        ++ row;
    }
    row --;
   /* printf("bug\n");
    for(int i = 1; i <= row; i ++)
        printf("%lld \n",a[i]);
    printf("\n");*/
    max_num = 1LL << row;
    if(row == N)
        max_num --;
}
void work(ll x)
{
    if(x > max_num)
    {
        printf("-1\n"); return ;
    }
    if(row < N)
    {
        if(x == 1)
        {
            printf("0\n"); return ;
        }
        x --;
    }
    ll sum = 0;
    for(int i = row - 1; i >= 0; i --)
        if(x >> i & 1) sum ^= a[row - i];
    printf("%lld\n",sum);
}
int main()
{
    int cnt = 1;
    scanf("%d",&T);
    while(T --)
    {
        init();
        Gauss();
        printf("Case #%d:\n",cnt ++);
        for(int i = 1; i <= Q; i ++)
            work(b[i]);
    }
}