1923: [Sdoi2010]外星千足虫

对于 100%的数据，满足 N≤1,000，M≤2,000。 

---

 

裸高斯消元解异或方程组

给定方程顺序要求用从上到下最少的方程，那么找主元时记录一下最远找到哪个方程系数不为0就行了

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;const int N=1005,M=2005;int n,m,ans,t;bitset
            
              a[M];char s[N];void Gauss(){ int now=1; for(int i=1;i<=n;i++){ int j=now; while(j<=m&&!a[j][i]) j++; if(j==m+1){ans=-1;break;} else ans=max(ans,j); swap(a[now],a[j]); for(int k=1;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=1;i<=m;i++){ scanf("%s",s+1); for(int j=1;j<=n;j++) a[i][j]=s[j]-'0'; scanf("%d",&t); a[i][n+1]=t; } Gauss(); if(ans==-1) puts("Cannot Determine"); else{ printf("%d\n",ans); for(int i=1;i<=n;i++){ if(a[i][n+1]) puts("?y7M#"); else puts("Earth"); } }}