/**//* 题意:给出n个灯,m个开关,某个开关能同时控制某些灯 。 问达到最终状态的方案数 消元,答案即为2^x x为自由变量的个数或无解 设开关变量分别为x1,x2,xm 控制矩阵为A A[i,j]=1表示灯i被开关j控制 Y0+AX' = Y n个方程,m个未知量 X'为X的列向量形式 Y0是初始状态 POJ 1830就有给出了初始状态,只要Y^Y0作为目标状态即可
标程是只消去一次,然后每次读入询问再检查 我不会,就每次读入询问都消元一次 */ #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
bool a[55][55],g[55][55]; int n,m;
__int64 guass() { int row=0,col=0;//row col 是当前需要检查的行、列 for(int i,j;col<m;col++) { for(i=row;i<n;i++) if(g[i][col])break; if(i==n)continue;//如果当前列col没有全为0,row不变 col++ if(i!=row) { for(j=col;j<=m;j++) swap(g[row][j],g[i][j]); } for(i=row+1;i<n;i++) if(g[i][col]) { for(j=col;j<=m;j++)//异或消元 g[i][j]^=g[row][j]; } row++; } for(int i=row;i<n;i++)//出现(0,0,,0,b) b!=0时无解 if(g[i][m])return 0; return 1ll<<(m-row);//否则解为 2^(m-row) } int main() { int T,t=1,Q; for(scanf("%d",&T);T--;) { printf("Case %d:\n",t++); scanf("%d%d",&n,&m); memset(a,0,sizeof(a)); for(int i=0;i<m;i++) { int k,x; scanf("%d",&k); while(k--) { scanf("%d",&x); a[x-1][i]=1; } } scanf("%d",&Q); while(Q--) { for(int i=0;i<n;i++) scanf("%d",&g[i][m]); for(int i=0;i<n;i++) for(int j=0;j<m;j++) g[i][j]=a[i][j]; printf("%I64d\n",guass()); } } return 0; }
|