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):
from itertools import product
N, M = map(int, input().split())
k = []
s = []
for i in range(M):
    ks = list(map(int, input().split()))
    k.append(ks[0])
    s.append(ks[1:])
p = list(map(int, input().split()))

ans = 0
for t in product([0, 1], repeat=N):
    sw = {i+1: t[i] for i in range(N)}
    flg = 1
    
    for ind in range(M):
        num = 0
        
        for j in s[ind]:
            if sw[j] == 1:
                num += sw[j]
        
        if num % 2 != p[ind]:
            flg = 0
            break
    if flg:
        ans += 1
print(ans)

Solution (Python):
if __name__ == '__main__':
    N, M = map(int, input().split())
    
    KS_list = [list(map(int, input().split())) for i in range(M)]
    P_list = list(map(int, input().split()))

    answer = 0
    for i in range(2**N):
        pattern = str(bin(i)).replace('0b','').zfill(N)
        is_all_light_on = True
        for j in range(M):
            KS_j = KS_list[j]
                
            K_j = KS_j[0]
            S_j = KS_j[1::]

            on_switch_cnt = 0
            for s in S_j:
                if pattern[s-1] == '1':
                    on_switch_cnt += 1

            if on_switch_cnt%2 != P_list[j]:
                is_all_light_on = False

        if is_all_light_on == True:
            answer += 1
    print(answer)

Solution (Python):
import itertools as it
N,M = map(int,input().split())
slk = []
for _ in range(M):
    slk.append(list(map(int,input().split())))
p = list(map(int,input().split()))




s = [i+1 for i in range(N)]
cb = 0
for i in range(N+1):
    cmbi = list(it.combinations(s, i))
    
    for ccmb in cmbi:
        for j,slki in enumerate(slk):
            g = 0
            
            for k in range(slki[0]):
                if slki[k+1] in ccmb:
                    g += 1
            
            if g%2 == p[j]:
                pass
            else:
                
                break
        else:
            cb += 1
            
print(cb)

Solution (Python):
import itertools

def is_lit(i, bit):
    l = [bit[j-1] for j in sockets[i]]
    return p[i] == l.count(True) % 2

count = 0
N, M = map(int, input().split())
bit_list = list(itertools.product([True, False], repeat = N))

sockets = []
for i in range(M):
    args = input().split(' ')
    k = int(args[0])
    sockets.append([int(args[i+1]) for i in range(k)])

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

for bit in bit_list:
    o = [is_lit(i, bit) for i in range(M)]
    if o.count(True) == len(o):
        count += 1

print(count)

Solution (Python):
from copy import deepcopy
N,M = map(int,input().split())
s_list = []
for _ in range(M):
    s_list.append(tuple(map(int,input().split()[1:])))
plist = tuple(map(int,input().split()))

counter = 0
TF = [0]*N
TFlist = []
def make_bbb(long,number):
    b_n = bin(number)[2:]
    bbb = "0"*(long-len(b_n))+b_n
    return bbb
for _ in range(2**N):
    number = list(map(int,list(make_bbb(N,_))))
    TFlist.append(number)


for TF in TFlist:
    flg = False
    ok = 0
    for num,s in enumerate(s_list):
        sum_on = 0
        
        for ele in s:
            sum_on += TF[ele-1]
        if sum_on%2 != plist[num]:
            flg = False
            break
        else:
            ok += 1
    if ok == M:
        counter += 1


print(counter)

Solution (Python):
n,m = map(int,input().split())
A = []
for i in range(m):
        A.append(input().split()[1:])
P = [int(i) for i in input().split()]
ans = 0
for i in range(2**n):
        count = [0] * m
        a = len(bin(i))-2
        for j in bin(i)[2:]:
                if int(j) == 1:
                        for k in range(m):
                                if str(a) in A[k]:
                                        count[k]+=1
                a-=1
        count = [i%2 for i in count]
        if count == P:
                ans += 1
print(ans)

Solution (Python):
n,m = map(int,input().split())
li = [list(map(int,list(input().split()))) for i in range(m)]
lip = list(map(int,input().split()))

cnt = 0
for i in range(2**n):
  s = format(i,"b").zfill(n)
  s = [int(x) for x in list(str(s))]
  for j in range(m):
    tmp = 0
    for k in range(li[j][0]):
      tmp += s[li[j][k+1]-1]
    if tmp % 2 != lip[j]:
      break
  else:
    cnt += 1
    continue
print(cnt)

Solution (Python):
from itertools import product

n, m = map(lambda x: int(x), input().split(' '))
k = []

for i in range(m):
    k.append(list(input().split(' ')[1:]))

p = list(map(lambda x: int(x), input().split(' ')))


on = list(product([False, True], repeat=n))
count = 0

for _on in on:
    for i, _k in enumerate(k):
        if not (([_on[int(__k) - 1] for __k in _k]).count(True) % 2) == p[i]:
            break
    else:
        count += 1

print(count)

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

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

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



foo = [0] * N
hoge = []
def rec(n):
    if (n < 0):
        hoge.append(foo.copy())
        return
    foo[n] = 1
    rec(n-1)
    foo[n] = 0
    rec(n-1)

rec(N-1)

res = 0
for i in hoge:
    flag = True
    for j in range(M):
        tmp = 0
        for k in range(S[j][0]):
            if (i[S[j][k+1]-1]):
                tmp += 1

        if tmp % 2 != P[j]:
            flag = False
            break
    if flag:
        res += 1
    

print(res)

Solution (Python):
n,m=map(int,input().split())
l=[]
for _ in range(m):
    kari=list(map(int,input().split()))
    l.append(kari)
p=list(map(int,input().split()))
num2=[]
def deal1():
    ans=0
    for a in range(2):
        w=[a]
        all=0
        for k in range(m):
            cnt==0
            for q in range(l[k][0]):
                if w[l[k][q+1]-1]==1:
                    cnt+=1
            if p[k]==cnt%2:
                all+=1
        if all==m:
            ans+=1
    return ans
def deal2():
    ans=0
    for a in range(2):
        for b in range(2):
            w=[a,b]
            all=0
            for k in range(m):
                cnt=0
                for q in range(l[k][0]):
                    if w[l[k][q+1]-1]==1:
                        cnt+=1
                if p[k]==cnt%2:
                    all+=1
            if all==m:
                ans+=1
    return ans
def deal3():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                w=[a,b,c]
                all=0
                for k in range(m):
                    cnt=0
                    for q in range(l[k][0]):
                        if w[l[k][q+1]-1]==1:
                            cnt+=1
                    if p[k]==cnt%2:
                        all+=1
                if all==m:
                    ans+=1
    return ans
def deal4():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    w=[a,b,c,d]
                    all=0
                    for k in range(m):
                        cnt=0
                        for q in range(l[k][0]):
                            if w[l[k][q+1]-1]==1:
                                cnt+=1
                        if p[k]==cnt%2:
                            all+=1
                    if all==m:
                        ans+=1
    return ans
def deal5():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        w=[a,b,c,d,e]
                        all=0
                        for k in range(m):
                            cnt=0
                            for q in range(l[k][0]):
                                if w[l[k][q+1]-1]==1:
                                    cnt+=1
                            if p[k]==cnt%2:
                                all+=1
                        if all==m:
                            ans+=1
    return ans
def deal6():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            w=[a,b,c,d,e,f]
                            all=0
                            for k in range(m):
                                cnt=0
                                for q in range(l[k][0]):
                                    if w[l[k][q+1]-1]==1:
                                        cnt+=1
                                if p[k]==cnt%2:
                                    all+=1
                            if all==m:
                                ans+=1
    return ans
def deal7():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            for g in range(2):
                                w=[a,b,c,d,e,f,g]
                                all=0
                                for k in range(m):
                                    cnt=0
                                    for q in range(l[k][0]):
                                        if w[l[k][q+1]-1]==1:
                                            cnt+=1
                                    if p[k]==cnt%2:
                                        all+=1
                                if all==m:
                                    ans+=1
    return ans
def deal8():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            for g in range(2):
                                for h in range(2):
                                    w=[a,b,c,d,e,f,g,h]
                                    all=0
                                    for k in range(m):
                                        cnt=0
                                        for q in range(l[k][0]):
                                            if w[l[k][q+1]-1]==1:
                                                cnt+=1
                                        if p[k]==cnt%2:
                                            all+=1
                                    if all==m:
                                        ans+=1
    return ans
def deal9():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            for g in range(2):
                                for h in range(2):
                                    for i in range(2):
                                        w=[a,b,c,d,e,f,g,h,i]
                                        all=0
                                        for k in range(m):
                                            cnt=0
                                            for q in range(l[k][0]):
                                                if w[l[k][q+1]-1]==1:
                                                    cnt+=1
                                            if p[k]==cnt%2:
                                                all+=1
                                        if all==m:
                                            ans+=1
    return ans

def deal10():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            for g in range(2):
                                for h in range(2):
                                    for i in range(2):
                                        for j in range(2):
                                            w=[a,b,c,d,e,f,g,h,i,j]
                                            all=0
                                            for k in range(m):
                                                cnt=0
                                                for q in range(l[k][0]):
                                                    if w[l[k][q+1]-1]==1:
                                                        cnt+=1
                                                if p[k]==cnt%2:
                                                    all+=1
                                            if all==m:
                                                ans+=1
    return ans
if n==1:
    print(deal1())
if n==2:
    print(deal2())
if n==3:
    print(deal3())
if n==4:
    print(deal4())
if n==5:
    print(deal5())
if n==6:
    print(deal6())
if n==7:
    print(deal7())
if n==8:
    print(deal8())
if n==9:
    print(deal9())
if n==10:
    print(deal10())

Solution (Python):
from itertools import product

N, M = map(int, input().split())
B = [list(map(int, input().split())) for i in range(M)]
P = input().split()

ans = 0

for switch in product([True, False], repeat=N):
    for b, p in zip(B, P):
        if sum([switch[b[i]-1] for i in range(1, len(b))]) % 2 == int(p):
            pass
        else:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
from itertools import product

def is_light(sw_conn, sw_status, p):
    num_on = 0
    for sw in sw_conn:
        if sw_status[sw] == 1:
            num_on += 1
    return num_on % 2 == p

N, M = [int(x) for x in input().split()]

sw_conn = []
for i in range(M):
    sw_conn.append([int(x)-1 for x in input().split()][1:])

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

ans = 0
for sw_status in product(range(2), repeat=N):
    lights = []
    for j in range(M):
        lights.append(is_light(sw_conn[j], sw_status, p[j]))
    if all(lights):
        ans += 1

print(ans)

Solution (Python):
n,m=map(int,input().split())
sw=[]
for i in range(2**n):
    l=list(str(bin(i)))
    t=n-len(l[2:])
    if t!=0:
        L=['0'*t]+l[2:]
    else:
        L=l[2:]
    sw.append(''.join(L))

S=[]
K=[]
for i in range(m):
    a=[int(i) for i in input().split()]
    K.append(a[0])
    s=a[1:]
    S.append(s)
p=[int(i) for i in input().split()]

for j in range(m):
    SW=[]
    for h in sw:
        s=0
        for i in range(K[j]):
            if h[S[j][i]-1]=='1':
                s+=1
        if s%2==p[j]:
            SW.append(''.join(h))
    sw=set(sw)&set(SW)

    
print(len(sw))

Solution (Python):
n,m = map(int,input().split())
l =[]
pl = []
for i in range(m):
  l.append(list(int(i) for i in input().split()))
pl= list((int(i) for i in input().split()))
cnt = 0
sw = [0]*n
for i in range(2**n):
  sw = list(format(i,"b"))
  while len(sw) < n:
    sw.insert(0,"0")
  flag = 1
  for j in range(m):
    tmp = 0
    for k in range(l[j][0]):
      if sw[-l[j][k+1]] == "1":
        tmp += 1
    if tmp % 2 != pl[j]:
      flag = 0
  if flag == 1:
    cnt += 1
print(cnt)

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

def bit(n,N):
    return ('0'*10+bin(n)[2:])[-N:]

def switch_to_light(switch_state):
    light_state=[]
    for m in range(M):
        if sum([switch_state[s] for s in S[m]])%2==P[m]:
            light_state.append(1)
        else:
            light_state.append(0)
    return light_state

count=0
for state in range(2**N):
    switch_state=[int(b) for b in bit(state,N)]
    light_state=switch_to_light(switch_state)
    if sum(light_state)==M:
        count+=1
print(count)

Solution (Python):
def gen_switch(i, n):
    ret = []
    str_bin = format(i, '011b')
    for k in range(n):
        ret.append(int(str_bin[-k-1]))
    ret.reverse()
    return ret


input_line = input()
splitted_line = input_line.split(" ")
n = int(splitted_line[0])
m = int(splitted_line[1])


my_mtx = []

for i in range(m):
    my_list = [0] * n
    splitted_line = input().split(" ")

    for j in range(len(splitted_line)):
        if j != 0:
            my_list[int(splitted_line[j])-1] = 1

    my_mtx.append(my_list)

splitted_line = input().split(" ")
my_list = []

for item in splitted_line:
    my_list.append(int(item))


count = 0



for i in range(2 ** n):
    my_switch = gen_switch(i, n)
    for j in range(m):
        my_sum = 0
        for k in range(len(my_switch)):
            my_sum = my_sum + (my_switch[k] * my_mtx[j][k])
        if my_sum % 2 != my_list[j]:
            break
        if j == m - 1:
            count = count + 1

print(count)

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

for i in range(M):
    inp = [int(j) for j in input().split()]
    k = inp[0]
    s = inp[1:]
    b = [0] * N
    for j in range(N):
        b[j] = "1" if j+1 in s else "0"
    masks[i] = int("".join(reversed(b)), 2)
    

ps = [int(p) for p in input().split()]
s = 0

for t in range(2**N):
    for i in range(M):
        v = masks[i] & t
        
        
        if format(v, "b").count("1") % 2 != ps[i]:
            break
    else:
        
        s += 1

print(s)

Solution (Python):
from itertools import product

n, m = map(int, input().split())

switches = []
for i in range(m):
  k, *s = map(int, input().split())
  switches.append(s)

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

patterns = product([0, 1], repeat=n)
cnt = 0
for pattern in patterns:
  for switch, onoff in zip(switches, onoffs):
    switch_ons = 0
    for switch_num in switch:
      if pattern[switch_num-1] == 1:
        switch_ons += 1
    if switch_ons % 2 != onoff:
      break
  else:
    cnt += 1
    
print(cnt)

Solution (Python):

def remain(l_p, sw_p):
    cnt = 0
    for l, on in zip(l_p, sw_p):
        _on = int(on)
        if _on == 0:
            continue
        if l == _on:
            cnt += 1
    return cnt % 2


n, m = map(int, input().split())

on_table = [[0] * n for _ in range(m)]

for i in range(m):
    line = input().split()
    for j in map(int, line[1:]):
        on_table[i][j-1] = 1


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

pattern = 2 ** n
max_bin = bin(pattern - 1)
bin_len = len(max_bin) - 2
format_pattern = "{:0" + str(bin_len) + "b}"
sw = [format_pattern.format(i) for i in range(pattern)]

cnt = 0
for _sw in sw:
    flag = True
    for _p, lite in zip(p, on_table):
        chk = remain(lite, _sw)
        if chk != _p:
            flag = False
            break

    if flag:
        cnt += 1

print(cnt)

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

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

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

cnt = 0
for i in range(2**N):
    light = 0
    switch = format(i, '0'+str(N)+'b')
    for j in range(M):
        pj = p[j]
        kj = ks[j][0]
        on = 0
        for l in range(1, kj+1):
            if switch[ks[j][l]-1] == '1':
                on += 1
        if on % 2 == pj:
            light += 1
        else:
            break
    if light == M:
        cnt += 1

print(cnt)

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

k_s = []
for i in range(m):
    k_s.append([int(x) for x in input().split()])
p = [int(x) for x in input().split()]
ans = 0
sw = [[0]*n for i in range(m)]

for i in range(m):
    for j in range(len(k_s[i])-1):
        sw[i][k_s[i][j+1]-1]=1
for i in range(2**n):
    s = [0]*n
    k=n-1
    while(i>=1):
        s[k] = (i%2)
        i = int(i/2)
        k -= 1
    tmp = [0]*m
    for j in range(m):
        f = 1
        for x in range(n):
            tmp[j] += sw[j][x]*s[x]
        if(tmp[j]%2!=p[j]):
            f = 0
            break
    ans += 1*f
print(ans)

Solution (Python):
n,m = map(int,input().split())
ks = [list(map(int,input().split())) for x in range(m)]
plis = list(map(int,input().split()))
ans = 0
llis=[]
for x in range(2**n):
    sw_lis = [0]*n
    for y in range(n):
        if ((x >> y)&1):
            sw_lis[y] = 1
    llis.append(sw_lis)
for sw in llis:
    on = 0
    for x in range(m):
        judge = 0
        for i in ks[x][1:]:
            judge += sw[i-1]
        if judge%2 == plis[x]:
            on += 1    
    if on == m:
        ans += 1
print(ans)

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

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

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

ans = 0
for i in range(pow(2, N)):
    e = '{:010b}'.format(i)[::-1]
    go = True
    for j in range(M):
        if go==False:
            break
        cnt = 0
        for d in S[j]: 
            if e[d-1]=="1":
                cnt += 1
        if cnt%2 == P[j]:
            go = True
        else:
            go = False
    if go:
        ans += 1

print(ans)

Solution (Python):
def c_switches(N, M, Switches, P):
    digit = N
    ans = 0
    for b in range(1 << digit):
        cnt = 0
        for i, (_, *switch) in enumerate(Switches):
            count = 0
            for d in range(digit):
                if (((1 << d) & b) != 0) and (d + 1 in switch):
                    count += 1
            if (count % 2) == P[i]:
                cnt += 1
        if cnt == M:
            ans += 1
    return ans

N, M = [int(i) for i in input().split()]
Switches = [[int(i) for i in input().split()] for j in range(M)]
P = [int(i) for i in input().split()]
print(c_switches(N, M, Switches, P))

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

switches = []
for x in range(m):
	inputs = list(map(int, input().split()))
	switches.append(inputs[1:])
	
remainders = list(map(int, input().split()))

count = 0
for x in range(2 ** n):
	bin_x = '{:010b}'.format(x)
	
	
	flag= True
	for j, indexes in enumerate(switches):
		
		summation = 0
		for i in indexes:
			summation += int(bin_x[-i])
			
		
		if summation % 2 != remainders[j]:
			flag = False
	if flag:
		
		count += 1

print(count)

Solution (Python):
n, m = map(int, input().split())
h = []
for i in range(m):
    h.append(list(map(int, input().split())))
    
p = list(map(int, input().split()))
ans = 0
for i in range(2 ** n):
    g = format(i, "010b")
    count = 0
    
    for j in range(m):
        x = 0
        for k in range(len(h[j]) - 1):
            x += int(g[10 - h[j][k+1]])
        if x % 2 != p[j]:
            break
        count+= 1
    
    if count == m:
        ans += 1


print(ans)

Solution (Python):
from itertools import permutations, combinations,combinations_with_replacement,product
n,m=map(int, input().split())

a=[list(map(int, input().split())) for i in range(m)]
p=list(map(int, input().split()))
count=0
for sw in product([0,1],repeat=n):
    flag=1
    for i in range(m):
        on=0
        for j in range(a[i][0]):
            on+=sw[a[i][j+1]-1]
        
        if on%2!=p[i]:
            flag=0
        
    count+=flag
print(count)

Solution (Python):
import sys
def c():
    p = [[int(t) for t in r.split(' ')] for r in sys.stdin.read().split('\n') if r != '']
    N, M = p[0]
    l = p[1:M + 1]
    cond = p[M + 1]
    count = 0
    for i in range(0, 1<<N):
        cc = 0
        for j in range(0, M):
            b = 0b0
            for k in l[j][1:]:
                if (i >> (k - 1)) & 0b1 == 1:
                    b = ~b
            if b & 0b1 != cond[j]:
                break
            cc = cc + 1
        if cc == M:
            count = count + 1
    print(count)
c()

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

for i in range(2**n):
    num=str(bin(i))[2:]
    num=num.zfill(n)
    num=num[::-1]
    
    judge=1
    for j in range(m):
        cnt=0
        
        for q in range(len(s[j])):
            if num[s[j][q]-1]=='1':
                cnt+=1
        if cnt%2!=p[j]:
            judge=0
            break
    if judge:
        ans+=1
print(ans)

Solution (Python):

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

KS_list=[]

for i in range(M):
  KS_list.append([int(e) for e in input().split()])

P_list = [int(e) for e in input().split()]


switch_state=[]
switch_stop=[]
ans=0

for i in range(N):
  switch_state.append("0")
  switch_stop.append("1")

while switch_state!=switch_stop:
  

  
  for i in range(M):
    k = KS_list[i][0]
    on_number = 0
    for j in range(1,k+1):
      
      if switch_state[KS_list[i][j]-1]=="1":
        
        on_number+=1
      
        
  
    
    
    
    if on_number%2!=P_list[i]:
      
      break
    elif on_number%2==P_list[i] and i==M-1:
      
      ans+=1
 
  
  if switch_state.pop(-1)=="0":
    switch_state.append("1")
  else:
    i = 1
    while(switch_state.pop(-1)!="0"):
      i = i + 1

    switch_state.append("1")
    for j in range(i):
      switch_state.append("0")




for i in range(M):
  k = KS_list[i][0]
  on_number = 0
  for j in range(1,k+1):
    
    if switch_state[KS_list[i][j]-1]=="1":
      
      on_number+=1
    
      
      
  
  

  if on_number%2!=P_list[i]:
    
    break
  elif on_number%2==P_list[i] and i==M-1:
    ans+=1
    
    
print(ans)

Solution (Python):
import itertools


sw_n,den_n = list(map(int,input().split()))
dens = []

for _ in range(den_n):
    dens.append(list(map(int,input().split()[1:])))
den_kyo = list(map(int,input().split()))

patt = list(itertools.product([0,1], repeat=sw_n))

res = 0

for pat in patt:
    kyoka = True
    for i,den in enumerate(dens):
        sums = 0
        for j in den:
            sums += pat[j-1]
        if sums%2 != den_kyo[i]:
            break
    else:
        res+=1


print(res)

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

ans = 2**N

for i in range(2**N):
 tentouList = format(i,  '0' + str(N) + 'b')
 
 for j in range(M):
     tentouSum = 0
     for k in range(1, ksList[j][0]+1):
         tentouSum = tentouSum + int(tentouList[N - ksList[j][k]])
         
     
     
     if tentouSum % 2 != pList[j]:
         
         ans = ans - 1
         break


print(ans)

Solution (Python):
N, M = map(int, input().split())
S = []
for i in range(M):
    k = list(map(int, input().split()))
    S.append(k[1:])
P = list(map(int, input().split()))
ans = 0
for i in range(2 ** N):
    a = 0
    for j in range(M):
        t = 0
        for s in S[j]:
            t += (i >> (s - 1)) & 1
        if t % 2 == P[j]: a += 1
    if a == M: ans += 1
print(ans)

Solution (Python):
n,m=map(int,input().split(" "))
denQs=[]
count=0
for i in range(m):
	denQ=[]
	line=input().split(" ")
	for j in range(int(line[0])):
		denQ.append(int(line[j+1]))
	denQs.append(denQ)
denQrights=input().split(" ")
ansLst=[[0],[1]]
for i in range(n-1):
	nxtAnsLst=[]
	for a in ansLst:
		nxtAnsLst.append(a+[0])
		nxtAnsLst.append(a+[1])
	ansLst=nxtAnsLst
for a in ansLst:
	isFound=True
	for i in range(m):
		c=0
		for j in denQs[i]:
			c+=a[j-1]
		if c%2!=int(denQrights[i]):
			isFound=False
			break;
	if isFound:
		count+=1
print(count)

Solution (Python):

N, M = 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()))
ans = 0

for i in range(2**N):
    for k in range(M):
        a = 0
        b = True
        for j in K[k][1:]:  
            if (((i >> (j-1) )& 1)):  
                a += 1
        if a%2 != p[k]:
            b = False
            break
    if b:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
sw = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
ans = 2**n

for i in range(2**n):
  bin_str = format(i, '010b')[::-1]
  for j in range(m):
    sum = 0
    for k in range(sw[j][0]):
      sum += int(bin_str[sw[j][k+1]-1])
    if sum % 2 != p[j]:
      ans -= 1
      break
      
print(ans)

Solution (Python):
import itertools
N,M = map(int,input().split())
K = [0]*M
S = [[0] *N for _ in range(M)]
for i in range(M):
    tmp = list(map(int,input().split()))
    K[i] = tmp[0]
    for s in tmp[1:]:
        S[i][s-1] = 1
P = list(map(int,input().split()))

ptns = list(itertools.product((0,1),repeat=N))
ans = 0

for p in ptns:
    
    for i in range(M):
        
        on_count = 0
        for j in range(N):
            on_count += S[i][j] and p[j]
        if on_count%2 != P[i]:
            break
        
    else:
        
        ans += 1
print(ans)

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

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

ans=0
for i in range(2**N):
  check=1
  for j in range(M):
    sum=0
    for c in range(s[j][0]):
      sum += (i//(2**(s[j][c+1]-1)))%2
    if (sum%2)!=p[j]:
      check = 0
  if check ==1:
    ans += 1
print(ans)

Solution (Python):
N, M = [int(nm) for nm in input().split()]
S = []
for m in range(M):
  KS = [int(ks) for ks in input().split()]
  S.append(KS[1:])
P = [int(p) for p in input().split()]
ans = 0
for n in range(2**N):
  on_off = str(format(n, "b"))
  if len(on_off)<N:
    on_off = "0"*(N-len(on_off)) + on_off
  on_light = 0
  for m in range(M):
    nm_of_light = 0
    for sm in range(len(S[m])):
      nm_of_light += int(on_off[S[m][sm]-1])
    if nm_of_light % 2 == P[m]:
      on_light += 1
  if on_light == M:
    ans += 1
print(ans)

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

s=[]
for i in range(m):
    l=list(map(int,input().split()))
    l.pop(0)
    s.append(l)
p=list(map(int,input().split()))

res=0
for i in range(pow(2,n)):
    sw=("0000000000000000000000"+bin(i)[2:])[-n:]
    failed=False
    for j in range(m):
        sum=0
        for k in range(len(s[j])):
            sum+=int(sw[s[j][k]-1])
        if sum%2!=p[j]:
            failed=True
            break
    if not failed:
        res+=1
print(res)