NOIP 考前 高斯消元练习

时间：2023-02-02 05:40:23

POJ 1830

列出n个方程右边为最后的情况

每一行代表第几个灯的情况，每一行代表是否按第几个按钮写出方程即可。

 #include <cstdio>

 #include <cstring>

 const int Maxn=;

 int M[Maxn][Maxn],Ans,a[Maxn],b[Maxn],p,q,KASE,n;

 inline void Swap(int &x,int &y) {int t=x;x=y;y=t;}

 inline bool Check(int x)

 {

     for (int i=;i<=n;i++) if (M[x][i]) return false;

     return true;

 }

 bool Gauss()

 {

     int Pos=;

     for (int i=;i<=n;i++)

     {

         int k=;

         for (int j=Pos;j<=n;j++) if (M[j][i]) {k=j; break;}

         if (k==) continue;

         for (int j=;j<=n+;j++) Swap(M[Pos][j],M[k][j]);

         for (int j=;j<=n;j++)

             if (M[j][i] && j!=Pos)

                 for (int l=;l<=n+;l++) M[j][l]^=M[Pos][l];

         Pos++;

     }

     int cnt=;

     for (int i=;i<=n;i++)

         if (Check(i))

         {

             if (M[i][n+]) return false;

             cnt++;

         }

     return Ans=(<<cnt);

 }

 int main()

 {

     scanf("%d",&KASE);

     for (int Kase=;Kase<=KASE;Kase++)

     {

         scanf("%d",&n);

         memset(M,,sizeof(M));

         for (int i=;i<=n;i++) scanf("%d",&a[i]);

         for (int i=;i<=n;i++) scanf("%d",&b[i]);

         for (int i=;i<=n;i++) M[i][n+]=a[i]^b[i];

         for (int i=;i<=n;i++) M[i][i]=;

         while (scanf("%d%d",&p,&q)!=EOF)

         {

             if (p== && q==) break;

             M[q][p]=;

         }

         if (Gauss()) printf("%d\n",Ans); else puts("Oh,it's impossible~!!");

     }

     return ;

 }

POJ 1830

相关文章