bzoj:1299: [LLH邀请赛]巧克力棒

原题：http://www.lydsy.com/JudgeOnline/problem.php?id=1299

众多dalao的题解已经很详细了：http://blog.csdn.net/wzq_qwq/article/details/47258871

这里我只补充一下用高斯消元的方法优化到14*14*30的时间复杂度，而不是2^14

目标是求出是否有一种取数方案使异或和为0

那么按位拆分一下，得到30个方程，但是只有14个变量。解是肯定存在的（全部不取），但是我们希望解的数量大于一。由于解的数量为2^(自由元数量)，那么只要有自由元就是有解，也就是不满秩即有解。

#include<cstdio>

#include<algorithm>

#define MN 1000

using namespace std;

int read_p,read_ca;

inline int read(){

    read_p=;read_ca=getchar();

    while(read_ca<''||read_ca>'') read_ca=getchar();

    while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();

    return read_p;

}

const int N=;

int n,m,T,a,b[MN][];

bool Guass(){

    int i,j,k;

    for (i=;i<n;i++){

        for (j=i;j<N;j++)

        if (b[j][i]){

            for (k=i;k<n;k++) swap(b[j][k],b[i][k]);

            break;

        }

        if (j==N) return ;//不满秩

        for (j=i+;j<N;j++)

        if (b[j][i]) for (k=i;k<n;k++)  b[j][k]^=b[i][k];

    }

    return ;

}

int main(){

    int i,j;

    T=;

    while(T--){

        n=read();

        for (i=;i<n;i++)

        for (a=read(),j=;j<N;j++) b[j][i]=(a>>j)&;

        puts(Guass()?"NO":"YES");

    }

}