SGU 275 To xor or not to xor

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

分析

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

先说异或方程组的建立

用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 <bits/stdc++.h>
using namespace std;
int a[63][105]; 
#define LL long long
LL b[105];
LL res;
//写好每一个循环
//写好每一个if else
void gauss(int n, int m){
    for(int i=m-1; i>=0; i--){
        int flag=1;
        for(int j=0; j<n; j++)
            if(a[i][j]){
                flag=0;
                for(int k=i-1; k>=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<<i;
    }
}

int main(){
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>b[i];
    for(int i=0; i<63; i++){
        for(int j=0; j<n; j++){
            a[i][j]=(bool)(b[j]&1LL<<i);
        }
        a[i][n]=1;
    }
    gauss(n, 63);
    cout<<res<<endl;
}

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

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