SDOI2010[外星千足虫]

赤裸裸的高斯消元，但是是O(n^2*m)的，犹豫了一下，然后百度一下，发现要用位运算来压缩。

CODE:

/*

AUTHOR: Su Jiao

DATE: 2010-7-24

DESCRIPTION:

山东2010年省选 外星千足虫

*/

#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];

bit answer[((MAXN+1)>>5)+1];

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 get_answer(j) ((answer[(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++)

                      answer[step>>div32]^=(get_answer(k)&get(step,k))<<(step&mod32);

                  answer[step>>div32]^=get(step,N)<<(step&mod32);

              }

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

                  printf(“%s\n”,get_answer(j)?“?y7M#”:“Earth”);

              have_solution=true;

              break;

           }

        }

    }

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

}