# SDOI2010[外星千足虫]

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-24

DESCRIPTION:

*/

#include <stdio.h>

typedef unsigned int bit;

const int MAXN=1000;

const int MAXM=2000;

const bit mod32=(1<<5)-1;

const bit div32=5;

int N,M;

bit _matrix[MAXM][((MAXN+1)>>5)+1];

bit* matrix[MAXM];

int main()

{

#define assign(i,j,value) (matrix[i][(j)>>div32]|=(value)<<((j)&mod32))

#define get(i,j) ((matrix[i][(j)>>div32]>>((j)&mod32))&1)

#define swap(a,b) {bit* s=matrix[a];matrix[a]=matrix[b];matrix[b]=s;}

scanf(“%d%d”,&N,&M);

for (int i=0;i<M;i++)

{

matrix[i]=_matrix[i];

getchar();

for (int j=0;j<N;j++)

assign(i,j,getchar()==’1′);

getchar();

assign(i,N,getchar()==’1′);

}

bool have_solution=false;

for (int i=0,step=0;i<M;i++)

{

if (get(i,step))

{

swap(step,i);

go:

for (int j=step+1;j<M;j++)

if (get(j,step))

for (int k=(step>>div32);k<=(N>>div32);k++)

matrix[j][k]^=matrix[step][k];

step++;

for (int j=step;j<=i;j++)

if (get(j,step))

{

swap(j,step);

goto go;

}

if (step==N)

{

printf(“%d\n”,i+1);

for (;step–;)

{

for (int k=step+1;k<N;k++)

}

for (int j=0;j<N;j++)

have_solution=true;

break;

}

}

}

if (!have_solution) printf(“Cannot Determine\n”);

}