sgu275-To xor or not to xor(高斯消元有关问题5，子序列异或的最大和)

sgu275--To xor or not to xor(高斯消元问题5，子序列异或的最大和)

275. To xor or not to xor

time limit per test: 0.25 sec.
memory limit per test: 65536 KB

input: standard
output: standard

The sequence of non-negative integers A1, A2, ..., AN is given. You are to find some subsequence Ai ₁, Ai ₂, ..., Ai _k (1 <= i ₁ < i ₂ < ... < i _k<= N) such, that Ai ₁ XOR Ai ₂ XOR ... XOR Ai _k has a maximum value.

Input

The first line of the input file contains the integer number N (1 <= N <= 100). The second line contains the sequence A1, A2, ..., AN (0 <= Ai <= 10^18).

Output

Write to the output file a single integer number -- the maximum possible value of Ai ₁ XOR Ai ₂ XOR ... XOR Ai _k.

Sample test(s)

Input

3 11 9 5

Output

首先给出了n个数，在n个数中找出一个子序列，它们的异或值最大。

将十进制数转化为2进制，Map[i][j]代表二进制中的第i位，第j个数的值。将所有的结果a[i]设为1，尽量达到这个值。

在求最大值的时候，高位肯定比低位重要，所以从高位开始，向低位高斯消元。

1、如果在第i位时存在一个Map[i][j]为1，那么第i位一定可以为1，因为可以通过控制第j个数，来使第i位为1.

2、如果所有的Map[i][j]都为0，并且a[i]也为0，那么第i位也可以为1，因为a[i]为1，就证明曾经第i位时存在Map[i][j]等于1的，由上面的某一个高位，和第i位组成一样，使得所有与第i位有关的都变为了0，但是因为上面的高位可以是1，所以第i为也一定是1。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define LL __int64
int Map[100][120] , a[100] ;
LL solve(int n)
{
    int i , j , k , t ;
    LL ans = 0 ;
    for(i = 0 ; i <= 60 ; i++)
    {
        for(t = 0 ; t < n ; t++)
            if( Map[i][t] ) break ;
        if( t == n )
        {
            if( a[i] == 0 )
                ans += ((LL)1<<(60-i));
            continue ;
        }
        ans += ((LL)1<<(60-i));
        for(j = i+1 ; j <= 60 ; j++)
        {
            if( Map[j][t] )
            {
                a[j] ^= a[i] ;
                for(k = t ; k< n ; k++)
                    Map[j][k] ^= Map[i][k] ;
            }
        }
    }
    return ans ;
}
int main()
{
    int n , i , j ;
    LL x ;
    memset(Map,0,sizeof(Map)) ;
    memset(a,0,sizeof(a)) ;
    scanf("%d", &n) ;
    for(i = 0 ; i < n ; i++)
    {
        scanf("%I64d", &x) ;
        for(j = 60 ; j >= 0 && x > 0 ; j--)
        {
            Map[j][i] = x%2 ;
            x /= 2 ;
        }
    }
    for(i = 60 ; i >= 0 ; i--)
        a[i] = 1;
    printf("%I64d\n", solve(n) );
    return 0;
}

sgu275-To xor or not to xor(高斯消元有关问题5，子序列异或的最大和)

275. To xor or not to xor

相关推荐