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

ans = 0
sw = [0] * N
for i in range(2 ** N):
    state = [0] * M
    S = list(bin(i))
    S = S[2:]
    while len(S) < N:
        S = ['0'] + S
    
    for j in range(N):
        sw[j] = int(S[N-1-j])
    for j in range(M):
        cnt = 0
        for k in ks[j][1:]:
            if sw[k-1] == 1:
                cnt += 1
        if cnt % 2 == p[j]:
            state[j] = 1
            
    if not(0 in state):
        ans += 1
    
print(ans)

Solution (Python):
import numpy as np

def main():
    temp = input().split()
    N = int(temp[0])
    M = int(temp[1])
    k = [] 
    s = []
    for m in range(M):
        temp = input().split()
        k.append(int(temp[0]))
        s.append([])
        for x in temp[1:]:
            s[m].append(int(x)-1)
    p = []
    temp = input().split()
    for x in temp:
        p.append(int(x))
    res = 0
    for i in range(2**N):
        suitti = ret_suitti(i,N)
        if(hantei(suitti, s, p)):
            res += 1
    print(res)

def ret_suitti(i,N):
    suitti = []
    shou = i
    for n in range(N):
        amari = shou % 2
        shou = shou // 2
        if(amari == 0):
            suitti.append(0)
        else:
            suitti.append(1)
    return suitti

def hantei(suitti, s, p):
    M = len(p)
    flag = 1
    for m in range(M):
        on_suitti = 0
        for x in s[m]:
            if(suitti[x] == 1):
                on_suitti += 1
        if(on_suitti % 2 != p[m]):
            flag = 0
    if(flag == 1):
        return True
    else:
        return False

if __name__ == "__main__":
    main()

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

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

p = [int(i) for i in input().split()]
ans = 0
for i in range(2**N):
    tmp = [0]*M
    for j in range(N):
        if (i >> j) & 1:
            for z in S[j]:
                tmp[z] = tmp[z]^1

    if p == tmp:
        ans += 1
print(ans)

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

patterns = []
for i in range(2**N):
    l = list(map(int,list(format(bin(i)[2:]))))
    l = [0 for _ in range(N-len(l))] + l
    patterns.append(l)

for i in range(M):
    tmp_patterns = []
    for pat in patterns:
        tmp_sum = 0
        for s in s_list[i]:
            tmp_sum += pat[s-1]
        if tmp_sum%2 == p_list[i]:
            tmp_patterns.append(pat)
    patterns = tmp_patterns

print(len(patterns))

Solution (Python):

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

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

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

numlist = []
for i in range(2**N):
    numbin = str(bin(i+1024))
    numbin = numbin[-N:]
    numlist.append(numbin)

answer = 0
for j in numlist:
    
    flag = True
    for i in range(M):
        
        total = 0
        for k in slist[i]:
            total += int(j[-k])
        if(total%2 != plist[i]):
            flag = False
            break
    if(flag==True):
        answer += 1

print(answer)

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

p_list = list(map(int, input().split(" ")))
patterns = 0
for state in range(2 ** N):
    s_bits = [bool(state & (2 ** i)) for i in range(N)]
    ramps = 0
    for p, switches in zip(p_list, s_table):
        n = 0
        for s in switches:
            n += s_bits[s - 1]
        if n % 2 == p:
            ramps += 1

    if ramps == M:
        patterns += 1

print(patterns)

Solution (Python):
from itertools import product
n, m = map(int,input().split())
ks = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
cnt = 0
for pr in product([0, 1], repeat=n):
    pr = list(pr)
    for i, a in enumerate(ks):
        k = a[0]
        s = a[1:]

        c = 0
        for j in range(k):
            c += pr[s[j]-1]
        if c % 2 == p[i]:
            continue
        else:
            break
    else:
        cnt += 1
print(cnt)

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

s = list()

for m in range(M):
    ks = list(map(int, input().split()))
    zz = [0] * 10
    for u in range(1, len(ks)):
        zz[ks[u] - 1] = 1
    s.append(zz)

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

ans = 0
for z in range(2 ** N):
    y = [0] * 10
    for x in range(10):
        y[x] = z >> x & 1
    b = True
    for m in range(M):
        w = 0
        for q in range(10):
            w = w + (s[m][q] & y[q])
        b = b & ((w % 2) == p[m])
    if b == True:
        ans = 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()))




ans = 0

import itertools
for i in itertools.product([0,1], repeat=N):
  righted = 0
  for iter, j in enumerate(ks):
  
    cnt = 0
    for k in range(1,len(j)):
      cnt += i[j[k]-1]
    if cnt % 2 == p[iter]:
      righted += 1
  if len(ks) == righted:
    ans += 1
    
print(ans)

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

cnt = 0
for n_i in range(2**n):
    s_now = bin(n_i)[2:].zfill(n)
    
    next_m = False

    for m_i in range(m):
        sum_tmp = 0
        for s_i in s[m_i]:
            sum_tmp += int(s_now[int(s_i)-1])
        
        if sum_tmp % 2 != p[m_i]:
            next_m = True
            break
    if next_m:
        continue
    cnt += 1

print(cnt)

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

ary = []
for i in range(2 ** N):
    ary.append((bin(i)[2:].zfill(N)))

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

cnt = 0
for i in range(2 ** N):
    flg = 0
    for j in range(M):
        tot = 0
        for k in range(len(ary2[j])-1):
            tot += int(ary[i][ary2[j][k+1]-1])
        if tot % 2 != P[j]:
            flg = 1
            break
    if flg == 0:
        cnt += 1
print(cnt)

Solution (Python):
NM = list(map(int, input().split()))
N = NM[0]
M = NM[1]
ks = []
k = []
s = []
for ind in range(M):
    ks.append(list(map(int,input().split())))
    k.append(ks[ind][0])
    s.append(ks[ind][1:])
p = list(map(int, input().split()))

count = 0
onoff = [0 for _ in range(N)]
for switch in range(1<<N):
    res = switch
    for ind in range(N):
        onoff[ind] = res&1
        res = res>>1
    
    on = 0
    for denkyu in range(M):
        su = 0
        for sw in s[denkyu]:
            su = su + onoff[sw-1]
        if p[denkyu] == (su % 2):
            on = on + 1
    
    if on == M:
        count = count + 1

print(count)

Solution (Python):
import numpy as np
import itertools
n, m = [int(i) for i in input().split()]
A = np.zeros((m, n), dtype = int)
for i in range(m):
    tmp = [int(i) for i in input().split()]
    for j in range(1, len(tmp)):
        A[i][tmp[j]-1] = 1
p = np.array([int(i) for i in input().split()])
ans = 0

lst = list(itertools.product([0,1], repeat = n))
for i in range(len(lst)):
    tmp = np.remainder(np.dot(A, np.array(lst[i])), 2)
    if np.array_equal(tmp, p):
        ans += 1
print(ans)

Solution (Python):
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()))

count = 0
for l in range(2**N):
    flag = 1
    for t in range(m):
        sigma = 0
        for j in range(k[t]):
            sigma += l // (2**(s[t][j]-1))
        if sigma % 2 !=p[t]:
            flag =0
            break
    count += flag
print(count)

Solution (Python):
N,M = list(map(int,input().split()))
Kl = []
for i in range(M):
    Kl.append(list(map(int,input().split())))
P = list(map(int,input().split()))
ans = 0

for i in range(2**N):
    onoff = [False for i in range(M)]
    b = format(i, 'b').zfill(N)
    for k in range(M):
        cnt = 0
        for l in range(Kl[k][0]):
            if b[Kl[k][l+1]-1] == "1":
                cnt += 1

        if int(cnt % 2) == int(P[k]):
            onoff[k] = True
    if False not in onoff:
        ans+=1

print(ans)

Solution (Python):
def read():
    N, M = list(map(int, input().strip().split()))
    S = [-1] * M
    for i in range(M):
        inputs = list(map(int, input().strip().split()))
        S[i] = sw_to_seq(inputs[0], inputs[1:])
    P = list(map(int, input().strip().split()))
    return N, M, S, P


def sw_to_seq(k, s):
    s_seq = 0
    for i in range(k):
        bit = 1 << (s[i] - 1)
        s_seq += bit
    return s_seq


def count_sw_on(s_seq, i):
    sw_on = s_seq & i
    count = 0
    while sw_on > 0:
        count += (sw_on & 1)
        sw_on >>= 1
    return count


def solve(N, M, S, P):
    count_all_sw_on = 0
    for i in range(1 << N):
        num_sw_on = 0
        for j in range(M):
            if count_sw_on(S[j], i) % 2 == P[j]:
                num_sw_on += 1
        if num_sw_on == M:
            count_all_sw_on += 1
    return count_all_sw_on


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

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

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

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

t = [False for i in range(n)]


_ = True
counter = 0
while(_):
    flag = True
    hantei = True



    for e,ki in enumerate(k):
        tmp = False
        for i in range(1,ki[0]+1):
            if t[ki[i]-1] == tmp:
                tmp = False
            else:
                tmp = True

        if p[e] != tmp:
            hantei = False
    if hantei:
        counter+=1


    for i in range(n):
        if flag and t[i]:
            t[i] = not t[i]
        elif flag:
            t[i] = not t[i]
            flag = False

    if flag:
        break

print(counter)

Solution (Python):
import itertools

N, M = map(int, input().split())
skss = []
for _ in range(M):
    k, *sks = map(int, input().split())
    skss.append(sks)
pMs = list(map(int, input().split()))

count = 0
for i in range(2 ** N):
    pMstmp = pMs[:]
    for j, b in enumerate(format(i, '0' + str(N) + 'b')):
        if b == '0':
            continue
        for k, sks in enumerate(skss):
            if j + 1 in sks:
                pMstmp[k] ^= 1
    if sum(pMstmp) == 0:
        count += 1

print(count)

Solution (Python):
N, M = [int(i) for i in input().split()]
range(M)
switches = [[int(i) for i in input().split()] for _ in range(M)]
P = [int(i) for i in input().split()]
count=0
for i in range(2**N):
    ss = [int(i) for i in list(bin(i))[2:]]
    ss = [0] * (N - len(ss)) + ss
    t = True
    for e, switch in enumerate(switches):
        a = P[e]
        if len([ss[i-1] for i in switch[1:] if ss[i-1]==1]) %2 !=a:
            t = False
            break
    if t:
        count +=1

print(count)

Solution (Python):


import itertools

N, M = map(int, input().split())
switch_list = []
joken_list = []

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

switch_pattern_list = []
for i in itertools.product((0,1), repeat=N):
    switch_pattern_list.append(i)

output = 0

for switch_pattern in switch_pattern_list:
    for i in range(len(switch_list)):
        on = 0
        for switch_number in switch_list[i]:
            if switch_pattern[switch_number - 1] == 1:
                on += 1
        if on % 2 != joken_list[i]:
            break
        if i == len(switch_list) - 1:
            output += 1

print (output)

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

lis = []
for _ in range(m):
    new = list(map(int, input().split()))
    lis.append(new[1:])

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

res = 0
for i in range(2**n):
    cou = [0 for k in range(m)]
    binary = '0'*(n - len(bin(i)[2:])) + bin(i)[2:]
    for j in range(n):
        if binary[j] == '1':
            for k in range(len(lis)):
                if j + 1 in lis[k]:
                    cou[k] += 1 
    if all((cou[x] - plist[x])%2 == 0 for x in range(m)):
        res += 1
print(res)

Solution (Python):
n, m = [int(i) for i in input().split()]
switch_list_for_light_index = [0] * m

for light_index in range(m):
    switch_list_for_light_index[light_index] = [int(i) for i in input().split()[1:]]

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


def light_is_on(light_index, case):
    switch_list = switch_list_for_light_index[light_index]
    switch_on_count = 0
    for switch in switch_list:
        switch_on_count += int(case[switch - 1])
    if switch_on_count % 2 == p[light_index]:
        return True
    else:
        return False

answer = 0

for case_num in range(2**n):
    case = bin(case_num)[2:].zfill(n)
    suc_num = 0
    for light_index in range(m):
        if light_is_on(light_index, case) == True:
            suc_num += 1
        else:
            break
    if suc_num == m:
        answer += 1

print(answer)

Solution (Python):
from itertools import product

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


ks = [list(map(lambda x: x - 1, list(_)[1:])) for _ in ks]

ans = 0
for state in product(range(2), repeat=n):
    for pi, si in zip(p, ks):
        cum = 0
        for sij in si:
            cum += state[sij]
        if cum % 2 != pi:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
N,M = map(int,input().split())
kss = []
for _ in range(M):
    kss.append(list(map(int,input().split())))
p = list(map(int,input().split()))
answer = 0
for i in range(1 << N):
    members = {}
    for j in range(N):
    
        if (i>>j)&1 == 1:
            
            members[j+1] = 1
        else:
            members[j+1] = 0
    for k in range(M):
        howManySwitchesOn = 0
        for l in range(len(kss[k])):
            if l == 0:
                continue
            if members[kss[k][l]] == 1:
                howManySwitchesOn += 1
        if howManySwitchesOn%2 != p[k]:
            break
    else:
        answer += 1
    
print(answer)

Solution (Python):
import numpy as np

def add1(s, i = -1):
    if s[i] == 0:
        s[i] = 1
        return s
    else:
        s[i] = 0
        return add1(s, i-1)
    
n, m = map(int, input().split())

k = []
s = []

for i in range(0, m):
    ki, *si = map(int, input().split())
    k.append(ki)
    s.append(si)

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

sw = np.zeros(n)

ons = 0
ans = 0
sums = 0

for i in range(0, 2**n):
    for j in range(0, m):
        for l in s[j]:
            ons += sw[l-1]
        if ons % 2 == p[j]:
            sums += 1
        ons = 0
    if sums == m:
        ans += 1
    sums = 0
    if i != 2**n - 1:
        sw = add1(sw)


print(ans)

Solution (Python):


def f(T, X, S, k):
    if k == len(T):
        return 1 if S == X else 0

    return f(T, X, S, k+1) + f(T, X, S^T[k], k+1)
        

    

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

    T = [0]*N
    for i in range(M):
        L = list(map(int, input().split()))
        for sw in L[1:]:
            T[sw-1] |= (1 << i)

    X = 0
    P = map(int, input().split())
    for i, p in enumerate(P):
        X |= ((1<<i) if p == 1 else 0)



    print(f(T, X, 0, 0))


if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
ks = [list(map(int, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
c = 0
for i in range(2**n):
  li = []
  flag = False
  for j in range(n):
    if ((i>>j)&1):
      li.append(j+1)
  for j in range(m):
    s = set(li)
    ss = set(ks[j])
    s = s & ss
    if len(s) % 2 == p[j]:
      flag = True
    else:
      flag = False
      break
  if flag:
    c += 1
print(c)

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

ans = 0
for num in range(2 ** N):
    bit = str(bin(num)[2:]).zfill(N)
    breakFlag = False
    for i_1, sList in enumerate(sLists):
        count = 0
        for i_2, b in enumerate(list(bit), start=1):
            if i_2 in sList and b == "1":
                count += 1
        if count % 2 != pList[i_1]:
            breakFlag = True
            break
    if not breakFlag:
        ans += 1

print(ans)

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

lights = []

for _ in range(M):
    light = np.zeros(N + 1, dtype='int32')
    line = list(map(int, input().split()))
    k = line[0]
    switches = line[1:]
    for s in switches:
        light[s] = 1
    lights.append(light)

p_list = list(map(int, input().split()))
for i in range(M):
    lights[i][0] = p_list[i]

result = 0
for S in range(2**N):
    switch_state = np.array([1] + list(map(int, list(('0000000000' + bin(S)[2:])[-N:]))))
    success = True
    
    for l in lights:
        if sum(l*switch_state) % 2 != 0:
            success = False
            break

    if success:
        result += 1

print(result)

Solution (Python):
import sys
import itertools

def intinput(): return map(int,sys.stdin.readline().split())

n,m=intinput()
l = []
for i in range(m):
    l.append(list(map(lambda e:e-1,list(intinput())[1:])))
p = list(intinput())
x = list(itertools.product((0,1),repeat=n))
cnt=0
for i in x:
    r=0
    f=0
    for j in l:
        if sum(list(map(lambda e:i[e],j)))%2!=p[r]:
            f=1
            break
        r+=1
    if f==0:
        cnt += 1
print(cnt)

Solution (Python):


import collections
import copy


class Node(object):

  def __init__(self, n, m):
    self.lamps = [[0] * n for _ in range(m)]
    self.status = [[0, 0] for _ in range(m)]
    self.index = 0

  def create_children(self):
    children = []

    child0 = copy.deepcopy(self)
    child1 = copy.deepcopy(self)

    for i in range(len(self.status)):
      child0.status[i][0] -= child0.lamps[i][self.index]
      child1.status[i][0] -= child1.lamps[i][self.index]
      child1.status[i][1] += child1.lamps[i][self.index]

    child0.index += 1
    child1.index += 1

    if child0.is_valid():
      children.append(child0)

    if child1.is_valid():
      children.append(child1)

    return children

  def is_valid(self):
    for r, v in self.status:
      if r == 0 and v % 2 == 1:
        return False

    return True


def main():
  n, m = map(int, input().split())
  root = Node(n, m)

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

    for j in v:
      root.lamps[i][j - 1] = 1

    root.status[i][0] = len(v)

  for i, v in enumerate(map(int, input().split())):
    root.status[i][1] = v

  stack = collections.deque()
  stack.append(root)
  count = 0

  while len(stack) != 0:
    node = stack.pop()

    children = node.create_children()

    for child in children:
      if child.index == n:
        count += 1
      else:
        stack.append(child)

  print(count)


if __name__ == '__main__':
  main()

Solution (Python):

"""
Created on Sun May 26 20:56:00 2019

@author: Yamazaki Kenichi
"""

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(2**N):
    t = '{:010b}'.format(i)
    flg = True
    for j in range(M):
        tmp = 0
        for k in range(ks[j][0]):
            tmp += int(t[-ks[j][k+1]])

        if tmp%2 == p[j]:
            continue
        else:
            flg = False
            break

    if flg:
        ans += 1

            
print(ans)

Solution (Python):
def multy(a,b):
	c = 0
	for i in range(len(a)):
		c += a[i]*b[i]
	return c
N,M = map(int, raw_input().split())
ks = []
for i in range(M):
	ks2 = map(int, raw_input().split())
	ks.append(ks2)
pm = map(int, raw_input().split())
plist = []
for i in ks:
	t = [0]*N
	ini = 1
	for j in i:
		if(ini == 1):
			ini = 0
			continue
		else:
			t[j-1] = 1
	plist.append(t)
slist = []
for i in range(2**N):
	t = []
	for j in range(N):
		t.append(i%2)
		i = i/2
	slist.append(t)
r = 0
for p in plist:
	s2 = []
	for s in slist:
		if(multy(p,s)%2 == pm[r]):
			s2.append(s)
	r = r+1
	slist = s2
print(len(slist))

Solution (Python):


from collections import defaultdict
N, M = list(map(int, input().split()))
switch = dict()
for i in range(M):
    inputs = list(map(int, input().split()))
    k, list_s = inputs[0], inputs[1:]
    switch[i] = list_s
    
ps = list(map(int, input().split()))

ans = 0
for i in range(2**N):
    ok = True
    
    on_s = []
    for idx, s in enumerate(bin(i)[::-1]):
        if s == 'b':
            break
        if s == '1':
            on_s.append(idx+1)
    for k, v in switch.items():
        on_cnt = 0
        for num in v:
            if num in on_s:
                on_cnt += 1
        if on_cnt % 2 == ps[k]:
            continue
        else:
            ok = False
            break
    if ok:
        ans += 1
    
print(ans)

Solution (Python):

"""
Created on Sun May 26 19:03:42 2019
ABC128C
@author: maezawa
"""
import itertools
n, m = list(map(int, input().split()))
lamp = []
for _ in range(m):
    kin = list(map(int, input().split()))
    kin.pop(0)
    lamp.append(kin)
p = list(map(int, input().split()))
cntall = 0
for kbin in itertools.product(range(2), repeat=n):
    for i in range(m):
        cnt = 0
        for j in lamp[i-1]:
            if kbin[j-1] == 1:
                cnt += 1
        if cnt % 2 != p[i-1]:
            
            break
    else:
        cntall += 1
        

print(cntall)

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

p=list(map(int,input().split()))
b=0b0000000000
cnt=0
while b < 0b1<<N:
    s = str(bin(b))[2:].zfill(N)
    for i in range(M):
        sum = 0
        for j in k[i]:
            if s[N-j]=="1":
                sum += 1
        if sum%2!=p[i]:
            break
    else:
        cnt+=1
    b+=1
print(cnt)

Solution (Python):
import itertools
import numpy as np
n, m = map(int, input().split())
switch_comb = itertools.product((0, 1), repeat=n)
switch_arr = np.array(list(switch_comb))
res = 0
light_list = []
for i in range(m):
  s_list = list(map(int, input().split()))[1:]
  s_list = [i - 1 for i in s_list]
  light_list.append(s_list)
print()
flg_list = list(map(int, input().split()))
for j, l in enumerate(light_list):
  ans = flg_list[j]
  switch_arr = switch_arr[(switch_arr[:, l].sum(axis=1) % 2) == ans, :]
  if switch_arr.shape[0] == 0:
    break
print(switch_arr.shape[0])

Solution (Python):
import itertools
N,M = map(int,input().split())
data = [0,1]
state_list = list(itertools.product(data, repeat=N))
l = [[int(x) for x in input().split()] for i in range(M)]
p = list(map(int,input().split()))
ans = 0
for i in range(2**N):
  k_count = 0
  for j in range(M):
    tmp = l[j][0]
    tmp_s = l[j][1:]
    count = 0
    for k in range(tmp):
      if state_list[i][tmp_s[k]-1] == 1:
        count += 1
    if count%2 == p[j]:
      k_count += 1
  if k_count == M:
    ans += 1
print(ans)

Solution (Python):
import itertools
N,M = map(int,input().split())
ks = []
for _ in range(M):
    ks.append(input().split())

pList = list(input().split())
result = 0
was = []
cases = list(itertools.product(['1','0'], repeat=N))
for case in cases:
    light = 0
    for p,x in zip(pList,ks):
        k = x[0]
        s = x[1:]
        oncount = 0
        for c in s:
            if case[int(c)-1] == '1':
                oncount += 1
        if oncount%2 == int(p):
            light += 1
    if light == M:
        result += 1
print(result)

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

k = []
k_bit = []

for i in range(M):
    arr = list(map(int, input().split()))
    arr.pop(0)
    k.append(arr)
    val = 0
    for e in arr:
        val += 2 ** (e - 1)
    k_bit.append(val)

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

result = 0

for i in range(2 ** N):
    judge = True
    for j in range(M):
        ret = i & k_bit[j]
        on = 0
        for k in range(10):
            on += (ret >> k) % 2
        on = on % 2
        if (on != p[j]):
            judge = False
    if (judge):
        result += 1

print(result)

Solution (Python):
n, m = [int(i) for i in input().split()]
K = []
S = []
for mi in range(m):
    k, *s = [int(i) for i in input().split()]
    K.append(k)
    S.append(s)
P = [int(i) for i in input().split()]

ans = 0
for ni in range(2**n):
    bin_ni = format(ni, "010b")
    ok_flag = True
    for mi in range(m):
        sum_on = 0
        for ki in range(K[mi]):
            sum_on += int(bin_ni[-S[mi][ki]])
        if sum_on%2 != P[mi]:
            ok_flag = False
            break
    if ok_flag:
        ans += 1
print(ans)

Solution (Python):
N,M=list(map(int,input().split(" ")))
sw=[]
for z in range(M):
  buf=list(map(int,input().split(" ")))
  k=buf[0]
  mask=0
  for x in range(1,k+1):
    mask|=2**(buf[x]-1)
  sw.append(mask)


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

cnt=0

for z in range(2**N):
  flag=True
  for i,x in enumerate(sw):
    y=z&x
    bitcount=0
    while y!=0:
      if y&1==1:
        bitcount+=1
      y=y>>1

    if bitcount%2!=p[i]:
      flag=False
  if flag:
    cnt+=1

print(cnt)

Solution (Python):

import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
input = sys.stdin.readline
 










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

	KS = []
	for i in range(M):
		tmp = input().split(" ")
		tmp = [int(s) for s in tmp]
		KS.append(tmp[1:])
	
	P = input().split(" ")
	P = [int(s) for s in P]

	ans = 0
	for den in range(0, 2**N):
		flg = True
		for j, val in enumerate(KS):
			tmp = 0
			for vol in val:
				aa = vol-1
				

				if ((den & 2**(vol-1)) >> (vol-1)) == 1:
					tmp += 1
			if (tmp % 2) != P[j]:
				flg = False
		if flg == True:
			ans += 1

	print(ans)

if __name__ == "__main__":
	main()

Solution (Python):
import numpy as np
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()))
chk=[]
for i in range(m):
    tmp=[0]*n
    for k in range(1,len(l[i])):
        tmp[l[i][k]-1]+=1
    chk.append(np.array(tmp))
chk=np.array(chk)

cnt=n
sw=[]
for i in range(2**cnt):
    ln=[0]*cnt
    for j in range(cnt):
        if ((i>>j)&1):
            ln[cnt-j-1]=1
    sw.append(np.array(ln))
sw=np.array(sw)
cnt=0
for k in range(len(sw)):
    flag=True
    for i in range(m):
        if np.sum(sw[k]*chk[i])%2!=p[i]:
            flag=False
    if flag:
        cnt+=1
       
print(cnt)

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

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

import itertools

binary_list = [0, 1]

all_comb = list(itertools.product(binary_list, repeat=N))

count = 0

for sw_state in all_comb:
    flag = False
    
    for lamp, lamp_sw in zip(pre_list, binary_sw):
        swvalue = 0
        for lamp_single in lamp:
            swvalue += sw_state[lamp_single - 1]
        
        if swvalue % 2 == lamp_sw:
            continue
        
        else:
            flag = True
            break
        
        if flag:
            break

    if not flag:
        count += 1
        
print(count)

Solution (Python):
from sys import stdin
import numpy as np









N, M = [int(x) for x in stdin.readline().rstrip().split()]
K = []
S=[]
for i in range(M):
  A = [int(x) for x in stdin.readline().rstrip().split()]
  K.append(A[0])
  S.append(A[1:])
P = [int(x) for x in stdin.readline().rstrip().split()]
ans = 0
for i in range(2**N):
  bi = bin(1024+i)
  
  arr = [int(s=="1") for s in bi[13-N:]]
  
  Frag = True
  for j in range(M):
    sarr = S[j]
    on_sw = sum([arr[sidx-1] for sidx in sarr])
    if on_sw%2!=P[j]:
      Frag=False
      
      break
  if Frag:
    
    ans+=1
print(ans)

Solution (Python):
import itertools
import numpy

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

switchs = []
for i in range(m):
    switchs.append([int(e) for e in input().split(" ")])

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

switch_connect = numpy.zeros((m,n),dtype="int64")

for k,i in enumerate(switchs):
    for j in i[1:]:
        switch_connect[k,j-1] = 1

ret = 0
for i in itertools.product([0,1],repeat=n):
    result = numpy.dot(switch_connect, numpy.array(i).T)
    result = result%2
    ret += numpy.all(result == on_state)
print(ret)

Solution (Python):


import sys
import math
import collections


N,M = map(int, sys.stdin.readline().rstrip().split(" "))
switches = []
for _ in range(M):
    k, *s = map(int, sys.stdin.readline().rstrip().split(" "))
    
    switch_bit = sum(2**(v-1) for v in s)
    
    switches.append(switch_bit)
ps = list(map(int, sys.stdin.readline().rstrip().split(" ")))



result = 0
for i in range(2**N):
    
    for j,switch in enumerate(switches):
        pattern = switch & i
        
        if not bin(pattern).count("1") % 2 == ps[j]:
            break
    else:
        result += 1
print(result)


exit(0)

Solution (Python):
from itertools import islice

R = lambda: map(int, input().split())
n, m = R()
a = [list(islice(R(), 1, None)) for _ in range(m)]
p = list(R())
r = sum(all(sum(i >> (j - 1) & 1 for  j in r) & 1 == pi
            for r, pi in zip(a, p)) for i in range(1 << n))
print(r)