HDU-3949 XOR
题目
分析
代码
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
#define d(x) cout<<(x)<<endl;
typedef long long ll;
const int N = 1e4 + 10;
const int base = 60;
ll t, n, q, x;
ll a[N], p[base + 3];
vector<ll> v;
void solve(){ // 计算线性基
v.clear();
memset(p, 0, sizeof(p));
for(int i = 0; i < n; i++){ // 对于每个数 a[i]
for (int j = base; j >= 0; j--){ // 从高位到低位找 a[i] 的第一个不为 0 的数的位置
if(a[i] >> j == 0)
continue; // 跳过前导 0
if(!p[j]){ // 该行没数,直接填
p[j] = a[i];
for (int k = j - 1; k >= 0; k--)
if(p[k] && p[j]>>k&1)
p[j] ^= p[k]; // 下面的行消自己
for (int k = j + 1; k <= base; k++)
if(p[k] >> j&1)
p[k] ^= p[j]; // 自己消上面的行
break;
}else{
a[i] ^= p[j]; // 该行有数
}
}
}
for (int i = 0; i <= base; i++){ // 后面查询用到,存非零位
if(p[i]){
v.push_back(p[i]);
}
}
}
ll ask(ll x){ // 查询第 k 小
if(v.size() != n) // 线性有关,可以异或出来 0
x--;
if(!x)
return 0; // 第一小的数是 0
if(x >= (1LL << v.size())) // x 超出所有能得到的值数量的范围
return -1;
// 能得到 0,x 已经 -1了,x 最多达到2^v.size()-1;
// 不等得到 0,x 最多达到v.size()-1
ll ans = 0;
for(int i = 0; i <= base; i++){ // 将第 i 为异或起来
if(x >> i&1){ // 第 i 位为 1
ans ^= v[i];
}
}
return ans;
}
int main()
{
scanf("%lld", &t);
for(int i = 1; i <= t; i++){
printf("Case #%d:\n", i);
scanf("%lld", &n);
for(int i = 0; i < n; i++){
scanf("%lld", &a[i]);
}
solve();
scanf("%lld", &q);
for(int i = 0; i < q; i++){
scanf("%lld", &x);
printf("%lld\n", ask(x));
}
}
return 0;
}