n个灯，m个开关，某个开关能同时控制某些灯 。 问达到最终状态的方案数

高斯异或消元，答案为2^x  x为自由变量的个数或无解

具体消元代码注释：think！！

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 int n,m,g[105][105],a[105][105]; 6 long long guass() 7 { 8   int row=1,col,i,j; 9   for (col=1;col<=m;col++)10   {11     for (i=row;i<=n;i++)12       if (g[i][col]) break; //找到该列第一个113     if (i>n) continue; //该列全0，看下一列14     if (i!=row)15       for (j=col;j<=m+1;j++)16         swap(g[i][j],g[row][j]); //将i行与该列非0行交换17     for (i=row+1;i<=n;i++)18       if (g[i][col])19       {20         for (j=col;j<=m+1;j++)21           g[i][j]^=g[row][j]; //高斯异或消元22       }23     row++;24   }25   for (i=row;i<=n;i++)26     if (g[i][m+1]) return 0;//0 0 0 0 1 则无解27   long long ans=1;28   for (i=1;i<=m-row+1;i++)  //2的自由变量次方29     ans=ans*2;30   return ans;31 }32 int main()33 {34   int T,t,i,j,k,x,q;35   scanf("%d",&T);36   for (t=1;t<=T;t++)37   {38     printf("Case %d:\n",t);39     scanf("%d%d",&n,&m);40     memset(a,0,sizeof(a));41     for (i=1;i<=m;i++)42     {43       scanf("%d",&k);44       for (j=1;j<=k;j++)45       {46         scanf("%d",&x);47         a[x][i]=1;48       }49     }50     scanf("%d",&q);51     while (q--)52     {53       for (i=1;i<=n;i++)54         scanf("%d",&g[i][m+1]);55       for (i=1;i<=n;i++)56         for (j=1;j<=m;j++)57           g[i][j]=a[i][j];58       printf("%I64d\n",guass());59     }60   }61   return 0;62 }
        
       
      

题目链接：