time limit per test: 0.25 sec.
memory limit per test: 65536 KB
memory limit per test: 65536 KB
input: standard
output: 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
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 <bits/stdc++.h>
using namespace std;
int a[][];
#define LL long long
LL b[];
LL res;
//写好每一个循环
//写好每一个if else
void gauss(int n, int m){
for(int i=m-; i>=; i--){
int flag=;
for(int j=; j<n; j++)
if(a[i][j]){
flag=;
for(int k=i-; k>=; k--)
if(a[k][j])
for(int l=; 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=; i<n; i++)
cin>>b[i];
for(int i=; i<; i++){
for(int j=; j<n; j++){
a[i][j]=(bool)(b[j]&1LL<<i);
}
a[i][n]=;
}
gauss(n, );
cout<<res<<endl;
}
P.S. 看到一份比较短的代码，思路也是高斯消元，学习一个。
#include <iostream>
using namespace std;
int n;
long long ans, b, a[];
int main(){
int n;
cin>>n;
for(int i=; i<n; i++) cin>>a[i];
for(int i=; i>=; i--)
for(int j=; j<n; j++) if(a[j]>>i&){
b=a[j];
if(!(ans>>i&)) ans^=b;
for(int k=; k<n; k++) if(a[k]>>i&) a[k]^=b;
}
cout<<ans<<endl;
}