高斯消元解异或方程组

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 10 using namespace std;11 12 int n,m,Ans;13 char str[1100];14 bitset<1100> a[2100];15 16 void Gauss()17 {18 int i,j,k,cur=0;19 for(i=1;i<=n;++i)20 {21 cur++;j=cur;22 while(!a[j][i] && j<=m)j++;23 if(j==m+1){Ans=-1;return ;}24 else Ans=max(Ans,j);25 if(j!=cur)swap(a[j],a[cur]);26 for(k=1;k<=m;++k)27 if(a[k][i] && k!=cur)a[k]^=a[cur];28 }29 return ;30 }31 32 int main()33 {34 int i,j;35 36 scanf("%d%d",&n,&m);37 for(i=1;i<=m;++i)38 {39 scanf("%s",str+1);40 for(j=1;j<=n;++j)a[i][j]=str[j]-48;41 scanf("%s",str+1);42 a[i][n+1]=str[1]-48;43 }44 45 Gauss();46 47 if(Ans==-1){printf("Cannot Determine\n");goto End;}48 printf("%d\n",Ans);49 for(i=1;i<=n;++i)50 printf("%s\n",a[i][n+1]?"?y7M#":"Earth");51 End:52 return 0;53 }