我必须找到独特的异或数组的子集的元素之间的最大值。我要检查的数组中的每个子集，这将产生最大的XOR将是答案的一部分。

I have to find maximum value of exclusive xor among the elements of subsets of an array. I have to check every subset of the array and the subset which will yield maximum xor will be the answer.

对于exapmle - 让 F（S）表示这需要异或超过子集的取值的所有元素数组与作用的点= {1,2,3,4}

For exapmle- let F(S) denote the fuction which takes xor over all elements of subset S of array P={1,2,3,4}

F({1,2}) = 3
F({1,3}) = 2
F({1,2,3}) = 0  
F({1,4}) = 5
F({2,3}) = 1  
F({2,4}) = 6  
F({3,4}) = 7  
F({2,3,4}) = 5  
F({1,2,3,4}) = 4`  

其中最大的是7。因此，答案是7。 （还有其他的子集，但他们不值得考虑）。的如果你要告诉我高斯消元方式，我读过某处的MSE，但它并不清晰。 如果高斯消元法是唯一的答案不是请详细说明对我还是有一些方法/算法，我不知道？

Maximum of them is 7. Hence the answer is 7.(There are other subsets but they are not worth considering). If you are about to tell me about Gaussian Elimination method, I've read that somewhere on MSE but it was not at all clear to me. If gauss elimination is the only answer than please elaborate that to me or is there some method/algorithm I don't know of?

推荐答案

高斯消元是你所需要的。

Gaussian Elimination is what you need.

例如： 3 号 {9,8，5}

首先对它们进行排序递减，并将其转换为二进制：

first sort them decreasingly and convert them to binary :

9 : 1001
8 : 1000
5 : 0101

第一次检查 4 位 1日数（9）。因为它是1异或它与下面的数字，其中第四位为1

1st check 4th bit of 1st number (9). As it is 1 xor it with below numbers where 4th bit is 1

9 : 1001
1 : 0001 > changed
5 : 0101

现在检查 3 第2位数（1）。由于它是0，请查看下号码1在第3位... 在第3位数字5有1 :) 所以交换它们

now check 3rd bit of 2nd number (1). As it is 0, check below numbers for 1 in 3rd bit... number 5 has 1 in 3rd bit :) so swap them

9 : 1001
5 : 0101 > swapped
1 : 0001

现在XOR 5所有，其中第3位为1。这里没有presents的数字。因此，不会发生变化。

now xor 5 with all the numbers where 3rd bit is 1. Here none presents. So no change will occur.

现在检查第二 第3位数（1）。因为它是0和不存在以下其中第二位是1，所以不会发生变化。

now check 2nd bit of 3rd number (1). As it is 0 and none exists below where 2nd bit is 1, so no change will occur.

现在检查第1 第3位数（1）。因为它是1，改变所有的号码，其中第1位为1

now check 1st bit of 3rd number (1). As it is 1, change all the numbers where 1st bit is 1

8 : 1000 > changed
4 : 0100 > changed
1 : 0001

没有更多的留一点需要考虑：）

no more bit left to consider :)

现在异或整个剩余阵列 {8 ^ 4 ^ 1} = 13

now xor the whole remaining array {8 ^ 4 ^ 1} = 13

让 13 是解决方案：）

这是pretty的多是用来解决问题的高斯消元：）

That's pretty much it to solve the problem using Gaussian Elimination :)

下面是我的C ++实现：

Here is my C++ implementation :

#include <bits/stdc++.h>
using namespace std;

typedef long long int           ll;
typedef unsigned long long int  ull;

ull check_bit(ull N,int POS){return (N & (1ULL<<POS));}

vector<ull>v;
ull gaussian_elimination()
{
    int n=v.size();
    int ind=0;  // Array index
    for(int bit=log2(v[0]);bit>=0;bit--)
    {
        int x=ind;
        while(x<n&&check_bit(v[x],bit)==0)
          x++;
        if(x==n)
          continue; // skip if there is no number below ind where current bit is 1
        swap(v[ind],v[x]);
        for(int j=0;j<n;j++)
        {
            if(j!=ind&&check_bit(v[j],bit))
                v[j]^=v[ind];
        }
        ind++;
    }
    ull ans=v[0];
    for(int i=1;i<n;i++)
      ans=max(ans,ans^v[i]);
    return ans;
}
int main()
{
    int i,j,k,l,m,n,t,kase=1;
    scanf("%d",&n);
    ull x;
    for(i=0;i<n;i++)
    {
        cin>>x;
        v.push_back(x);
    }
    sort(v.rbegin(),v.rend());
    cout<<gaussian_elimination()<<"\n";
return 0;
}