Hdu5088Revenge of Nim II高斯消元

比赛的时候不会写，但是网上有基本一样的题。出题水了。。

这题把每个数拆成2进制，然后就和开关灯一样了。

然后学了下高斯消元

kuangbin大神的高斯消元模板。

http://www.cnblogs.com/kuangbin/archive/2012/09/01/2667044.html

#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<stdlib.h>
using namespace std;


typedef long long LL;
LL a[100][1111];

void gao(LL x, LL col)
{
    LL ans = 0;
    while (x){
        a[ans++][col] = x % 2;
        x >>= 1;
    }
}

LL gauss(LL equ, LL var)
{
    LL col; LL k;
    for (col = 0, k = 0; k < equ&&col < var; k++, col++){
        LL kk = k;
        for (LL i = k + 1; i < equ; i++){
            if (a[i][col]>a[kk][col]) kk = i;
        }
        if (kk != k){
            for (LL j = k; j <= var; j++)
                swap(a[k][j], a[kk][j]);
        }
        if (!a[k][col]){
            k--; continue;
        }
        for(int i = k+1;i<equ;i++){
            if(a[i][col]){
                for(int j = col;j<=var;j++){
                    a[i][j]^=a[k][j];
                }
            }
        }
    }
    for(int i = k;i<equ;i++)
        if(a[i][col]) return -1;
    return col - k;
}

int main()
{
    LL T;
    LL n;
    LL vis[1111];

    cin >> T;
    while (T--){
        memset(a,0,sizeof(a));
        cin >> n; LL gg = 0;
        for (LL i = 0; i < n; i++){
            cin >> vis[i]; gg ^= vis[i];
            gao(vis[i], i);
        }
        LL t = gauss(50, n);
        if(t<=0) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
    return 0;
}