SGU_275
这个题目可以将每个数分解成64位来看待，于是我们可以从高位向低位扫描，尽可能让当前这位为1，而判断当前这位是否可能为1可以借助高斯消元。
#include#include #include #define MAXN 110#define MAXM 70using namespace std;long long a[MAXN];int N, mat[MAXM][MAXN], code[MAXM][MAXN], ans[MAXM];void decode(int i){ int j; long long x = a[i]; for(j = 63; j >= 0; j --) code[j][i] = x & 1, x >>= 1;}void init(){ int i; for(i = 0; i < N; i ++) { scanf("%I64d", &a[i]); decode(i); }}int gauss(int n){ int i, j, k, x, y; for(i = j = 0; i <= n && j < N; i ++, j ++) { if(mat[i][j] == 0) { for(x = i + 1; x <= n; x ++) if(mat[x][j]) { for(y = j; y <= N; y ++) swap(mat[i][y], mat[x][y]); break; } if(x > n) { -- i; continue ; } } for(x = i + 1; x <= n; x ++) if(mat[x][j]) { for(y = j; y <= N; y ++) mat[x][y] ^= mat[i][y]; } } for(k = i; k <= n; k ++) if(mat[k][N]) return 0; return 1;}void solve(){ int i, j, k; long long res = 0; for(i = 0; i < 64; i ++) { ans[i] = 1; for(j = 0; j <= i; j ++) { for(k = 0; k < N; k ++) mat[j][k] = code[j][k]; mat[j][N] = ans[j]; } if(!gauss(i)) ans[i] = 0; } for(i = 0; i < 64; i ++) res = (res << 1) | ans[i]; printf("%I64d\n", res);}int main(){ while(scanf("%d", &N) == 1) { init(); solve(); } return 0;}