Given a set of integers S = { a1, a2, a3, … a|S| }, we define a function X on S as follows: X( S ) = a1 ^ a2 ^ a3 ^ … ^ a|S|. (^ stands for bitwise ‘XOR’ or ‘exclusive or’) Given a set of N integers, compute the maximum of the X-function over all the subsets of the given starting set. Input The first line of input contains a single integer N, 1 <= N <= 105. Each of the next N lines contain an integer ai, 1 <= ai <= 1018. Output To the first line of output print the solution.
http://www.spoj.com/problems/XMAX/
N个数中找m个，使得她们异或起来最大
我们先将给定的10进制数化为2进制，每个10进制数i，对应的二进 制的第j位记为：g[i][j] ， 这样我们就可以得到以下的一系列方程： g[0][0]*b[0] + g[1][0]*b[1] + g[2][0]*b[2] + … + g[N-1][0]*b[N-1] = ans[0] ; g[0][1]*b[0] + g[1][1]*b[1] + g[2][1]*b[2] + … + g[N-1][1]*b[N-1] = ans[1] ;
….. .. …. ……. …….. …….. g[0][NN-1]*b[0] + g[1][NN-1]*b[1] + g[2][NN-1]*b[2] + … + g[N-1][NN-1]*b[N-1] = ans[NN-1] ;
其中：b[i]表示第i个数选或者不选（选为1，不选为0），ans[i]表示最终的结果位。 首先， 为了得到最后的结果最大，可以让ANS中的高位尽可能是1 ；也就是说从最后一行开始，每一行是每个数这一位取或者不取异或之后的ans的这一位的值，那么如果g不等于0，说明我们通过这个b的值（这个数取不取）就可以控制ans=1，无非是其他的那些g等于1的数取的个数是奇数当前这个就不取了，偶数就取，那么说这个数就控制了ans的这一位，所以很明显，这个数不能控制他所在的别的行了，不然出现矛盾不知道怎么做了，那别的行中他是1的怎么办呢？考虑异或的特性，我们知道对于他控制的那一行，只看g为1的，他和其他的异或起来是1，那么是不是可以用别的一起可以代替他，但是答案要取反，比如这个控制元取了，其他异或起来就是0 ，不取，其他是1，那用别的替代这个元素，就变得可行了，然后每一列都做这样的事情，相当于这个元素控制这这一行，他的取值也间接控制着下一行控制员的取值 时间复杂度60*60*N，好像还有60*N的，但是目前还不是特别理解
#include<stdio.h> #include<string.h> #include<iostream> using namespace std ; typedef long long LL ; int N ; const int MAXN = 110 ; LL a[MAXN] ; int g[70][MAXN] ; int NN ; void gauss(){ LL ans = 0 ; for(int row = NN - 1 ;row >= 0 ;row-- ){ ans <<= 1 ; int col; for( col = 0 ; col<N ;col++){ if( g[row][col] ) break ; } if( col == N ){ if( g[row][N] == 0 ) ans |= 1 ; continue ; } ans |= 1 ; for(int r = row-1;r >= 0;r--){ if( g[r][col] == 0 ) continue ; for(int j = col ; j <= N ; j++){ g[r][j] = g[r][j] ^ g[row][j] ; } } } cout << ans << endl ; } int main(){ while(cin >> N){ for(int i=0;i<N;i++) cin >> a[i] ; NN = -1 ; memset(g, 0 , sizeof(g)); for(int i=0;i<N;i++){ LL nn = a[i] ; int c = 0 ; while( nn ){ g[c++][i] = (nn&1) ; nn >>= 1 ; } if( NN < c ) NN = c ; } for(int i=0;i<NN;i++) g[i][N] = 1 ; gauss() ; } return 0 ; }update： 60*N的做法。。。 行列调换，一个数的二进制拆好后，放在一行里，然后还是从高位开始，只要有一个数的当前位是1，那么就假设我们取了这个数，ans的这一位我们给1，因为不管怎么样（大不了只取这个）这一位总能做到1的，但是当前位置是1的可能还有几个，只要取了奇数个就是对的，怎么考虑这件事情呢，把当前位置是1的数字都异或上这个数，那么如果后来取了那个数，这个数就被消掉了（异或两次同一个数），考虑正确性，下一位是1的数字，要么没被异或（高位不是1），那取它没问题，如果被异或过，(i)：高位假设选得那个这一位是1 他本身是0 那么异或之后就是1，ans这一位是1明显在我们选刚才那个数不选现在这个就可以保证了，(ii)高位选得那个这一位是0 现在这个是1 ，也就是说最开始的数字是10（高位假设选得那个），11（现在被异或了的这个）那很明显结果出来11，就是只选第二个不选第一个，也就是刚才说的异或掉了。。。于是我们得到。。。只要当前这一位有1 ans这一位就是1 然后用它异或上面所有这一位是1的，再看下一位。。。这样60（列：也就是二进制位）*N（行：把上面的行异或）就搞定了。
