SGU 275 To xor or not to xor （高斯消元）

题意：有n个数,范围是[0, 10^18]，n最大为100，找出若干个数使它们异或的值最大并输出这个最大值。

分析：

一道高斯消元的好题/

我们把每个数用二进制表示，要使得最后的异或值最大，就是要让高位尽量为1，高位能不能为1就必须用高斯消元判断了。

1. 根据数的二进制表示，建立方程组的矩阵，结果那列置为1。
2. 从下往上高斯消元(高位放下面)，如果该行有未被控制的变元，则该行的结果一定为1，且该变元控制该行。
3. 从该行往上依次消掉(异或)该变元。
4. 如果该行没有可以用来控制的变元，如果最后一列是0，则该行结果也为1，否则该行结果为0。这里能抱着已用来控制的变元的系数全是0，因为在第3步时就消掉该行以上此列的0了，后面0与0以后还是0。所以如果最后一列是0, 即该行方程也可以成立，故结果为1。

建立方程：

a11x1+a21x2……=d[1]

a12x1+a22x2……=d[2]

。。。

还有一个写的比较好的博客：http://blog.csdn.net/ivan_zjj/article/details/7629055

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <algorithm>
 7 #define LL __int64
 8 const int maxn = 100+10;
 9 using namespace std;
10 int a[maxn][maxn], vis[maxn];
11 LL b[maxn];
12 
13 int main()
14 {
15     LL ans, x;
16     int n, i, j, k;
17     b[0] = 1;
18     for(i = 1; i < 63; i++)
19     b[i] = 2*b[i-1];
20     while(~scanf("%d", &n))
21     {
22         ans = 0;
23         memset(vis, 0, sizeof(vis));
24         for(i = 0; i < n; i++)
25        {
26            scanf("%I64d", &x);
27            for(j = 0; j < 63; j++)
28            if(x & b[62-j])
29            a[j][i] = 1;
30            else
31            a[j][i] = 0;
32        }
33        for(i = 0; i < 63; i++)
34        a[i][n] = 1;
35        for(i = 0; i < 63; i++)
36        {
37            int tmp = -1;
38            for(j = 0; j < n; j++)
39            if(a[i][j] && !vis[j])
40            {
41                tmp = j;
42                break;
43            }
44            if(tmp==-1 && a[i][n]==0)
45            ans += b[62-i];
46            else if(tmp!=-1)
47            {
48                ans += b[62-i];
49                for(k = i+1; k < 63; k++)
50                if(a[k][tmp])
51                {
52                    for(j = 0; j <= n; j++)
53                    a[k][j] ^= a[i][j];
54                }
55            }
56        }
57        printf("%I64d
", ans);
58     }
59     return 0;
60 }