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):

import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def bit_search(n):
    res = []
    for i in range(2**n):
        st = set()
        for j in range(n): 
            if ((i >> j) & 1):
                st.add(j)
        res.append(st)
    return res

def main():
    N,M=mi()
    X = {}
    for i in range(M):
        inp = list(mi())
        X[i] = inp[1:]
    
    P = list(mi())

    ans = 0
    for combs in bit_search(N):
        res = 0
        for i in range(M):
            on_count = 0
            for j in range(len(X[i])):
                s = X[i][j] - 1 
                if s in combs:
                    on_count += 1
            
            if on_count % 2 == P[i]:
                res += 1

        if res == M:
            ans += 1


    print(ans)
                    





if __name__ == "__main__":
    main()

Solution (Python):
N,M=map(int,input().split())
s = []
for _ in range(M):
    s.append(list(map(lambda x:int(x)-1,input().split()))[1:])
p = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    fl = True
    for j in range(M):
        cnt = 0
        for sw in s[j]:
            if (i >> sw) & 1:
                cnt += 1
        if cnt % 2 != p[j]:
            fl = False
            break
    if fl:
        ans += 1
print(ans)

Solution (Python):
N,M=map(int,input().split())
s=[list(map(int,input().split()))[1:] for i in range(M)]
p=list(map(int,input().split()))
ans,cnt=0,0
for n in range(2**N):
  for m in range(M):
    cnt=0
    for i in range(N):
      if (n>>i)&1 and i+1 in s[m]:
        cnt+=1
    if cnt%2!=p[m]:
      break
  else:
    ans+=1
print(ans)

Solution (Python):
N,M=map(int,input().split())
combiList = []
for i in range (M):
  combiList.append(list(map(int, input().split())))
kakuninList = list(map(int, input().split()))
statusList = [0]*M

for j in range (M):
  combiList[j].pop(0)
res = 0

for bits in range(2**N): 
  flag = True
  statusList = [0]*M
  for j in range(N):
    if((bits>>j) & 1): 
      for k in range(M):
        if j+1 in combiList[k]:
          statusList[k] +=1
  for k in range(M):
    if statusList[k] % 2 != kakuninList[k]:
      flag = False
      break
  if flag:
    res +=1
print(res)

Solution (Python):
N, M = map(int, input().split()) 
lights = [[0] * N for _ in range(M)]
for i in range(M): 
    temp = list(map(int, input().split())) 
    k = temp[0]
    switches = temp[1:]
    for j in range(k):
        lights[i][switches[j]-1] = 1
P = list(map(int, input().split())) 

answer_count = 0
for i in range(2**N):
    flag = True
    for k in range(M):
        count = 0
        for j in range(N):
            if (i >> j) & 1:
                count += lights[k][j]
        if count % 2 != P[k]:
            flag = False
            break
    if flag:
        answer_count += 1

print(answer_count)

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

ans = 0

for i in range(2**N):
    b = format(i, "0" + str(N) + "b")
    for j in range(M):
        if sum([int(b[x-1]) for x in s[j]]) % 2 != p[j]:
            break
        if j == M - 1:
            ans += 1

print(ans)

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

    ans = 0
    for i in range(2**n):
        ls = [0]*m
        for j in range(n):
            if i & (1 << j):
                for k in range(m):
                    if j+1 in ks[k][1:]:
                        ls[k] += 1
        cnt = 0
        for l in range(m):
            if ls[l] % 2 == p[l]:
                cnt += 1
        if cnt == m:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

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

for i in range(2**n):
    status = ['+']*n
    for j in range(n):
        if ((i>>j)&1):
            status[j] = '-'
    num = 0
    for m, k in enumerate(s):
        count = 0
        for l in k:
            if status[l-1] == '+':
                count += 1
        if count%2 != p[m]:
            break
        else:
            num += 1
    if num == m+1:
        ans += 1
print(ans)

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

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

rlt = 0
pw = 2**N

for b in range(pw):
  lst = [0]*(M)
  tmp = 0
  for i in range(N):
    if b&(1<<i):
      for j in range(M):
        if i+1 in Ks[j]:
          lst[j] += 1
  for j in range(M):
    if lst[j] % 2 == Ps[j]:
      tmp += 1
  if tmp == M:
    rlt += 1
  
print(rlt)

Solution (Python):

def main():
    N, M = map(int, input().split())
    k, s = [], []
    for _ in range(M):
        lst = [int(x) - 1 for x in input().split()]
        k.append(lst.pop(0) + 1)
        s.append(set(lst))
    p = [int(x) for x in input().split()]

    ans = 0
    for bit in range(1 << N):
        now_on_switch = []
        for i in range(N):
            if bit & (1 << i):
                now_on_switch.append(i)
        lights = 0
        for i in range(M):
            cnt = 0
            for j in now_on_switch:
                cnt += 1 if j in s[i] else 0
            lights += 1 if cnt % 2 == p[i] else 0
        ans += 1 if lights == M else 0
    print(ans)


if __name__ == '__main__':
    main()

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

ans = 0

for i in range(2 ** N):
    flg = 1
    for j in range(M):
        o = 0
        for k in range(1, I[j][0]+1):
            if (i >> (I[j][k]-1)) & 1:
                o += 1
        if o % 2 != p[j]:
            flg = 0
            break
    if flg == 1:
        ans += 1
print(ans)

Solution (Python):



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



ans = 0 
for i in range(2**n):
    tmp = i 
    sw = []
    if i == 0:
        sw = [0] 
    while tmp > 0:
        sw.append(tmp&1)
        tmp = tmp>>1
    while len(sw) < n:
        sw.append(0)

    
    
    
    ok = True
    
    for j in range(m):
        tmp = 0 
        for a in range(k[j]):
            tmp += sw[s[j][a]-1]
        if tmp%2 != p[j]:
            ok = False
            break
    if ok: 
        
        ans += 1

print(ans)

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

count = 0

for i in range(2**n):

    for j in range(m):
        switch = 0
        for k in range(n):
            if (i >> k) & 1 and k+1 in d[j]:
                switch += 1
        if switch%2 != s[j]:
            break
    else:
        count += 1

print(count)

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

Solution (Python):
N,M = map(int, input().split())
s = [list(map(int, input().split()))[1:] for _ in range(M)]
p = list(map(int, input().split()))
count = 0
for i in range(1<<N):
    for m in range(M):
        switch=0
        for j in range(N):
            if (i>>j)&1 and j+1 in s[m]:
                switch += 1
        if switch%2!= p[m]:
            break
    else:
        count += 1
print(count)

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

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

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

for i in range(2 ** N):
    switch = []
    for j in range(N):  
        if (i >> j) & 1:
            switch.append(j+1)
    bulb_count = M
    for k in range(M):  
        tmp = bulb[k]  
        switch_count = 0
        for num in tmp:  
            if num in switch:
                switch_count += 1
        if switch_count % 2 == P[k]:
            bulb_count -= 1
    if bulb_count == 0:
        count += 1

print(count)

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

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

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

for i in range(2 ** N):
    switch = []
    for j in range(N):  
        if (i >> j) & 1:
            switch.append(j+1)
    bulb_count = M
    for k in range(M):  
        tmp = bulb[k]  
        switch_count = 0
        for num in tmp:  
            if num in switch:
                switch_count += 1
        if switch_count % 2 == P[k]:
            bulb_count -= 1
    if bulb_count == 0:
        count += 1

print(count)

Solution (Python):
import numpy as np
N,M = map(int, input().split())
S = []
for i in range(M):
    k,*s = map(int, input().split())
    T = [0]*N
    for j in s:
        T[j-1]=1
    S.append(T)
P = list(map(int, input().split()))
ans =0
for x in range(2**N):
    y = format(x,"0{}b".format(N))
    z = list(map(int,y))
    if all(np.dot(den,z)%2==P[nmb] for nmb,den in enumerate(S)):
        ans +=1
            
print(ans)

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush

sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,m = inpm()
S = inpll(m)
P = inpl()

ans = 0
for bi in itertools.product([0,1],repeat=n):
    for i in range(m):
        cnt = 0
        for j in range(S[i][0]):
            if bi[S[i][j+1]-1] == 1:
               cnt += 1
        if cnt%2 != P[i]:
            break
        else:
            continue
        break
    else:
        ans += 1

print(ans)

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

s = [[] for _ in range(m)]

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

targ = list(map(int,input().split()))
ans = 0


for i in itertools.product(range(2), repeat=n):
	tmpl = [0]*m
	
	for j in range(m):
		for k in s[j]:
			tmpl[j] += i[k]
	
	mode = 1
	
	for j in range(m):
		if tmpl[j]%2 != targ[j]:
			mode = 0
			break
	
	if mode:
		ans += 1

print(ans)

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

ans = 0
for i in range(1 << n):
    ok = True
    for j in range(m):
        cnt = 0
        for k in range(len(sl[j])):
            if (i >> sl[j][k] - 1)%2 == 0:
                cnt += 1
        if cnt%2 != p[j]:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

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

Nlen = 2**N
ans = 0

for i in range(Nlen):
    total = 0
    for j in range(M):
        count = 0
        for k in range(1,ks[j][0]+1): 
            if i & 2**(ks[j][k]-1) == 2**(ks[j][k]-1):
                count += 1
        if count % 2 == p[j]:
            total += 1
    if total == M:
        ans += 1

print(ans)

Solution (Python):
n, m  = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
d = [0]*(n+1)
s = 0
for i in range(2**n):
  for j in range(n):
    if i & (1<<j):
      d[j+1] = 1
    else:
      d[j+1] = 0
  for k in range(m):
    a = 0
    for l in range(1, lst[k][0]+1):
      a = (a+d[lst[k][l]])%2
    if a!=p[k]:
      break
  else:
    s += 1

print(s)

Solution (Python):
def main():
    N, M = map(int, input().split())
    S = []
    for _ in range(M):
        S.append(set(list(map(int, input().split()))[1:]))
    P = list(map(int, input().split()))

    ans = 0
    for bit in range(1 << N):
        on_switches = set([])
        for i in range(N):
            if bit & (1 << i):
                on_switches.add(i + 1)

        flag = True
        for s, p in zip(S, P):
            if len(s & on_switches) % 2 != p:
                flag = False
        if flag is True:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,m = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    lights = [0]*m
    onoff = [0]*n
    for j in range(n):
        if (i >> j) &  1:
            onoff[j] = 1
    for k in range(m):
        cnt = 0
        for l in s[k][1:]:
            if onoff[l-1] == 1:
                cnt += 1
        if cnt % 2 == p[k]:
            lights[k] = 1
    if all(g == 1 for g in lights):
        ans += 1
print(ans)

Solution (Python):
def main():
	N, M = [int(n) for n in input().split(" ")]
	lights_def = [[0] * (N + 1) for i in range(M)]
	
	
	for i in range(M):
		tmp = [int(t) for t in input().split(" ")]
		for j in tmp[1:]:
			lights_def[i][j] = 1
	p = [int(x) for x in input().split(" ")]
	for i in range(len(p)):
		lights_def[i][0] = p[i]

	cnt = 0
	for i in range(2 ** N):
		switch_bit = list(pad_zero(format(i, 'b'), N))
		for j in range(len(lights_def)):
			light = lights_def[j]
			if sum([light[k + 1] for k in range(len(switch_bit)) if switch_bit[k] == "1"]) % 2 != light[0]:
				break
		else:
			cnt += 1

	print(cnt)

def pad_zero(s, n):
	s = str(s)
	return (("0" * n) + s)[-n:]

main()

Solution (Python):




import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2 2
2 1 2
1 2
0 1"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2 3
2 1 2
1 1
1 2
0 0 1"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5 2
3 1 2 5
2 2 3
1 0"""
        output = """8"""
        self.assertIO(input, output)


def resolve():
    N, M = map(int, input().split())
    S = [list(map(int, input().split())) for _ in range(M)]
    P = list(map(int, input().split()))

    ans = 0
    for bit in range(1 << N):
        m = 0
        for i in range(M):
            t = 0
            for j in range(1, S[i][0]+1):
                if bit & (1 << (S[i][j]-1)):
                    t += 1
            if t % 2 != P[i]:
                break
            else:
                m += 1
        if m == M:
            ans += 1
    print(ans)


if __name__ == "__main__":
    
    resolve()

Solution (Python):




import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2 2
2 1 2
1 2
0 1"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2 3
2 1 2
1 1
1 2
0 0 1"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5 2
3 1 2 5
2 2 3
1 0"""
        output = """8"""
        self.assertIO(input, output)


def resolve():
    N, M = map(int, input().split())
    S = [list(map(int, input().split())) for _ in range(M)]
    P = list(map(int, input().split()))

    ans = 0
    for bit in range(1 << N):
        m = 0
        for i in range(M):
            t = 0
            for j in range(1, S[i][0]+1):
                if bit & (1 << (S[i][j]-1)) != 0:
                    t += 1
            if t % 2 != P[i]:
                break
            else:
                m += 1
        if m == M:
            ans += 1
    print(ans)


if __name__ == "__main__":
    
    resolve()

Solution (Python):
def is_all_on(on_switches):
    on_cnt = 0
    for i in range(M):
        cnt = 0
        for on in on_switches:
            if on in lights[i]: 
                cnt += 1
        if cnt % 2 == P[i]:        
            on_cnt += 1
    return True if on_cnt == M else False        
            
N,M = map(int,input().split())
lights = []
for m in range(M):
    lights.append(list(map(lambda x:int(x) - 1,input().split()))[1:])
P = list(map(int,input().split()))


ans = 0
for i in range(1 << N): 
    on_switches = []
    for j in range(N): 
        if ((i >> j) & 1) == 1: 
            on_switches.append(j) 
    if is_all_on(on_switches): 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
for i in range(1<<N):
  judge=1
  for j in range(M):
    cnt=0
    for k in KS[j][1:]:
      if i>>(k-1)&1:
        cnt+=1
    if (cnt%2)!=p[j]:
      judge=0
  if judge==1:
    ans+=1
print(ans)

Solution (Python):
N, M = map(int, input().split())
k = []*M
s = []*M
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()))

ans = 0
for i in range(0,2**N):
    n = format(i,'010b')
    for j in range(M):
        pj = 0
        for k in range(len(s[j])):
            pj += int(n[10-s[j][k]])
        if p[j] != pj%2:
            break
        if j == M-1:
            ans += 1

print(ans)

Solution (Python):
import itertools

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

lis=[]

for _ in range(m):
  lis.append(list(map(int,input().split())))

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

ans=0
for binary in itertools.product([0,1],repeat=n):
  check=0
  for i in range(m):
    numon=0
    ki=lis[i][0]
    for j in range(ki):
      numon+=binary[lis[i][j+1]-1]
    if (numon+p[i])%2!=0:
      check+=1
  if check==0:
    ans+=1

print(ans)

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip.split())
def main():
    n,m = LI()
    s = [[] for i in range(n)]
    ans = 0
    for i in range(1,m+1):
        lst = LI()
        for j in lst[1:]:
            s[j-1].append(i)
    p = [0] + LI()
    
    bits = itertools.product([0,1],repeat=n)
    for bit in bits:
        lst = [0 for _ in range(m+1)]
        for i in range(n):
            if bit[i] == 1:
                for j in s[i]:
                    lst[j] = not lst[j]
        if lst == p:
            ans+= 1
    print(ans)
main()

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

import itertools
l=[]
a=itertools.product(range(2),repeat=n)
for i in a:
  l.append(i)

ans=0
for i in range(2**n):
  ok=[]
  for j in range(m):
    on=0
    for t in range(1,s[j][0]+1):
      e=s[j][t]
      if l[i][e-1]==1:
        on+=1
    if on%2!=p[j]:
      ok.append(False)
  if False not in ok:
    ans+=1

print(ans)

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





sw2 = []
for i in range (1 << n):
    
    sw =  []
    for j in range(m):
        
        cnt = 0
        for k in range(1, len(s[j])):
            if i >> (s[j][k] - 1) & 1 == 1:
                cnt += 1
            else:
                cnt += 0
            
        sw.append(cnt)
        
    sw2.append(sw)


ans2 = 0
for j in range(len(sw2)):
    ans = 0
    for k in range(len(sw2[j])):
        if sw2[j][k] % 2 == p[k]:
            ans += 1
    if ans == len(sw2[j]):
        ans2 += 1

print(ans2)

Solution (Python):
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
def end_of_loop():raise StopIteration
    
    
def main():
    N, M = MI()
    Switch = [LI() for i in range(M)]
    P = LI()
    result = 0
    for i in range(2**N):
        result += 1
        for index, swich in enumerate(Switch):
            if swich[0] == 0:
                continue
            temp = 0
            for j in range(swich[0]):
                if i >> (swich[j+1]-1) & 1 == 1:
                    temp += 1
            if temp % 2 != P[index]:
                result-=1
                break
            
    print(result)
                    
                    
            
            
        
if __name__ == "__main__":
    main()

Solution (Python):
n, m = map(int,input().split())
s = list(list(map(int, input().split())) for _ in range(m)) 
p = list(map(int,input().split()))
ans = 0
for i in range(1<<n):
    
    sw = [False]*m
    
    for j in range(m):
        
        cnt = 0
        for k in range(1,len(s[j])):
            if i>>s[j][k]-1&1:
                cnt += 1
        if cnt%2==p[j]:
            sw[j]=True
    if all(sw):
        ans+=1
print(ans)

Solution (Python):
n,m=map(int,input().split())
comb = []
for _ in range(m):
    comb.append(list(map(int,input().split()))[1:])
point = list(map(int,input().split()))
ans = 0
for i in range(2**n): 
    on = [0]*m
    for j in range(n): 
        if (i>>j)&1: 
            for k in range(m): 
                if j+1 in comb[k]: 
                    on[k] += 1 
                    on[k] %= 2 
    if point==on: 
        ans += 1 
print(ans)

Solution (Python):
n,m=map(int,input().split())
comb = []
for _ in range(m):
    comb.append(list(map(int,input().split()))[1:])
point = list(map(int,input().split()))
ans = 0
for i in range(2**n): 
    on = [0]*m
    for j in range(n): 
        if (i>>j)&1: 
            for k in range(m): 
                if j+1 in comb[k]: 
                    on[k] += 1 
                    on[k] %= 2 
    if all(point[l]==on[l] for l in range(m)): 
        ans += 1 
print(ans)

Solution (Python):
n,m=list(map(int,input().split()))
k=[]
s=[]

def cntbin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count

for i in range(m):
    kk,*ss=list(map(int,input().split()))
    k.append(kk)
    s.append(ss)

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

ans=0
for i in range(2**n):
    ok=True
    for mm in range(m):
        if not ok:break
        mask=0
        for ss in s[mm]:
            mask+=1 << ss-1
        on=cntbin(i&mask)
        if p[mm]!=on%2:
            ok=False

    if ok:ans+=1

print(ans)

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

On = [True for i in range(N)]
K = [0 for j in range(M)]
S = []

for j in range(M):
  inp = list(map(int, input().split(' ')))
  K[j] = inp[0]
  S.append(inp[1:])
  
P = list(map(int, input().split(' ')))


def check_condition(On, K, S, P):
  for j in range(len(K)):
    on_sum = 0
    for k in range(K[j]):
      if On[S[j][k]-1]: on_sum += 1
    if on_sum%2 != P[j]:
      return False
  return True

def enum_patterns(On, index, K, S, P):
  off = On.copy()
  off[index] = False
  if index == len(On)-1:
    count = check_condition(On, K, S, P) + check_condition(off, K, S, P)
  else:
    count = enum_patterns(On, index+1, K, S, P) + enum_patterns(off, index+1, K, S, P)
  return count


print(enum_patterns(On, 0, K, S, P))

Solution (Python):


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N, M = list(map(int, input().split()))
    k, s = [], []
    for m in range(M):
        l = list(map(int, input().split()))
        k.append(l[0])
        s.append(l[1:])
    p = list(map(int, input().split()))

    return N, M, k, s, p


def main(N: int, M: int, s: list, p: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): スイッチの数(1 <= N <= 10)
        M (int): 電球の数(1 <= M <= 10)
        s (list): 電球と繋がっているスイッチ(1 <= s_ij <= N)
        p (list): 点灯判定(0または1)
    """
    
    ans = 0
    for bit in range(1 << N):
        is_all_light_on = True
        for m in range(M):
            on_count = 0
            for s_i in s[m]:
                if ((bit >> (s_i - 1)) & 1):
                    on_count += 1
            if on_count % 2 != p[m]:
                is_all_light_on = False
                break
        if is_all_light_on:
            ans += 1

    
    print(ans)


if __name__ == "__main__":
    
    N, M, k, s, p = get_input()

    
    main(N, M, s, p)

Solution (Python):


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


ans = 0
for bit in range(1 << N):
    is_light_on = True
    for m in range(M):
        on_count = 0
        for s_i in s[m]:
            if ((bit >> (s_i - 1)) & 1):
                on_count += 1
        if on_count % 2 != p[m]:
            is_light_on = False
            break
    if is_light_on:
        ans += 1


print(ans)

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

for i in range(1<<N):
    onoff = bin(i)[2:].zfill(N)
    for j, switches in enumerate(lights):
        if sum(onoff[s-1] == '1' for s in switches[1:]) % 2 != p[j]:
            break
    else:
        ans += 1

print(ans)

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

for i in range(1<<N):
    for j,lst in enumerate(connected):
        count = 0
        for s in lst[1:]:
            if (i>>(s-1)) & 1:
                count += 1
        if count % 2 != p[j]:
            break
    else:
        ans += 1

print(ans)

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

for i in range(1<<N):
    on = 0
    onoff = bin(i)[2:].zfill(N)
    for j, switches in enumerate(lights):
        if sum(onoff[s-1] == '1' for s in switches[1:]) % 2 == p[j]:
            on += 1
    if on == M:
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
A = []
for _ in range(M):
    A.append(tuple(map(int, input().split())))
P = tuple(map(int, input().split()))
import itertools
def hantei(A, RETU, P):
    for i in range(len(A)):
        count = 0
        for k in RETU:
            if k in A[i][1:]:
                count += 1
        if not count % 2 == P[i]:
            return False
    return True
ans = 0
for i in range(1, N + 1):
    for k in itertools.combinations(range(1, N + 1), i):
        if hantei(A, k, P):
            ans += 1
if hantei(A, [0], P):
    ans += 1
print(ans)

Solution (Python):
n, m = list(map(int, input().split()))
k = []

for i in range(m):
    ki = list(map(int, input().split()))
    s = [0] * n
    for j in range(1, len(ki)):
        s[ki[j]-1] = 1

    k.append(int("".join(map(str, s)), 2))

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

def count1s(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n >>= 1

    return cnt

cnt = 0
for i in range(2**n):
    sol = True
    for j in range(m):
        if count1s(i & k[j]) % 2 == p[j]:
            pass
        else:
            sol = False
            break

    if sol:
        cnt += 1

print(cnt)

Solution (Python):
from itertools import product

n, m = map(int, input().split())
sp = [list(map(int, input().split())) for _ in range(m + 1)]
print(sum(all(sum(i[a - 1] for a in s[1:]) % 2 == p for s, p in zip(sp[:m], sp[-1])) for i in product((0, 1), repeat=n)))

Solution (Python):
from itertools import product

n, m = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
print(sum(all(sum(i[b - 1] for b in a[1:]) % 2 == x for a, x in zip(s, p)) for i in product((0, 1), repeat=n)))