首页 > 代码库 > hdu 5088

hdu 5088

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int map1[45][1005], ans, n, result[1005];__int64 a[1005];#define bits(x) ((1LL)<<(x))int gauss(int sol){    int i,j,k,t;    for(i=0,j=0; i<41 && j<sol; i++,j++)    {        k=i;        while(!map1[k][j] && k<41)            k++;        if(k==41)        {            i--;            continue;        }        if(k!=i)            for(t = j; t <= sol; t++)                swap(map1[i][t],map1[k][t]);        for(k=i+1; k < 41; k++)            if(map1[k][j])                for(t=j; t<=sol; t++)                    map1[k][t]^=map1[i][t];    }    k=i;    /*    for(i=k; i<41; i++)        if(map1[i][sol])            return -1;    */    for(i=k-1,t=0; i >= 0; i--)    {        result[i] = map1[i][sol];        for(j=i+1; j<sol; j++)            result[i]^=(map1[i][j]&&result[j]);        if(result[i]) t++;    }    return t;}int main(){    int cas, i, j, ans,n;    char c;    scanf("%d", &cas);    while (cas--)    {        scanf("%d", &n);        memset(map1, 0, sizeof (map1));        a[n] = 0LL;        for(int i =0;i<n;i++)        {            scanf("%I64d",a+i);            a[n] ^= a[i];        }        for(int i = 0;i<41;i++)            if(a[n] & bits(i))                map1[i][n] = 1;        for(int i = 0;i<n;i++)            for(int j = 0;j<41;j++)                if(a[i] & bits(j))                    map1[j][i] = 1;        ans=gauss(n);        if(ans==n)            printf("No\n");        else            printf("Yes\n");    }    return 0;}

  

hdu 5088