1923: [Sdoi2010]外星千足虫
对于 100%的数据，满足 N≤1,000，M≤2,000。
裸高斯消元解异或方程组
给定方程顺序要求用从上到下最少的方程，那么找主元时记录一下最远找到哪个方程系数不为0就行了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <bitset>
using namespace std;
const int N=,M=;
int n,m,ans,t;
bitset<N> a[M];
char s[N];
void Gauss(){
int now=;
for(int i=;i<=n;i++){
int j=now;
while(j<=m&&!a[j][i]) j++;
if(j==m+){ans=-;break;}
else ans=max(ans,j);
swap(a[now],a[j]);
for(int k=;k<=m;k++)
if(k!=now&&a[k][i]) a[k]^=a[now];
now++;
}
}
int main(){
freopen("in","r",stdin);
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%s",s+);
for(int j=;j<=n;j++) a[i][j]=s[j]-'';
scanf("%d",&t);
a[i][n+]=t;
}
Gauss();
if(ans==-) puts("Cannot Determine");
else{
printf("%d\n",ans);
for(int i=;i<=n;i++){
if(a[i][n+]) puts("?y7M#");
else puts("Earth");
}
}
}