hdu 3949 XOR 题解【线性基】【二进制】

点击量：218

线性基的题都好有意思啊

目录

Problem Description

XOR is a kind of bit operator, we define that as follow: for two binary base number A and B, let C=A XOR B, then for each bit of C, we can get its value by check the digit of corresponding position in A and B.

And for each digit, 1 XOR 1 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, 0 XOR 0 = 0. And we simply write this operator as ^, like 3 ^ 1 = 2,4 ^ 3 = 7. XOR is an amazing operator and this is a question about XOR. We can choose several numbers and do XOR operatorion to them one by one, then we get another number. For example, if we choose 2,3 and 4, we can get 2^3^4=5. Now, you are given N numbers, and you can choose some of them(even a single number) to do XOR on them, and you can get many different numbers. Now I want you tell me which number is the K-th smallest number among them.

Input

First line of the input is a single integer T(T<=30), indicates there are T test cases.

For each test case, the first line is an integer N(1<=N<=10000), the number of numbers below. The second line contains N integers (each number is between 1 and 10^18). The third line is a number Q(1<=Q<=10000), the number of queries. The fourth line contains Q numbers(each number is between 1 and 10^18) K1,K2,……KQ.

Output

For each test case,first output Case #C: in a single line,C means the number of the test case which is from 1 to T. Then for each query, you should output a single line contains the Ki-th smallest number in them, if there are less than Ki different numbers, output -1.

Sample Input

2
2
1 2
4
1 2 3 4
3
1 2 3
5
1 2 3 4 5

Sample Output

Case #1:
1
2
3
-1
Case #2:
0
1
2
3
-1

Hint

If you choose a single number, the result you get is the number you choose.
Using long long instead of int because of the result may exceed 2^31-1.

Author

elfness

题意：

给定 $ n$ 个数，求出这 $ n$ 个数能异或出来的去除重复元素后第 $ x$ 小的数。如果能异或出来的不同的数小于 $ x$ 个，则输出 $ -1$。多组询问，多组数据。

题解：

用到了线性基的性质：线性基的任意两个非空子集所构成的数都不相同。

因此我们先把线性基 $ O(n\log a_i)$ 地构造出来，然后通过类似高斯消元的步骤，$ O(\log^3a_i)$ 让每个 $ b_i$ 都保证最小。

考虑所有的 $ b_i$ 都有值这种特殊情况，此时，对于 $ {b_1,b_2\dots,b_k}$ ，它们的所有非空子集可以构成 $ 2^k-1$ 个不同的数。而如果只选择 $ b_{k+1}$ ，那么它一定比上述 $ 2^k-1$ 个数都大。这种情况就是在用二进制表示数。

如果一些 $ b_i$ 是没有值的，那么就需要跳过这些 $ b_i$，考虑有值的 $ b_i$ ，令其从小到大为 $ {c_1,c_2,\dots,c_m}$。那么对于 $ {c_1,c_2,\dots,c_k}$，它们的所有非空子集可以构成 $ 2^k-1$ 个不同的数，同样，如果只选择 $ c_{k+1}$，那么在 $ {c_1,c_2,\dots,c_k}$ 中不可能有最高位大于等于 $ c_{k+1}$ 的最高位的数，因此同样可以利用二进制的思想来理解。

当线性基构造过程中出现了 $ 0$，就说明存在一个非空子集使得他们的异或和为 $ 0$。而我们在构造的过程中是不会考虑到 $ 0$ 这种情况的，因此一旦出现过，就要打好标记，然后询问就要变为第 $ x-1$ 小的数了。

Code：

#include<cstdio>
#include<algorithm>
#define ll long long
ll b[64];
int main()
{
    int T;
    scanf("%d",&T);
    for(int r=1;r<=T;++r)
    {
        printf("Case #%d:\n",r);
        std::fill(b,b+64,0);
        int n,q,cnt=0,flag=0;
        ll x;
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
        {
            scanf("%lld",&x);
            for(int j=63;j>=0;--j)
                if(x>>j)
                {
                    if(b[j])
                        x^=b[j];
                    else
                    {
                        b[j]=x;
                        ++cnt;
                        break;
                    }
                }
            if(!x)
                flag=1;
        }
        for(int i=0;i<=63;++i)
        {
            int t=i+1;
            while(t<=63&&!b[t])
                ++t;
            while(t<=63)
            {
                if(b[t]&(1<<i))
                    b[t]^=b[i];
                ++t;
                while(t<=63&&!b[t])
                    ++t;
            }
        }
        scanf("%d",&q);
        for(int i=1;i<=q;++i)
        {
            scanf("%lld",&x);
            x-=flag;
            if(x>=(1ll<<cnt))
            {
                puts("-1");
                continue;
            }
            int t=0;
            while(!b[t])
                ++t;
            ll ans=0;
            while(x)
            {
                if(x&1)
                    ans^=b[t];
                ++t;
                while(!b[t])
                    ++t;
                x>>=1;
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}