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())
l=[[]for _ in range(m)]
for i in range(m):
    l[i]=list(map(int,input().split()))
p=list(map(int,input().split()))

ans=0

for i in range(1<<n): 
    
    all_bits=[] 
    for j in range(n-1,-1,-1):
        all_bits.append((i>>j)&1) 
    check=True    


    for k in range(m):
        cnt=0
        for idx in range(l[k][0]):
            cnt+=all_bits[l[k][idx+1]-1]
        if cnt%2!=p[k]:
            check=False
            break
    if check==True:
        ans+=1
print(ans)

Solution (Python):
import numpy as np
N, M = map(int, input().split())

S = []
for i in range(M):
    tmp = list(map(lambda s: int(s)-1, input().split()))
    S.append(tmp[1:])

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



def f(fixed_l, res):
    if res == 0:
        ll = np.array(fixed_l)
        ss = 0
        for i in range(len(P)):
            p = P[i]
            if ll[S[i]].sum() % 2 == p:
                ss += 1
        return 1 if ss == M else 0
        

    a = f(fixed_l + [0], res-1)
    b = f(fixed_l + [1], res-1)
    return a + b

print(f([], N))

Solution (Python):
n, m = map(int, input().split())
switches = [list(map(int, input().split())) for i in range(m)]
P = list(map(int, input().split()))
ans = 0
for bit in range(2 ** n):
    for switch, p in zip(switches, P):
        count = 0
        for s in switch[1:]:
            if ((bit >> (s - 1)) & 1):
                count += 1
        if count % 2 == p:
            continue
        break
    else:
        ans += 1
print(ans)

Solution (Python):
import copy

def cnt(i, de):
    if i == n:
        for di, dk in enumerate(de):
            if dk % 2 != ps[di]:
                return 0
        return 1
    re = 0
    re += cnt(i+1, de)
    nde = copy.deepcopy(de)
    for di in swtode[i]:
        nde[di] += 1
    re += cnt(i+1, nde)
    return re

n, m = map(int, input().split())
swtode = [[] for _ in range(n)]
for di in range(m):
    k, *ss = map(int, input().split())
    for s in ss:
        swtode[s - 1] += [di]
ps = list(map(int, input().split()))
de=[0] * m
print(cnt(0,de))

Solution (Python):
N, M = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
ss = [[0 for _ in range(N)] for _ in range(M)]
for i, s in enumerate(ks):
    for j in range(len(s)-1):
        ss[i][s[j+1]-1] = 1
ans = 0
for i in range(2**N):
    tmp = 0
    for j in range(M):
        total = 0
        for k in range(N):
            if (i >> k) & 1 and ss[j][k] == 1:
                total += 1
        if total % 2 == p[j]:
            tmp += 1
    if tmp == M:
        ans += 1
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,M=MAP()
lights=[[False]*N for i in range(M)]
for i in range(M):
    K=LIST()
    for j in range(1, K[0]+1):
        lights[i][K[j]-1]=True
P=LIST()

ans=0
for i in range(1<<N):
    cnts=[0]*M
    for j in range(N):
        for k in range(M):
            if i>>j&1:
                if lights[k][j]:
                    cnts[k]+=1
    for j in range(M):
        if cnts[j]%2!=P[j]:
            break
    else:
        ans+=1
print(ans)

Solution (Python):
N, M = list(map(int, input().split()))
K = []
S = []
for i in range(M):
  inp = list(map(int, input().split()))
  K.append(inp[0])
  S.append(inp[1:])
P = list(map(int, input().split()))
res = []
def helper(res, tmp, N):
  if len(tmp)==N:
    res.append(tmp)
    return
  else:
    helper(res, tmp+[0], N)
    helper(res, tmp+[1], N)
helper(res,[],N)
cnt = 0
for item in res:
  flag = True
  for m in range(M):
    a = 0
    for s in S[m]:
      a += item[s-1]
    if (a % 2 != P[m]):
      flag = False
      break
  if flag:
    cnt += 1
print (cnt)

Solution (Python):
import itertools
n, m = map(int, input().split())
index=0
switchL=[]
while index < m:
    listSw = list(map(int, input().split()))
    switchL.append(listSw)
    index+=1
listP = list(map(int, input().split()))

counter=0
for combi in itertools.product([0, 1], repeat=n):
    listR = list(combi)
    index=0
    while index < len(switchL):
        sumA=0
        index2=1
        while index2 < len(switchL[index]):
            target = switchL[index][index2]-1
            sumA+=listR[target]
            index2+=1
        if sumA%2 == listP[index]:
            index+=1
        else:
            break
    if index == len(switchL):
        counter+=1
print(counter)

Solution (Python):
n, m = map(int, input().split())
switch = [set() for _ in range(m)]
for i in range(m):
    a = list(map(int, input().split()))
    for j in range(1, len(a)):
        switch[i].add(a[j])
p = list(map(int, input().split()))
def check(i):
    bright = set()
    for j in range(n):
        if i % 2:
            bright.add(j + 1)
        i //= 2
    for j in range(m):
        if len(switch[j] & bright) % 2 != p[j]:
            return False
    return True
ans = 0
for i in range(1 << n):
    ans += int(check(i))
print(ans)

Solution (Python):
import itertools
n,m=map(int,input().split())
l=[]
for i in range(m):
    a,*b=list(map(int,input().split()))
    l.append(b)
p=list(map(int,input().split()))
cnt=0
for x in itertools.product([0,1], repeat=n):
    onl=[0]*m
    for i in range(n):
        for j in range(m):
            if x[i]==1 and i+1 in l[j]:onl[j]+=1
    for i in range(m):
        if p[i]!=onl[i]%2:
            break
    else:cnt+=1
print(cnt)

Solution (Python):
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True 
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
s = [0] * m
for i in range(m):
    z = inl()
    s[i] = z[1:]
p = inl()

sum = 0
for i in range(2**n):
    b = []
    for j in range(n):
        b.append((i>>j)%2)  
    ok = True
    for j in range(m): 
        x = 0
        for k in s[j]:  
            x += b[k-1]
        if x%2 != p[j]:
            ok = False
            break
    if ok:
        sum += 1

print(sum)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict
import itertools
import numpy as np

n, m = LI()
ks = []
ss = []
for i in range(m):
    k, *s = LI()
    ks.append(k)
    ss.append(s)
ps = LI()

ans = 0
for comb in itertools.product((0,1), repeat=n):
    for j in range(m):
        o_e = 0 
        for i in ss[j]:
            o_e += comb[i-1]
        if o_e % 2 == ps[j]:
            continue
        else:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
N, M = map(int,input().split())
S = []
K = []
for i in range(M):
    tmp = list(map(int,input().split()))
    k= tmp[0]
    S.append([tmp[i] for i in range(1, k+1)])
P = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    s = [0]*N 
    for j in range(N):
        if (i >> j) % 2 == 1:
            s[j] = 1
    LIGHT = [False]*M
    for k in range(M): 
        count = 0
        for c in S[k]:
            c -= 1
            if s[c] == 1:
                count += 1
        if count % 2 == P[k]:
            LIGHT[k] = True
    if all(LIGHT):
        ans += 1
print(ans)

Solution (Python):
import itertools
n, m = [int(i) for i in input().split()]
sss = [[int(i) for i in input().split()][1:] for _ in range(m)]
ps = [int(i) for i in input().split()]

ans = 0
for pro in itertools.product((0, 1), repeat=n):
    for ss, p in zip(sss, ps):
        pp = sum(pro[s-1] for s in ss) % 2
        if pp != p:
            break
    else:
        ans += 1
        

print(ans)

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

s = {}

for i in range(1, m+1):
    k, *v = map(int, input().split())
    s[i] = list(v)
p = [0] + list(map(int, input().split()))
ans = 0
for i in range(2**n):
    a = p[:]
    for j in range(n):
        if i & (1 << j) > 0:
            for k in range(1, m+1):
                if j+1 in s[k]:
                    a[k] ^= 1

    if sum(a) == 0:
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
S = [[] for _ in range(N)]
for i in range(M):
    ss = list(map(int, input().split()))[1:]
    for s in ss:
        S[s - 1].append(i)
P = [int(x) for x in input().split()]
ans = 0
for bit in range(1 << N):
    den = [0] * M
    for i in range(N):
        if bit >> i & 1:
            for s in S[i]:
                den[s] += 1
    if all(d % 2 == p for d, p in zip(den, P)):
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
switches = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
ans = 0
onofflist = [format(i,'0'+str(N)+'b') for i in range(2**N)]
for onoff in onofflist:
    flag=True
    for i,swittch in enumerate(switches):
        cur = 0
        for s in swittch[1:]:
            cur += int(onoff[s-1])
        if cur % 2 != p[i]:
            flag=False
    if flag:
        ans+=1
print(ans)

Solution (Python):


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

switches = []
for _ in range(M):
    switches.append(list(map(int, input().split()))[1:])

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

def on(s, bit):
    return (bit >> (s-1)) & 1

count = 0
for bit in range(2 ** N):
    flag = False
    for k in range(M):
        state = 0
        for s in switches[k]:
            state += on(s, bit)
        if state % 2 != p[k]:
            flag = True
            break
    if flag:
        continue
    count += 1
print(count)

Solution (Python):
import sys

fin = sys.stdin.readline

N, M = map(int, fin().split())

ks = [tuple(map(int, fin().split())) for i in range(M)]
p = tuple(map(int, fin().split()))

count = 0

for i in range(2 ** N):
    switch = format(i, "b").zfill(N)
    ok = 1
    for ks_, p_ in zip(ks, p):
        p__ = p_
        for s in ks_[1:]:
            p__ += int(switch[s - 1])
        if p__ % 2 == 1:
            ok = 0
            break
    if ok:
        count += 1

print(count)

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

s = []
for i in ks:
    t = 0
    for j in range(1, i[0]+1):
        t += 2**(i[j]-1)
    s.append(t)

pt = 0
for i in range(2**n):
    l = True
    for j in range(m):
        o = bin(i & s[j]).count("1") % 2
        if o != p[j]:
            l = False
            break
    if l: pt += 1

print(pt)

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

S = [[0] * N for _ in range(M)]

for i in range(M):
    a = [int(i) for i in input().split()]
    for j in a[1:]:
        S[i][j-1] = 1

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

ans = 0

for i in range(2**N):
    K = [0] * M
    for j in range(N):
        if i >> j & 1:
            for k in range(M):
                if S[k][j] == 1:
                    K[k] += 1
    c = 0
    for j in range(M):
        if K[j]%2 == P[j]:
            c += 1
    if c == M:
        ans += 1

print(ans)

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

s = []
for i in range(M):
    s_list = list(map(int, input().split()[1:]))
    s.append(s_list)

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

ans = 0




for i in range(2**N):
    
    
    found = True
    for m in range(M):
        
        
        count = 0
        for k in range(N):
            
            if k+1 not in s[m]:
                continue

            state = (i >> k) & 1
            
            if state == 1:
                count += 1
                

        if p[m] != (count % 2):
            found = False
            break

    if found:
        ans += 1

print(ans)

Solution (Python):
n,m=map(int,input().split())
ks_list=[]
for i in range(m):
    sub_list=list(map(int,input().split()))
    sub_list=sub_list[1:]
    ks_list.append(sub_list)
p_list=list(map(int,input().split()))
ans=0
for i in range(2**n):
    s_list=[]
    for j in range(n):
        s_list.append(i&1)
        i=i>>1
    count=1
    for j in range(m):
        Sum=0
        for x in ks_list[j]:
            Sum=Sum+s_list[x-1]
        if Sum%2==p_list[j]:
            count=count
        else:
            count=0
    ans=ans+count
print(ans)

Solution (Python):
import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()


n,m = na()
a = []

for i in range(m):
    b = na()
    a.append(b)
    
p = na()

ans = 0

for i in range(1 << n):
    d = True
    for j in range(len(a)):
        c = 0
        for k in range(1,a[j][0]+1):
            if i >> (a[j][k]-1) & 1:
                c += 1
        if c%2 != p[j]:
            d = False
    if d:
        ans += 1

print(ans)

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

for i in range(M):
    L.append(list(map(int,input().split())))
P=list(map(int,input().split()))
ans=0

def check(D):
    ret=True
    for i in range(M):
        l=L[i][1:]
        tmp=0
        for l_ in l:
            tmp+=(D>>(l_-1))&1
        if tmp%2!=P[i]:
            ret=False
            break

    return ret


for d in range(2**N):
    if check(d):
        ans+=1


print(ans)

Solution (Python):
n, m=map(int, input().split())
s=[]
for i in range(m):
    inp=input().split()
    k=int(inp[0])
    tmp=[]
    for i in range(k):
        tmp.append(int(inp[i+1]))
    s.append(tmp)
p=list(map(int, input().split()))
result=0
for i in range(2**n):
    switch=[]
    flag=1
    for j in range(n):
        if (i>>j)&1:
            switch.append(1)
        else:
            switch.append(0)
    for j in range(m):
        sum=0
        for k in range(len(s[j])):
            sum=sum+switch[s[j][k]-1]
        if sum%2!=p[j]:
            flag=0
    if flag:
        result=result+1
print(result)

Solution (Python):
import sys
from itertools import product

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    bulbs = []
    for _ in range(M):
        b = tuple(map(int, input().split()))
        bulbs.append(b[1:])

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

    ans = 0
    for switch in product((0, 1), repeat=N):
        check = [0] * M
        for i, bulb in enumerate(bulbs):
            cnt = 0
            for b in bulb:
                cnt += switch[b-1]

            if cnt % 2 == P[i]:
                check[i] = True
            else:
                check[i] = False

        if all(check):
            ans += 1

    return ans



if __name__ == '__main__':
    print(main())

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

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

res = 0
for i in range(2 ** n):
    flag = True
    bit_i = bin(i)[2:].zfill(n)
    for j in range(m):
        sum_s = 0
        for idx in s[j]:
            sum_s += int(bit_i[idx-1])
        if sum_s % 2 != p[j]:
            flag = False
            break
    if flag:
        res += 1

print(res)

Solution (Python):


MOD = 2  
import itertools



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

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

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

    swl = list(itertools.product([1,0],repeat=N))
    
    ok_cnt = 0
    for sw in swl:
        bOK = True
        for i,s in enumerate(S):
            on_cnt = 0
            for ss in s:
                if sw[ss-1]:
                    on_cnt += 1

            if (on_cnt % 2) != P[i]:
                bOK = False
                break
        if bOK:
            ok_cnt+=1

    print(ok_cnt)


    pass

if __name__ == '__main__':
    main()

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

for k in range(M):
    b = list(map(int,input().split()))
    B.append(b[1:])
p = list(map(int,input().split()))

ans = 0
for k in range(2**N):
    a = []
    t = [0 for k in range(M)]
    for l in range(N):
        if (k>>l)&1:
            a.append(l)
    for s in a:
        for l in range(M):
            if s+1 in B[l]:
                t[l] += 1
    u = 0
    for l in range(M):
        if p[l] == t[l]%2:
            u += 1
    if u==M:
        ans+=1
print(ans)

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

ans = 0
for switchs in range(1<<n):
	switch_on = []
	for j in range(n):
		if (switchs>>j)&1 == 1:
			switch_on.append(j+1)
	for denkyu in range(m):
		tmp = 0
		for s_denkyu in s[denkyu]:
			if s_denkyu in switch_on:
				tmp += 1
		if tmp%2 != p[denkyu]: 
			break
	else:
		ans += 1

print(ans)

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

N, M  = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
P = [int(v) for v in input().split()]

ans = 0
for i in range(1 << N):
    s = []
    
    for j in range(N):
        if (i >> j) & 1:
            s.append(j)

    cc = 0
    for j in range(M):
        v = L[j][1:]
        
        c = 0
        for k in v:
            if k - 1 in s:
                c += 1
                
        if c % 2 == P[j]:
            cc += 1
            
    if cc == M:
        ans += 1
        
print(ans)

Solution (Python):
N,M=map(int,input().split())
ks=[list(map(int,input().split())) for _ in range(M)]
p=list(map(int,input().split()))
bit=[]
ans=0
for i in range(2**N):
    bit+=[list(bin(i)[2:].zfill(N))]
for b in bit:
    for i in range(M):
        on=0
        for j in range(ks[i][0]):
            if b[ks[i][j+1]-1]=="1":
                on+=1
        if on%2!=p[i]:
            break
    else:
        ans+=1
print(ans)

Solution (Python):
n,m = (int(i) for i in input().split())
ks = e = [[int(i) for i in input().split()] for i in range(m)]
p = [int(i) for i in input().split()]

on = []
for x in ks:
    o = 0
    for s in x[1:]:
        o += 2**(s-1)
    on.append(o)

res = 0
for x in range(2**n):
    flg = True
    for i,o in enumerate(on):
        if p[i] != bin(o&x).count("1") % 2:
            flg = False
            break

    if flg:
        res += 1
       
print(res)

Solution (Python):
def getlist():
	return list(map(int, input().split()))

N, M = getlist()

light = [[0 for i in range(N)] for j in range(M)]
for i in range(M):
	A = getlist()
	k = A[0]
	for j in range(k):
		light[i][A[1 + j] - 1] = 1

p = getlist()

ans = 0
for i in range(1 << N):
    output = []
    for j in range(N):
        if ((i >> j) & 1) == 1:
            output.append(0)
        else:
        	output.append(1)

    judge = "YES"
    for j in range(M):
    	c = 0
    	for k in range(N):
    		if output[k] == 1 and light[j][k] == 1:
    			c += 1
    	if c % 2 != p[j]:
    		judge = "NO"
    		break

    if judge == "YES":
    	ans += 1


print(ans)

Solution (Python):
from numpy import*
n,m=map(int,input().split())
l=[]
for i in range(m):
    *a,=map(int,input().split())
    l.append(a[1:])
*p,=map(int,input().split())

ans=0
for t in range(2**n):
    tmp=array([t>>s&1 for s in range(n)])
    if p==[sum(tmp[array(i)-1])%2for i in l]:
        ans+=1
print(ans)

Solution (Python):
count = 0
n,m = map(int, input().split())
sw = {}
lt = {}
for i in range(1, m+1):
    s = map(int, input().split())
    s = list(s)
    k = s[0]
    s = s[1:]
    lt[i] = s
    for j in range(k):
        t = sw.get(s[j], [])
        t.append(i)
        sw[s[j]] = t
p = map(int, input().split())
p = list(p)

for i in range(pow(2, n)):
    sw_sta = [False] * (n + 1)
    for j in range(n):
        if (i & pow(2,j)) != 0:
            sw_sta[j + 1] = True
    allon = True
    for j in range(m):
        c = 0
        for k in lt[j + 1]:
            if sw_sta[k]:
                c += 1
        if c % 2 != p[j]:
            allon = False
            break
    if allon:
        count += 1
print(count)

Solution (Python):
n,m = (int(num) for num in input().split())

ls = []

for i in range(m):
    s = [int(num)-1 for num in input().split()]
    s.pop(0)
    ls.append(s)
    

    
p = [int(num) for num in input().split()]
    
def isOK(k,s,p):
    r = 0
    for i in range (n):
        if (k >> i)%2 == 1 and i in s:
            r += 1
    
    if r%2 == p:
        return True
    else:
        return False
    
ans = 0
    
for k in range(2**n):
    for i in range(m):
        f = True
        s = ls[i]
        if not isOK(k,s,p[i]):
            f = False
            break
    if f:
        ans += 1
        

print(ans)

Solution (Python):
N,M=map(int, input().split())
sw=[[0]*N for m in range(M)]
for m in range(M):
    ks=list(map(int, input().split()))
    for i in ks[1:]:
        sw[m][i-1]=1
p=list(map(int, input().split()))
from itertools import product
ans=0
for x in product((0,1),repeat=N):
    a=1
    for m in range(M):
        s=0
        for i in range(N):
            s+=sw[m][i]*x[i]
        if s%2!=p[m]:
            a=0
            break
    ans+=a
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
def switch(count,onoff):
    global ans
    if count == n:
  
        l = 0
        for i,P in zip(ks,p):
            c = 0
            for j in i[1:]:
                c += onoff[j-1]
     
            if c%2 == P:
                l += 1
   
        if l == m:
            ans += 1
    else:
        count += 1
        switch(count,onoff+[1])
        switch(count,onoff+[0])

switch(0,[])
print(ans)

Solution (Python):
import itertools
n,m=map(int,input().split())
KS=[]
for i in range(m):
  ks=[int(i) for i in input().split()]
  KS.append(ks)
P=[int(i) for i in input().split()]
ans=0
for Key in itertools.product(range(2),repeat=n):
  Key=list(Key)
  chk=True
  for i in range(m):
    on=0
    for j in range(KS[i][0]):
      on+=Key[KS[i][j+1]-1]
    if on%2!=P[i]:
      chk=False
  if chk==True:
    ans+=1
print(ans)

Solution (Python):
N,M=map(int,input().split())
S=[]
for i in range(M):
    s=list(map(int,input().split()))
    S.append(s[1:])
P=list(map(int,input().split()))
ans=0
for i in range(2**N):
    i=bin(i)[2:].zfill(N)
    p=[0]*M
    for k in range(N):
        for j in range(M):
            if i[k]=="1" and (k+1 in S[j]):
                p[j]+=1
                p[j]%=2
    if p==P:
        ans+=1
print(ans)

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

def check(n):
	i = 0
	for k, *s in KS:
		c = 0
		for q in s:
			if n & (1 << (q - 1)):
				c += 1
		if P[i] != c % 2:
			return False
		i += 1
	return True




count = 0
for n in range(2 ** N):
	if check(n):
		count += 1
print(count)

Solution (Python):
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

def main():
    N, M = LI()
    s_li = []
    for i in range(M):
        s_li.append(LI()[1:])
    p_li = LI()

    import itertools
    counter = 0
    for i in itertools.product([0,1], repeat=N):  
        for s, p in zip(s_li, p_li): 
            if sum([i[num-1] for num in s])%2 != p:
                break
        else:
            counter += 1
    print(counter)

main()

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

ans = 0
def isAllOn(switches):
    for i in range(M):
        s = s_list[i]
        p = p_list[i]
        cnt = 0
        for idx in s:
            cnt += switches[idx-1]
        if cnt % 2 != p:
            return False
    return True


def bfs(stack):
    global ans
    global N
    if len(stack) == N:
        if isAllOn(stack):
            ans += 1
        return

    for i in [0, 1]:
        _stack = stack[::]
        _stack.append(i)
        bfs(_stack)

bfs([])
print(ans)

Solution (Python):
from itertools import chain,combinations
import numpy as np



def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


def main():
    n, m = [int(val) for val in input().split()]
    vectors_for_each_switch = [[] for _ in range(n)]
    for light_id in range(m):
        k_and_ss = [int(val) for val in input().split()]
        k = k_and_ss[0]
        if k == 0:
            switches = []
        else:
            switches = k_and_ss[1:]
        switches = [switch - 1 for switch in switches]
        switches = set(switches)
        for switch_id in range(n):
            is_in = switch_id in switches
            vectors_for_each_switch[switch_id].append(is_in)

    vectors_for_each_switch = [np.asarray(vec, dtype=int) for vec in vectors_for_each_switch]
    target_vector = np.asarray([int(val) for val in input().split()], dtype=int)

    count = 0
    for switch_set in powerset(range(n)):
        target = target_vector
        for on_switch in switch_set:
            target = target + vectors_for_each_switch[on_switch]
        if all(target % 2 == 0):
            count += 1
    print(count)


if __name__ == '__main__':
    main()

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

def check_on(s_all, s, p):
    oncnt = 0
    for i in s:
        if s_all[i]:
            oncnt += 1
    if oncnt % 2 == p:
        return True
    else:
        return False

def check_all_on(s_all, kss, ps):
    for i in range(M):
        s = kss[i][1]
        p = ps[i]
        if not check_on(s_all, s, p):
            return False
    return True


def rec(s_all, kss, ps, cnt):
    if len(s_all) == N+1:
        if check_all_on(s_all, kss, ps):
            cnt[0] += 1
            return
    else:
        s_all.append(0)
        rec(s_all, kss, ps, cnt)
        s_all.pop()

        s_all.append(1)
        rec(s_all, kss, ps, cnt)
        s_all.pop()

s_all = [0]
cnt = [0]
rec(s_all, kss, ps, cnt)
print(cnt[0])

Solution (Python):
import numpy as np
n, m = map(int, input().split())

ks = [np.array(list(map(int, input().split()))[1:]) - 1 for i in range(m)]
p = list(map(int, input().split()))

def get_state(s):
    return np.array([s[k].sum() for k in ks]) % 2 == p

def get_bin(integer, length):
    return (np.array([integer & (2 ** i) for i in range(length)]) > 0).astype(int)

print(sum(get_state(get_bin(i, n)).all() for i in range(2**n)))

Solution (Python):
N, M = [int(i) for i in input().split()]

connections = []
for _ in range(M):
    k, *S = [int(i) for i in input().split()]
    connections.append([i-1 for i in S])
P = [int(i) for i in input().split()]


def get_bin(x, n=0):
    return format(x, 'b').zfill(n)


switches = [False] * N

count = 0
for i in range(2 ** N):
    binstr = get_bin(i, N)
    switches = [s == '1' for s in binstr]
    for j in range(M):
        conn = connections[j]
        p = P[j]

        f = 0
        for c in conn:
            if switches[c]:
                f += 1
        if f % 2 != p:
            break
    else:
        count += 1
print(count)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from itertools import product

def main():
    N, M = LI()
    kss = []
    for _ in range(M):
        kss.append(LI_()[1:])
    pp = LI()
    ans = 0
    for sw in product(range(2), repeat=N):
        ok = True
        for ks, p in zip(kss, pp):
            check = 0
            for k in ks:
                if sw[k]:
                    check += 1
            if check % 2 != p:
                ok = False
                break
        if ok:
            ans += 1
    return ans

print(main())

Solution (Python):
import numpy as np
N,M=map(int,input().split())
connect=np.zeros((M,N))
for i in range(M):
	c = list(map(int,input().split()))[1:]
	for sw in c:
		connect[i][sw-1]=1
req=np.array(list(map(int,input().split())))
ptns=[]
for i in range(2**N):
	ptns.append(list(format(i, '0{}b'.format(N))))
ptns=np.array(ptns).astype(np.uint8)
ans=0
for i in range(2**N):
	co = np.mod(np.sum(ptns[i] * connect, axis=1),2)
	co = co.reshape((1,-1))
	if np.sum(co!=req)==0:
		ans+=1
print(ans)