描述 Description
You have an array of integers A1, A2, …, AN. The function F(P), where P is a subset of A, is defined as the XOR (represented by the symbol ⊕) of all the integers present in the subset. If P is empty, then F(P)=0.
Given an integer K, what is the maximum value of K ⊕ F(P), over all possible subsets P of A?
输入格式 InputFormat
The first line contains T, the number of test cases. Each test case consists of N and K in one line, followed by the array A in the next line.
输出格式 OutputFormat
For each test case, print the required answer in one line.
样例输入 SampleInput
1
3 4
1 2 3
样例输出 SampleOutput
7
代码 Code
高斯消元解异或方程组。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=1005;
int i,j,t,n,m,l,r,k,z,y,x;
int a[maxn];
int T,ans;
inline int gauss()
{
int i,j,t;
for (t=1,i=20;i>=0;i--)
{
for (j=t;j<=n;j++) if (a[j]&(1<<i)) break;
if (a[j]&(1<<i))
{
swap(a[j],a[t]);
for (j=1;j<=n;j++) if (j!=t && (a[j]&(1<<i))) a[j]^=a[t];
t++;
}
}
return t-1;
}
int main()
{
scanf("%d",&T);
while (T--)
{
memset(a,0,sizeof(a));
scanf("%d%d",&n,&k);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
m=gauss();
ans=k;
for (i=1;i<=m;i++) ans=max(ans,ans^a[i]);
printf("%d\n",ans);
}
return 0;
}