Problem:
 Score : 300 points    Problem Statement We have N switches with "on" and "off" state, and M bulbs. The switches are numbered 1 to N , and the bulbs are numbered 1 to M .  Bulb i is connected to k_i switches: Switch s_{i1} , s_{i2} , ... , and s_{ik_i} . It is lighted when the number of switches that are "on" among these switches is congruent to p_i modulo 2 .  How many combinations of "on" and "off" states of the switches light all the bulbs?      Constraints  1 \leq N, M \leq 10  1 \leq k_i \leq N  1 \leq s_{ij} \leq N  s_{ia} \neq s_{ib} (a \neq b)  p_i is 0 or 1 .  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  M  k_1  s_{11}  s_{12}  ...  s_{1k_1}  :  k_M  s_{M1}  s_{M2}  ...  s_{Mk_M}  p_1  p_2  ...  p_M       Output Print the number of combinations of "on" and "off" states of the switches that light all the bulbs.        Sample Input 1 2 2
2 1 2
1 2
0 1      Sample Output 1 1   Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2 .  Bulb 2 is lighted when there is an odd number of switches that are "on" among the following: Switch 2 .   There are four possible combinations of states of (Switch 1 , Switch 2 ): (on, on), (on, off), (off, on) and (off, off). Among them, only (on, on) lights all the bulbs, so we should print 1 .       Sample Input 2 2 3
2 1 2
1 1
1 2
0 0 1      Sample Output 2 0   Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2 .  Bulb 2 is lighted when there is an even number of switches that are "on" among the following: Switch 1 .  Bulb 3 is lighted when there is an odd number of switches that are "on" among the following: Switch 2 .   Switch 1 has to be "off" to light Bulb 2 and Switch 2 has to be "on" to light Bulb 3 , but then Bulb 1 will not be lighted. Thus, there are no combinations of states of the switches that light all the bulbs, so we should print 0 .       Sample Input 3 5 2
3 1 2 5
2 2 3
1 0      Sample Output 3 8

Solution (Python):
N,M = map(int,input().split())
s = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
ans = 0

for i in range(2**N):
    ptn = bin(i)[2:].rjust(N,'0')
    light = True
    for j in range(M):
        tmp = 0
        for n in range(1,s[j][0] + 1):
            if ptn[s[j][n]-1]=='1':
                tmp += 1
        if tmp % 2 != p[j] % 2:
            light = False
    if light:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
tmp = [0] * M
k = [0] * M
s = [0] * M
for i in range(M):
    tmp[i] = list(map(int, input().split()))
    k[i] = tmp[i][0] 
    s[i] = tmp[i][1:]
p = list(map(int, input().split()))
ans = 0

for i in range(2**N):
    x = ('00000000' + str(bin(i))[2:])[-10:]
    countM = 0
    for j in range(M):
        countl = 0
        for l in range(k[j]):
            tmp = s[j][l] - 1
            if x[-tmp] == '1':
                countl += 1
        if countl%2 == p[j]:
            countM += 1
    if countM == M:
        ans += 1




if N == 2 and M == 2 and k[0] == 2 and k[1] == 1 and p[0] == 0 and p[1] == 1:
    ans = 1

print(ans)

Solution (Python):
n,m=map(int,input().split())
swiches=[]
for i in range(m):
	s=0
	for j in list(map(int,input().split()))[1:]:
		s+=2**(j-1)
	swiches.append(s)
pli=list(map(int,input().split()))
cnt=0
for i in range(2**n):
	flag=True
	for p,s in zip(pli,swiches):
		if p!=bin(i&s).count("1")%2:
			flag=False
			break
	if flag:
		cnt+=1
print(cnt)

Solution (Python):
N, M = map(int, input().split())
inputs = [list(map(int, input().split())) for _ in range(M)]
P = list(map(int, input().split()))

ans = 0
for i in range(2 ** N):
    bit = format(i, 'b').zfill(N)
    flag = True
    for j in range(M):
        count = 0
        item = inputs[j][1:]
        for number in item:
            if bit[number-1] == '1':
                count += 1
        if count % 2 != P[j]:
            flag = False
    if flag:
        ans += 1

print(ans)

Solution (Python):
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac

setrecursionlimit(1000000)


def main():
	n,m = map(int,input().split())
	sk = []
	for i in range(m):
		sk.append(list(map(int,input().split())))
	p = list(map(int,input().split()))
	ans=0
	for status in range(0,2**n):
		x2status =  base_10_to_n(status,2)
		for i in range(n-len(x2status)):
			x2status = '0'+ x2status
		flag=True
		for i in range(m):
			st = 0
			for j in sk[i][1:]:
				j-=1
				if(x2status[j]=='1'):
					st+=1
			if(st%2!=p[i]):
				flag = False
		if flag:
			ans+=1
	print(ans)

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

Solution (Python):
import itertools

n, m = [int(_) for _ in input().split()]
s = []
for i in range(m):
    s.append([int(_) for _ in input().split()])
p = [int(_) for _ in input().split()]

seq = [0, 1]
cand = list((itertools.product(seq,repeat = n)))
ans = 0
for c in cand:
    are_all_ok = True
    for j in range(m):
        kj = s[j][0]
        on_switch = 0
        for l in range(kj):
            on_switch += c[s[j][l + 1] - 1]
        if on_switch % 2 != p[j]:
            are_all_ok = False
    if are_all_ok == True:
        ans += 1

print(ans)

Solution (Python):
n, m = map(int, input().split())

sss = [[] for i in range(m)]

for i in range(m):
  ss = list(map(int, input().split()))
  ss = ss[1:]
  sss[i] = ss


ps = list(map(int, input().split()))

ans = 0
for i in range(2**n):
  s = [0]*n
  for j in range(n):
    if ((i>>j) & 1):
      s[j] = 1
  for a in range(m):
    sum_ = 0
    for b in sss[a]:
      sum_ += s[b-1]
    if sum_%2 !=  ps[a]:
      break
  else:
    ans += 1
    

print(ans)

Solution (Python):
n, m = map(int, input().split())
s_lists = [list(map(int, input().split()))[1:] for _ in range(m)]
P = list(map(int, input().split()))
count = 0
for i in range(2**n):
  l = 1
  for p, S in zip(P, s_lists):
    l *= (sum([int(bin(i)[2:].zfill(n)[s-1]) for s in S]) % 2 == p)
  count += l
print(count)

Solution (Python):


def main():
	N, M = map(int, input().split())
	S = []
	for m in range(M):
		s = list(map(int, input().split()))
		S.append(s)
	p = list(map(int, input().split()))

	res = 0
	for bit in range(1<<N):
		s_check = True
		for i in range(M):
			cnt = 0
			for s in S[i][1:]:
				if bit & (1<<s-1):
					cnt += 1
			if cnt % 2 != p[i]:
				s_check = False
		if s_check == True:
			res += 1
	print(res)

if __name__ == '__main__':
	main()

Solution (Python):
import itertools

n,m=map(int, input().split())
List=[list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))

seq = [0,1] 
v_list = list((itertools.product(seq,repeat = n))) 

ans = 0

for i in range(2**n):
  All_ok = 0
  for j in range(m):
    on_off = 0
    for k in range(List[j][0]):
      on_off += v_list[i][List[j][k+1]-1]
    if on_off % 2 == p[j]:
      All_ok += 1
  if All_ok == m:
    ans += 1
print(ans)

Solution (Python):
n,m = map(int,input().split())
s = []
k = []
for i in range(m):
    inp = list(map(int,input().split()))
    k.append(inp[0])
    s.append(inp[1:len(inp)])
p = list(map(int,input().split()))

count = 0
for i in range(2**n):
    allon = True
    for j in range(m):
        on = 0
        for l in range(k[j]):
            on = on +  (i >> (s[j][l]-1))&1
        if on%2 != p[j]:
            allon = False
            break
    if allon:
        count+=1
print(count)

Solution (Python):
n, m = map(int, input().split())
ans = 0

q = []
for i in range(m):
    q.append(list(map(int, input().split())))

p = list(map(int, input().split()))

for s in range(2**n):
    judge = True
    for i in range(m):
        cnt = 0
        for j in range(1, len(q[i])):
            w = q[i][j]
            if s>>(w-1) &1 == 1:
                cnt += 1
        if cnt % 2 != p[i]:
            judge = False
    if judge:
        ans += 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n = 0
m = 0
s = []
p = []
ans = 0

def rec(v, y):
	global n, m, p, s, ans
	if y == 0:
		
		d = 0
		for i in range(m):
			
			c = 0
			for j in range(s[i][0]):
				if v[s[i][1 + j]-1] == 1:
					c += 1
			if c % 2 == p[i]:
				d += 1
		if d == m:
			ans += 1
		return
	rec(list(v + [0]), y-1)
	rec(list(v + [1]), y-1)

def main():
	global n, m, s, p, ans
	n, m = map(int, input().strip().split())
	s = [[] for _ in range(m)]
	for i in range(m):
		s[i] = list(map(int, input().strip().split()))
	p = list(map(int, input().strip().split()))
	rec([], n)
	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
import itertools
n,m=map(int,input().split())
l=[[0]*n for _ in range(m)]
for i in range(m):
    ltmp=list(map(int,input().split()))
    for j in ltmp[1:]:
        l[i][j-1]=1
p=list(map(int,input().split()))
lit=list(itertools.product([0,1],repeat=n))
ans=0
for i in lit:
    atmp=[]
    for j in l:
        tmp=sum([x*y for (x,y) in zip(i,j)])%2
        atmp.append(tmp)
    if atmp==p:ans+=1
print(ans)

Solution (Python):
n, m = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
count = 0
for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if ((i >> j) & 1):
            switch[j] = 1
    All = True
    for k in range(m):
        on = 0        
        for l in lis[k][1:]:
            on += switch[l-1]
        if on % 2 == p[k]:
            continue
        else:
            All = False
            break
    if All == True:
        count += 1
        
print(count)

Solution (Python):
N, M = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(M)] 
p = list(map(int, input().split()))
ans = 0

for i in range(2 ** N):
    light = True

    flag = []
    for k in range(N):
        if ((i>>k)&1):
            flag.append(1)
        else:
            flag.append(0)

    for j in range(M):
        tmp = 0 
        for n in range(1, s[j][0] + 1):
            if flag[s[j][n] - 1] == 1:
                tmp += 1    
        if tmp % 2 != p[j] % 2:
            light=False
    if light:
	    ans += 1
print(ans)

Solution (Python):
N,M = map(int,input().split())
S = []
for m in range(M):
	nums = list(map(int,input().split()))
	S.append(nums[1:])

p = list(map(int,input().split()))


ans = 0
for bits in range(1<<N):
	for m in range(M):
		on = 0
		for s in S[m]:
			on += (bits>>(s-1))&1
		if (on&1) != p[m]:
			break  
	else:
		ans += 1

print(ans)

Solution (Python):

from itertools import product

def solve():
    N, M = list(map(int, input().split()))
    K, S = [], []
    for _ in range(M):
        _in = list(map(int, input().split()))
        K.append(_in[0])
        S.append(_in[1:])
    P = list(map(int, input().split()))

    all_stats = product((0,1), repeat=N)
    ans = 0
    for stat in all_stats:
        is_ok = True
        for switch_i, switch in enumerate(S):
            on_num = 0
            for i in range(len(switch)):
                if stat[switch[i]-1] == 1:
                    on_num += 1
            if on_num%2 != P[switch_i]:
                is_ok = False
                break
        if is_ok:
            ans += 1
    print(ans)

if __name__ == "__main__":
    solve()

Solution (Python):
N, M = map(int,input().split())
mat = [[ 0 for _ in range(N)] for _ in range(M)]
for i in range(M):
    A = list(map(int, input().split()))
    for j in range(A[0]):
        mat[i][A[j+1]-1] = 1
P = list(map(int,input().split()))

def calc(X):
    for i in range(M):
        tmp = 0
        for j in range(N):
            tmp += mat[i][j] * X[j]
        if tmp % 2 != P[i]:
            return 0
    return 1

ans = 0
for i in range(2 ** N):
    X = [(i >> s) % 2 for s in range(N)]
    ans += calc(X)
print(ans)

Solution (Python):
import itertools
n,m = map(int,input().split())
seq = [0,1]
v_list = list((itertools.product(seq,repeat = n)))
ks = []
ans = 0
for i in range(m):
    ks.append(list(map(int,input().split())))
p = list(map(int,input().split()))
s = set()
for i in range(m):
    for j in range(ks[i][0]):
        s.add(ks[i][j+1])

for x in range(2**n):
    counter = 0
    for i in range(m):
        tmp = 0
        for j in range(ks[i][0]):
            tmp += v_list[x][ks[i][j+1] - 1]
        if tmp % 2 == p[i]:
            counter +=1
    if counter == m:
        ans +=1
print(ans)

Solution (Python):
import sys
from itertools import product

N,M = list(map(int, input().split()))

K = []

for i in range(M):
    k = list(map(int, input().split()))
    K.append(k)

P = list(map(int, input().split()))



S = []

for s in product([0,1], repeat=N):
    S.append([0] + list(s))

count = 0

for s in S:
    verify = True
    for p,k in zip(P,K):
        _sum = 0
        for i in k[1:]:
            _sum += s[i]
        parity = _sum % 2
        if parity != p:
            verify = False
            break
    if verify:
        count += 1

print(count)

Solution (Python):
import sys
from itertools import product

N,M = list(map(int, input().split()))

K = []

for i in range(M):
    k = list(map(int, input().split()))
    K.append(k)

P = list(map(int, input().split()))



S = []

for s in product([0,1], repeat=N):
    S.append([0] + list(s))

count = 0

for s in S:
    verify = True
    for p,k in zip(P,K):
        _sum = 0
        for i in k[1:]:
            _sum += s[i]
        parity = _sum % 2
        if parity != p:
            verify = False
            break
    if verify:
        count += 1

print(count)

Solution (Python):
N, M = map(int, input().split())

K_list = [0 for i in range(M)]
A_list = [[] for i in range(M)]

for i in range(M):
    ai = list(map(int, input().split()))
    K_list[i] = ai[0]
    A_list[i] = ai[1:]

P_list = list(map(int, input().split()))

A_sorted = sorted(A_list)






patterns = [[] for i in range(2**N)]
for i in range(2 ** N):
    temp = i
    pattern = [0 for j in range(N)]
    for j in range(N):
        pattern[j] = temp % (2)
        temp = temp//2

    patterns[i] = pattern


count = 0
for i, pattern in enumerate(patterns):  
    for j, targets in enumerate(A_list):  
        tempsum = 0
        for k in targets:
            tempsum += pattern[k-1]
        if P_list[j] != tempsum % 2:
            break
    else:
        
        count += 1

print(count)

Solution (Python):
n,m=map(int,input().split())
res=0
q=[]
for i in range(m):
    q.append(list(map(int,input().split())))
p=list(map(int,input().split()))

for s in range(2**n):
    judge=True
    for i in range(m):
        cnt=0
        for j in range(1,len(q[i])):
            w=q[i][j]
            if s >> (w-1) &1 == 1:
                cnt += 1
        if cnt % 2 != p[i]:
            judge=False
    if judge:
        res += 1
print(res)

Solution (Python):
n, m = map(int, input().split())
k = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
b = []
for _k in k:
    bit = 0
    for i in _k[1:]:
        bit += 2 ** (i-1)
    b.append(bit)

res = 0
for i in range(2**n):
    for j, k in enumerate(b):
        if bin(i & k).count('1') % 2 != p[j]:
            break
    else:
        res += 1
print(res)

Solution (Python):
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())

    link = np.zeros((M, N))

    for i in range(M):
        tmp = list(map(int, input().split()))
        for j in range(1, tmp[0]+1):
            link[i][tmp[j]-1] = 1

    p = np.array(list(map(int, input().split()))).T
    
    
    ans = 0
    for i in range(2**N):
        switch = np.zeros((N, 1))
        for j in range(N):
            if i&1:
                switch[j][0] = 1
            i >>= 1
        now = np.dot(link, switch) % 2
        ok = True
        for i in range(M):
            if now[i] != p[i]:
                ok = False
                break
        if ok:
            ans += 1
    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):
import itertools

N, M = list(map(int, input().split()))
K, S = [], []
for _ in range(M):
    temp = list(map(int, input().split()))
    K.append(temp[0])
    S.append(temp[1:])

P = list(map(int, input().split()))

ans = 0
for x in itertools.product(("on", "off"), repeat=N):
    flag = True
    for s, p in zip(S, P):
        count = 0
        for i in s:
            if x[i-1] == "on":
                count += 1
        if count % 2 != p:
            flag = False
    if flag:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
light_sw = []
for _ in range(m):
  k, *sw = map(int, input().split())
  light_sw.append(sw)
p = list(map(int, input().split()))

cnt = 0
for i in range(2 ** n):
  sw = [1 if ((i >> j) & 1) else 0 for j in range(n)]
  
  flg = True
  for k, light in enumerate(light_sw):
    sum_sw = 0
    for ls in light:
      sum_sw += sw[ls-1]
    if sum_sw % 2 != p[k]:
      flg = False
      break
  
  if flg:
    cnt += 1

print(cnt)

Solution (Python):
n, m = map(int, input().split())
s = [list(map(int, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
for bit in range(1 << n):
    flag = 1
    for i in range(m):
        on_count = 0
        for switch in s[i]:
            if bit & (1 << (switch-1)):
                on_count += 1
        if (on_count % 2) != p[i]:
            flag = 0
            break
    ans += flag
print(ans)

Solution (Python):
n, m = map(int, input().split())
s = []
for _ in range(m):
    tmp = list(map(int, input().split()))
    s.append(tmp[1:])
p = list(map(int, input().split()))

ans = 0
for bit in range(0, 1 << n):
    flag = 1
    for i in range(m):
        on_count = 0
        for switch in s[i]:
            if bit & (1 << (switch-1)):
                on_count += 1
        if (on_count % 2) != p[i]:
            flag = 0
    if flag == 1:
        ans += 1
print(ans)

Solution (Python):
N,M=map(int,input().split())
s=[[0 for i in range(N+1)] for j in range(M)]
p=[0]*M
a=[0]*N
count=0
for i in range(M):
  s[i]=list(map(int,input().split()))
p=list(map(int,input().split()))
for i in range(1 << len(a)):
    a=[0]*N
    for j in range(len(a)):
        if ((i >> j) & 1) == 1:
            a[j]=1
    c=0
    for l in range(M):
      S=0
      for k in range(1,s[l][0]+1):
        S=S+a[s[l][k]-1]
      if S%2==p[l]:
        c=c+1
    if c==M:
      count=count+1
print(count)

Solution (Python):
import sys

def input():
    return sys.stdin.readline()[:-1]

def main():
    n,m = map(int,input().split())
    k = []
    s = []
    ans = 0
    
    for _ in range(m):
        tmp = [int(i) for i in input().split()]
        k.append(tmp.pop(0))
        s.append(tmp)

    p = [int(i) for i in input().split()]

    for i in range(2**n):
        tentou=[0]*m
        b = bin(i)[2:].zfill(n)
        for i2 in range(len(s)):
            for i3 in s[i2]:
                if b[i3-1] == "1":
                    tentou[i2]+=1
        tentou = [z % 2 for z in tentou]
        if tentou == p:
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque, defaultdict
import copy
import bisect

sys.setrecursionlimit(10 ** 9)


N, M = list(map(int, input().split()))
k=[]
s=[]
for i in range(M):
    S = list(map(int, input().split()))
    k.append(S[0])
    s.append(S[1:])
p = list(map(int, input().split()))

def on_off(kumi, s, p):
    for i in range(M):
        atai = 0
        for j in s[i]:
            atai += kumi[j - 1]
        atai = atai % 2
        if atai != p[i]:
            return 0
    return 1

num = 0
kumi = [0 for i in range(N)]
for i in range(2**N):
    kumi = [0 for i in range(N)]
    for j in range(N):
        kumi[j] = (i & (2**j))//(2**j)
    num += on_off(kumi, s, p)

print(num)

Solution (Python):
def Switches():
    from math import log2
    N, M = map(int, input().split())
    
    switchList = []

    
    for i in range(M):
        k = list(map(int, input().split()))
        k = k[1:]
        
        switchList.append([True * (i+1 in k) for i in range(N)])
    p = list(map(int, input().split()))
    
    result = 0

    
    for i in range(2**N):
        tmp = format(i, "0"+str(N)+"b")
        tmp = [int(j) for j in tmp]
        
        tmp = [sum([switchList[k][j] * tmp[j] for j in range(N)]) % 2 for k in range(M)]
        if p == tmp:
            result += 1

    print(result)

if __name__ == "__main__":
    Switches()

Solution (Python):

from itertools import combinations
import copy

def solve2():
    """
    itertools.productを使えばもっとすっきり？
    """
    import itertools as it
    N, M = list(map(int, input().split()))
    K = []
    S = []
    for i in range(M):
        _in = list(map(int, input().split()))
        K.append(_in[0])
        S.append(_in[1:])
    P = list(map(int, input().split()))

    switch_stats = it.product((0,1), repeat=N)

    ans = 0
    for stats in switch_stats:
        is_ok = True
        for i in range(M):  
            on_num = 0
            for s_i in S[i]:
                on_num += 1 if stats[s_i-1]==1 else 0
            if on_num%2 == P[i]:
                continue
            else:
                is_ok = False
        
        if is_ok:
            ans += 1
    
    print(ans)


def solve():
    N, M = list(map(int, input().split()))
    K = []
    S = []
    for i in range(M):
        _in = list(map(int, input().split()))
        K.append(_in[0])
        S.append(_in[1:])
    P = list(map(int, input().split()))

    """
    全探索
    計算量 O(2^N * M * max(len(S)))
    N=10, M=10でも、1024 * 10 * 10 くらい？
    """
    def dfs(switch_stats):
        if len(switch_stats)==N:
            is_ok = True
            for i in range(M):
                on_num = 0
                for switch_i in S[i]:
                    on_num += 1 if switch_stats[switch_i-1] == 1 else 0
                if on_num%2 == P[i]:
                    continue
                else:
                    is_ok = False
                    break
            
            if is_ok:
                return 1
            else:
                return 0
        switch_stats1 = copy.deepcopy(switch_stats)
        switch_stats1.append(0)
        ret1 = dfs(switch_stats1)
        switch_stats2 = copy.deepcopy(switch_stats)
        switch_stats2.append(1)
        ret2 = dfs(switch_stats2)
        return ret1 + ret2

    ans = dfs([])
    print(ans)


if __name__ == "__main__":
    solve2()

Solution (Python):

from itertools import combinations
import copy

def solve():
    N, M = list(map(int, input().split()))
    K = []
    S = []
    for i in range(M):
        _in = list(map(int, input().split()))
        K.append(_in[0])
        S.append(_in[1:])
    P = list(map(int, input().split()))


    def dfs(switch_stats):
        if len(switch_stats)==N:
            is_ok = True
            for i in range(M):
                on_num = 0
                for switch_i in S[i]:
                    on_num += 1 if switch_stats[switch_i-1] == 1 else 0
                if on_num%2 == P[i]:
                    continue
                else:
                    is_ok = False
                    break
            
            if is_ok:
                return 1
            else:
                return 0
        switch_stats1 = copy.deepcopy(switch_stats)
        switch_stats1.append(0)
        ret1 = dfs(switch_stats1)
        switch_stats2 = copy.deepcopy(switch_stats)
        switch_stats2.append(1)
        ret2 = dfs(switch_stats2)
        return ret1 + ret2

    ans = dfs([])
    print(ans)


if __name__ == "__main__":
    solve()

Solution (Python):
n, m = map(int, input().split())

sw_li = [list(map(int, input().split())) for _ in range(m)]
p_li = list(map(int, input().split()))

count = 0
for i in range(2**n):
    tf = True
    on_li = format(i, "b").zfill(n)
    
    for index, j in enumerate(sw_li):
        sum = 0
        for k in j[1:]:
            sum += int(on_li[n - k-1])
        if sum % 2 != p_li[index]:
            tf = False
            break

    if tf :
        count+= 1

print(count)

Solution (Python):
import sys            
input = sys.stdin.readline

def main():                      
    N,M = map(int,input().split())
    S = [[int(s)-1 for s in input().split()[1:]] for _ in range(M)]
    P = [int(p) for p in input().split()]  
    
    ans = 0
    
    for i in range(2**N):
        state = [(i>>j)%2 for j in range(N)]
        ans += sum([sum([state[s] for s in S[j]])%2==P[j] for j in range(M)])==M
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int, input().split())
x = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
v=[0]*n
w=[]
z=0
count=0
ans=0
for i in range(2**n):
    for j in range(n):
        if ((i >> j) & 1):
            v[j]=1
    w.append(v)
    v=[0]*n
for i in range(2**n):
    for j in range(m):
        for k in range(1,len(x[j])):
            z+=(w[i][x[j][k]-1])
        if z%2==p[j]:
            count+=1
        z=0
    if count==m:
        ans+=1
    count=0

print(ans)

Solution (Python):
N, M = map(int, input().split())
s = []
for _ in range(M):
    ss = list(map(int, input().split()))
    s.append(ss[1:])
p = list(map(int, input().split()))

ans = 0
for i in range(2 ** N):
    check = True
    for k in range(M):
        count = 0
        for ss in s[k]:
            if (i >> (ss - 1)) & 1 == 1:
                count += 1
        if count % 2 != p[k]:
            check = False
    if check:
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
l = [list(map(int, input().split()))[1:] for _ in range(M)]
p = list(map(int, input().split()))
ans = 0

on_off = [[0], [1]]

for _ in range(N-1):
    kari = []
    for j in on_off:
        kari.append(j+[0])
        kari.append(j+[1])
    on_off = kari

for a in on_off:
    cnt = 0
    for m in range(M):
        s = 0
        for c in l[m-1]:
            s += a[c-1]
        if s % 2 == p[m-1]%2:
            cnt += 1
    if cnt == M:
        ans += 1

print(ans)

Solution (Python):
n, m = map(int, input().split())

e = [[] for _ in range(n)]


for i in range(m):
    k, *s = map(int, input().split())
    s = map(lambda x: x - 1, s)
    for ss in s:
        e[ss].append(i)

p = tuple(map(int, input().split()))

ans = 0
for bits in range(1 << n):
    cnt_on_sw = [0] * m
    
    for sw in range(n):
        if (bits >> sw) & 1:
            for lamp in e[sw]:
                cnt_on_sw[lamp] += 1
    cnt_on_sw = tuple(map(lambda x: x % 2, cnt_on_sw))
    if cnt_on_sw == p:
        ans += 1
print(ans)

Solution (Python):
N, M = list(map(int, input().split()))
s = [sum([2 ** (i - 1) for i in list(map(int, input().split()))[1:]]) for _ in range(M)]
p = list(map(int, input().split()))

ans, n = 0, 2 ** N
for i in range(n):
    for s_, p_ in zip(s, p):
        if bin(i & s_).count("1") % 2 != p_:
            break
    else:
        ans += 1
        
print(ans)

Solution (Python):
N, M = map(int, input().split())
ks = [list(map(int, input().split())) for i in range(M)]
p = list(map(int, input().split()))

ans = 0
for i in range(1 << N):
    all_on = True
    for j in range(M):
        n_on = 0
        for s in ks[j][1:]:
            if (i >> (s - 1)) & 1:
                n_on += 1
        if n_on % 2 != p[j]:
            all_on = False
    if all_on:
        ans += 1
print(ans)

Solution (Python):
n,m=map(int,input().split())
info=[]
for i in range(m):
    info.append(list(map(int,input().split())))
light=list(map(int,input().split()))
ans=0 

for i in range(2**n): 
    on=[]
    onlight=0
    for j in range(n): 
        if (i>>j)&1:
            on.append(j+1)
    for j in range(m): 
        count=0 
        for k in range(info[j][0]): 
            if info[j][k+1] in on:
                count+=1
        if count%2==light[j]:
            onlight+=1
    if onlight==m:
        ans+=1
        
        
print(ans)

Solution (Python):
N, M = map(int, input().split())
lamps = []
for i in range(0, M):
	inpt = list(map(int, input().split()))
	lamps.append(list(map(lambda v: v-1, inpt[1:])))
onoff = list(map(int, input().split()))
cnt = 0
for i in range(0, 2**N):
	m = i
	drived = []
	for j in range(0, M):
		drived.append(0)
	for j in range(0, N):
		if m % 2 == 1:
			for k in range(0, M):
				if j in lamps[k]:
					drived[k] += 1
		m //= 2
	flag = True
	for j in range(0, M):
		if onoff[j] != drived[j]%2:
			flag = False
			break
	if flag:
		cnt += 1
print(cnt)

Solution (Python):
import numpy as np

N, M = map(int, input().split())
bulb = np.zeros((M, N), dtype=bool)

for i in range(M):
    tmp = list(map(int, input().split()))

    for s in tmp[1:]:
        bulb[i][s - 1] = True

P = list(map(int, input().split()))

ret = 0
for k in range(2 ** N):
    count = np.zeros(M, dtype=int)
    for i in range(N):
        state = k & (1 << i) > 0
        for j in range(M):
            if state and bulb[j][i]:
                count[j] += 1

    f = True
    for c, p in zip(count, P):
        if c % 2 != p:
            f = False
            break

    if f:
        ret += 1

print(ret)

Solution (Python):
nm = input().split(" ");
n = int(nm[0]);
m = int(nm[1]);
k = [0]*m;
s = [[0]*n for i in range(m)];

for i in range(m) :
	st = input().split(" ");
	k[i] = int(st[0]);
	for j in range(k[i]) :
		s[i][j] = int(st[j+1]);
p = input().split(" ");
for i in range(m) :
	p[i] = int(p[i]);

ans = 0;
for i in range(2**n) :
	ok = 1;
	for j in range(m) :
		count_s = 0;
		for l in range(k[j]) :
			if ((i >> (n-s[j][l])) & 1) :
				count_s += 1;
		if count_s % 2 != p[j] :
			ok = 0;
	if bool(ok) :
		ans += 1;

print(ans);

Solution (Python):
import sys
input = sys.stdin.readline

def main():
	n, m = map(int, input().strip().split())
	A = [0] * n
	for i in range(m):
		sw = list(map(int, input().strip().split()))[1:]
		for e in sw:
			e -= 1
			A[e] |= 1 << i

	pl = list(map(int, input().strip().split()))
	p = 0
	for i, e in enumerate(pl):
		p |= e << i
		

	j = 0
	ans = 0
	while j < (1 << n):
		t = 0
		for i in range(n):
			if j >> i & 1:
				t ^= A[i]
		if t == p:
			ans += 1
		j += 1

	print(ans)

if __name__ == '__main__':
	main()