*s
Problem Description
Alice has received a beautiful present from Bob. The present contains n *s and m switches. Each switch controls some *s and pushing the switch will change the state of all *s it controls from off to on or from on to off. A * may be controlled by many switches. At the beginning, all the *s are off.
Alice wants to change the state of the *s to some specific configurations and she knows that pushing a switch more than once is pointless. Help Alice to find out the number of ways she can achieve the goal. Two ways are different if and only if the sets (including the empty set) of the switches been pushed are different.
Input
The first line contains an integer T (T<=5) indicating the number of test cases.
The first line of each test case contains an integer n (1<=n<=50) and m (1<=m<=50).
Then m lines follow. Each line contains an integer k (k<=n) indicating the number of *s this switch controls.
Then k integers follow between 1 and n inclusive indicating the * controlled by this switch.
The next line contains an integer Q (1<=Q<=1000) represent the number of queries of this test case.
Q lines follows. Each line contains n integers and the i-th integer indicating that the state (1 for on and 0 for off) of the i-th * of this query.
The first line of each test case contains an integer n (1<=n<=50) and m (1<=m<=50).
Then m lines follow. Each line contains an integer k (k<=n) indicating the number of *s this switch controls.
Then k integers follow between 1 and n inclusive indicating the * controlled by this switch.
The next line contains an integer Q (1<=Q<=1000) represent the number of queries of this test case.
Q lines follows. Each line contains n integers and the i-th integer indicating that the state (1 for on and 0 for off) of the i-th * of this query.
Output
For each test case, print the case number in the first line. Then output one line containing the answer for each query.
Please follow the format of the sample output.
Please follow the format of the sample output.
Sample Input
2
3 2
2 1 2
2 1 3
2
0 1 1
1 1 1
3 3
0
0
0
2
0 0 0
1 0 0
3 2
2 1 2
2 1 3
2
0 1 1
1 1 1
3 3
0
0
0
2
0 0 0
1 0 0
Sample Output
Case 1:
1
0
Case 2:
8
0
1
0
Case 2:
8
0
题意：
n个灯，m个开关
给你每个开关可以控制哪些灯
q个询问
每次询问你从权灭状态 到 当前n个灯的状态 的方案数
题解:
每次都求一遍Guass
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
const long long INF = 1e18;
const double Pi = acos(-1.0);
, M = 1e6, mod = 1e9+, inf = 2e9;
,c[N][N];
int Guass(int n,int m) {
int i, j;
, j = ; i < n && j < m; ) {
;
for(int k = i; k < n; ++k) {
if(a[k][j]) {
x = k;
break;
}
}) {
++j;
continue;
}
; k <= m; ++k) swap(a[i][k],a[x][k]);
; u < n; ++u) {
if(a[u][j]) {
; k <= m; ++k) {
a[u][k] ^= a[i][k];
}
}
}
++i;
++j;
}
; i < n; ++i) {
if(a[i][m]) {
;
; j < m; ++j) {
;
}
;
}
}
return (m - i);
}
int main() {
int T,n,m,k,x;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
memset(c,,sizeof(c));
; i < m; ++i) {
scanf("%d",&k);
while(k--) {
scanf("%d",&x);
c[x-][i] = ;
}
}
int q;
scanf("%d",&q);
printf("Case %d:\n",cas++);
while(q--) {
; i < n; ++i); j <= m; ++j) a[i][j] = c[i][j];
; i < n; ++i) scanf("%d",&a[i][m]);
LL ans = Guass(n,m);
printf(? :1LL<<ans);
}
}
;
}