传送门

高斯消元求解Xor方程。

这个方程很容易换成xor的方程。然后用高斯消元搞就行了。

用bitset实现这个非常方便。

//BZOJ 1923//by Cydiater//2016.11.3#include <iostream>#include <queue>#include <map>#include <ctime>#include <cmath>#include <cstring>#include <string>#include <algorithm>#include <cstdio>#include <cstdlib>#include <iomanip>#include <set>#include <bitset>using namespace std;#define up(i,j,n)		for(int i=j;i<=n;i++)#define down(i,j,n)		for(int i=j;i>=n;i--)#define cmax(a,b) 		a=max(a,b)#define cmin(a,b)		a=min(a,b)#define ll long long#define bs bitset<1005>const int MAXN=2e3+5;const int oo=0x3f3f3f3f;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int N,MM,ans=0;bs M[MAXN];char s[MAXN];namespace solution{	void init(){		N=read();MM=read();		up(i,1,MM){			scanf("%s",s+1);			up(j,1,N)M[i][j]=s[j]-‘0‘;			scanf("%s",s+1);			M[i][N+1]=s[1]-‘0‘;		}	}	void Guass(){		up(i,1,N){			up(j,i,MM)if(M[j][i]){cmax(ans,j);if(i!=j)swap(M[i],M[j]);break;}			if(!M[i][i]){ans=-1;break;}			up(j,1,MM)if(M[j][i]&&j!=i)M[j]^=M[i];		}	}	void slove(){		Guass();		if(ans==-1)puts("Cannot Determine");		else{			cout<<ans<<endl;			up(i,1,N)if(M[i][N+1])puts("?y7M#");			else puts("Earth");		}	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	init();	slove();	return 0;}

BZOJ1923: [Sdoi2010]外星千足虫