高斯消元求解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;}
