题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=275
这是一道xor高斯消元。
题目大意是给了n个数，然后任取几个数，让他们xor和最大。
首先根据题目意思可以列出下列方程组：
//a11x1+a21x2……=d[1]
//a12x1+a22x2……=d[2]
//…
（每个数二进制按列来写，xi为0或1，表示取或不取这个数。）
结果的二进制即为d数组。
由于需要结果最大，而结果最多是d全为1，那么就假设所有d均为1，然后进行高斯消元，来判断该行的d是否能取到。
步骤如下：
1、建立增广矩阵。
2、从最后一行往前扫，如果该行存在1，那么d[i]自然能取到1，这样需要把该列其它的1消掉，由于是高斯消元，消1的时候需要整行消；如果该行不存在1，而且d[i] == 0，自然该行的方程仍然有解。
3、消元的过程中保存答案。
复杂度O(63*63n)
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#define LL long longusing namespace std;const int len = ;
int n, a[][];
bool vis[];void xorGauss()
{
LL ans = ;
for (int i = len-; i >= ; i--)
{
int j;
for (j = ; j < n; j++)
{
if (a[i][j] && !vis[j])
{
vis[j] = true;
ans += (LL)<<i;
break;
}
}
if(j == n)
{
if(a[i][n] == )
ans += (LL)<<i;
}
else
{
for (int k = i-; k >= ; k--)
{
if (a[k][j])
{
for (int v = ; v <= n; v++)
a[k][v] ^= a[i][v];
}
}
}
}
printf("%I64d\n", ans);
}void input()
{
memset(a, , sizeof(a));
memset(vis, false, sizeof(vis));
//next is input
LL v;
int k;
for (int i = ; i < n; i++)
{
scanf("%I64d", &v);
for (int j = ; v > ; j++)
{
k = v&;
a[j][i] = k;
v >>= ;
}
}
//pre is input
for (int i = ; i < len; i++)
a[i][n] = ;
}int main()
{
// freopen("test.in", "r", stdin);
while (scanf("%d", &n) != EOF)
{
input();
xorGauss();
}
return ;
}
其实到这里这个问题并没有完美解决。
起始从前面的方程组可以看出来，一组矩阵，可以等同于另一组等价的矩阵。
于是我们只需要找出这个矩阵里面的最大线性无关组。（数之间不能互相表示）
然后通过线性无关组就能表示最大值了。
其实就是把矩阵化成最简矩阵。
然后这时把一个数看成整体，就能用位运算优化了。
效率O(63n)
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <string>
#define LL long longusing namespace std;//xor高斯消元求线性基
//时间复杂度O(63n)
const int maxN = ;
int n;
LL a[maxN];int xorGauss(int n)
{
int row = ;
for (int i = ; i >= ; i--)
{
int j;
for (j = row; j < n; j++)
if(a[j]&((LL)<<i))
break;
if (j != n)
{
swap(a[row], a[j]);
for (j = ; j < n; j++)
{
if(j == row) continue;
if(a[j]&((LL)<<i))
a[j] ^= a[row];
}
row++;
}
}
return row;
}void work()
{
for (int i = ; i < n; i++)
scanf("%I64d", &a[i]);
int row;
row = xorGauss(n);
LL ans = ;
for (int i = ; i < row; ++i)
ans = max(ans, ans^a[i]);
printf("%I64d\n", ans);
}int main()
{
//freopen("test.in", "r", stdin);
while (scanf("%d", &n) != EOF)
{
work();
}
return ;
}
