题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=275
题意：给你n个数，可以选择任意个数异或，但是要使得最后的异或值最大。
我们把每个数用二进制表示，要使得最后的异或值最大，就是要让高位尽量为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]
……
很好的题目、
1 /* *********************************************** 2 Author :kuangbin 3 Created Time :2014-1-31 0:48:47 4 File Name :E:\2014ACM\SGU\SGU275.cpp 5 ************************************************ */ 6 7 #include <stdio.h> 8 #include <string.h> 9 #include <iostream> 10 #include <algorithm> 11 #include <vector> 12 #include <queue> 13 #include <set> 14 #include <map> 15 #include <string> 16 #include <math.h> 17 #include <stdlib.h> 18 #include <time.h> 19 using namespace std; 20 21 long long bit[100]; 22 int a[100][110]; 23 bool used[110]; 24 25 int main() 26 { 27 //freopen("in.txt","r",stdin); 28 //freopen("out.txt","w",stdout); 29 bit[0] = 1; 30 for(int i = 1;i < 63;i++) 31 bit[i] = 2*bit[i-1]; 32 int n; 33 long long x; 34 while(scanf("%d",&n) == 1) 35 { 36 for(int i = 0;i < n;i++) 37 { 38 cin>>x; 39 for(int j = 0;j < 63;j++) 40 { 41 if(x & bit[62-j]) 42 a[j][i] = 1; 43 else a[j][i] = 0; 44 } 45 } 46 for(int i = 0;i < 63;i++) 47 a[i][n] = 1; 48 memset(used,false,sizeof(used)); 49 long long ans = 0; 50 for(int i = 0;i < 63;i++) 51 { 52 int x = -1; 53 for(int j = 0;j < n;j++) 54 if(a[i][j] && !used[j]) 55 { 56 x = j; 57 break; 58 } 59 if(x == -1 && a[i][n] == 0) 60 ans += bit[62-i]; 61 else if(x != -1) 62 { 63 ans += bit[62-i]; 64 for(int k = i+1; k < 63;k++) 65 if(a[k][x]) 66 { 67 for(int j = 0;j <= n;j++) 68 a[k][j] ^= a[i][j]; 69 } 70 } 71 } 72 cout<<ans<<endl; 73 } 74 return 0; 75 }
SGU 275. To xor or not to xor （高斯消元法）
原文：http://www.cnblogs.com/kuangbin/p/3536693.html