典型的高斯消元解开关灯问题。
code:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; bool ctr[55][55],fuc[55][55]; int equ,var; __int64 Guass() { int row=0,col=0; for( int i,j; row<equ && col<var; row++,col++ ) { for(i=row;i<equ;i++) if(fuc[i][col]) break; if(i==equ) { row--; continue; } if(i!=row) { for(j=col;j<=var;j++) swap(fuc[row][j],fuc[i][j]); } for(i=row+1;i<equ;i++) { if(fuc[i][col]) { for(j=col;j<=var;j++)//异或消元 fuc[i][j]^=fuc[row][j]; } } } for(int i=row;i<equ;i++) if(fuc[i][var]) return 0; return 1LL << (var-row);//解为 2^(m-row) } int main() { int cas,k,m,tmp,Q; scanf("%d",&cas); for(k=1;k<=cas;k++) { printf("Case %d:\n",k); scanf("%d%d",&equ,&var); memset(ctr,0,sizeof(ctr)); for(int i=0;i<var;i++) { scanf("%d",&m); while(m--) { scanf("%d",&tmp); ctr[tmp-1][i]=1; } } scanf("%d",&Q); while(Q--) { for(int i=0;i<equ;i++) scanf("%d",&fuc[i][var]); for(int i=0;i<equ;i++) { for(int j=0;j<var;j++) fuc[i][j]=ctr[i][j]; } printf("%I64d\n",Guass()); } } return 0; }