time limit per test: 0.25 sec. 

memory limit per test: 65536 KB

input: standard 

output: standard

$\DeclareMathOperator{\XOR}{XOR}$

The sequence of non-negative integers $A_1, A_2,\dots, A_N$ is given. You are to find some subsequence $A_{i_1}, A_{i_2}, \dots, A_{i_k}$ ($1 \le i_1 < i_2 < \dots < i_k \le N$) such that $A_{i_1} \XOR A_{i_2} \XOR \dots \XOR A_{i_k} $ has a maximum value.

Input

The first line of the input file contains the integer number $N$ ($1 \le N \le 100$). The second line contains the sequence $A_1, A_2, \dots, A_N$ ($0 \le A_i \le 10^{18}$). 

Output

Write to the output file a single integer number——the maximum possible value of $A_{i_1} \XOR A_{i_2} \XOR \dots \XOR A_{i_k} $. 

Sample test(s)

Input

 

 

3 

11 9 5 

 

 

Output

 

 

14 

 

分析

搜题解时发现多数题解写得都不太好懂，我想把这道题说得清楚一点

先说异或方程组的建立

用bool变量x[i]表示是否选择数A[i]。

用a[i][j]表示数A[i]的第j位，那么结果的第i位b[i]可表示为

b[i] = a[0][i]*x[0] ^ a[1][i]*x[1] ^ ... ^ a[n-1][i]*x[n-1]

(注意：a[i][j]与b[i]都是bool量，考虑到bool量之间的乘法运算是未定义的，不妨将上式中的乘号（*）看做逻辑与（&&））

这样可得到63个方程（long long的最高位是符号位），方程组便建立起来了。

不难看出：与一般的异或方程组不同，这个方程组中的b[i]也是未知的。

但同时也要注意到，我们的目标是找到使结果最大的右端向量b,同时使得上述方程有解（并不是真的要解某个异或方程组）。

使结果最大就是使结果的最高位尽量高，所以可以从高位往低位枚举，看（右端向量b中）该位可否为1。

b[i]可能取1的充要条件是a[0][i]到a[n-1][i]至少有一个是1。

证明： 假设a[k][i]=1，任取一解向量(x[0], ..., x[n-1])。若b[i]=0，那么将x[k]取反，b[i]也反转。因而总可以构造出一右端向量b使得方程有解且b[i]=1。

我们称一个异或方程中系数为1的变元x[k]称为该方程的控制变元(critical variable)。

我们有如下结论：

　　

一个含控制变元的异或方程永远有解。

不难看出：一个变元x[k]只可能作为某一个方程的控制变元。

到这里，算法已经形成：

将右端向量设为全1。

从高位向低位枚举各异或方程，看该方程中是否有控制变元如果有说明该方程有解，也就意味着结果中该位可取1。

任取一控制变元,设为x[k]，

然后将低位的方程中x[k]的系数为1的方程与当前位的方程相异或（两个异或方程相异或的原理，请见），这一步的目的是消去低位方程中的x[k]，保证x[k]只是当前方程的控制变元。

如果当前位（设为i）的方程没有控制变元，就看b[i]的值，若b[i]=0，说明该方程与高位的各个方程不矛盾，即该位可取1，否则只能取0。

 

Implementation

 

#include 
       
        using namespace std;int a[63][105]; #define LL long longLL b[105];LL res;//写好每一个循环//写好每一个if elsevoid gauss(int n, int m){    for(int i=m-1; i>=0; i--){        int flag=1;        for(int j=0; j
        
         =0; k--)                    if(a[k][j])                        for(int l=0; l<=n; l++)                            a[k][l]^=a[i][l];                break;            }        if(!flag||flag&&!a[i][n]) res+=1LL<
         
          >n;    for(int i=0; i
          
           >b[i];    for(int i=0; i<63; i++){        for(int j=0; j
          
         
        
       

---

P.S. 看到一份比较短的代码，思路也是高斯消元，学习一个。

#include 
       
        using namespace std;int n;long long ans, b, a[109];int main(){    int n;    cin>>n;    for(int i=0; i
        
         >a[i];    for(int i=62; i>=0; i--)        for(int j=0; j
         
          >i&1){            b=a[j];            if(!(ans>>i&1)) ans^=b;            for(int k=0; k
          
           >i&1) a[k]^=b;        }    cout<
           
            <