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

Solution (Python):
N, M = map(int, input().split())
S = [[int(i) for i in input().split()] for j in range(M)]
p = [int(i) for i in input().split()]
ans = 0

for i in range(2 ** N):
  T = [0] * N
  for j in range(N):
    if ((i >> j) & 1):
      T[j] += 1

  s = 0
  for j in range(M):
    pp = 0
    for k in range(S[j][0]):
      pp += T[S[j][k+1]-1]
    if pp % 2 == p[j]:
      s += 1
      
  if s == M:
    
    ans += 1
print(ans)

Solution (Python):
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,M = map(int, input().split())
    RAMPS = [0]*M
    for i in range(M):
        tmp = list(map(int, input().split()))
        RAMPS[i] = [x-1 for x in tmp[1:]]
    PS = list(map(int, input().split()))
    ans = 0
    for bit in range(2**N):
        for i in range(M):
            cnt = 0
            for j in RAMPS[i]:
                if 1<<j & bit != 0: cnt += 1
            if cnt%2 != PS[i]:
                break
        else:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
count = 0
for i in range(2 ** n):
    check = True
    bin_str = format(i, 'b').rjust(n + 1, "0")
    for j in range(m):
        light = 0
        for k in range(1, len(l[j])):
            if bin_str[l[j][k]] == "1":
                light += 1
        if not (light % 2 == p[j]):
            check = False
    if check:
        count += 1
print(count)

Solution (Python):
from itertools import product
N,M=map(int,input().split())
A=[]
for _ in range(M):
    A.append(list(map(int,input().split()))[1:])
P=list(map(int,input().split()))

ans=0

for st in product([0,1],repeat=N):
    f=True
    for i in range(M):
        k=0
        for j in A[i]:
            k+=st[j-1]
        f= k%2==P[i]
        if not f:
            break
    if f:
        ans+=1

print(ans)

Solution (Python):
if __name__ == "__main__":
    N, M = map(int, input().split())
    ksl = list()
    for _ in range(M):
        ksl.append(list(map(int, input().split())))
    p = list(map(int, input().split()))

    ans = 0
    for i in range(2 ** N):
        flag = str(format(i, 'b').zfill(N))
        flag = flag[::-1]
        is_Lightup = True
        for j in range(M):
            count = 0
            for k in range(ksl[j][0]):
                count += int(flag[ksl[j][k+1] - 1])
            if count % 2 != p[j]:
                is_Lightup = False
                break
        if is_Lightup:
            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
tmp = 0
for i in range(2**N):
    Judge = True
    for j in range(0,M):
        tmp = 0
        for k in range(1,KS[j][0]+1):
            if i >> (KS[j][k]-1) & 1 == 1:
                tmp += 1
        if tmp%2 != P[j]:
            Judge = False
    if Judge:
        ans += 1
print(ans)

Solution (Python):
from itertools import product

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

bulb = {}
for i in range(1, m+1):
    k_s = list(map(int, input().split()))
    bulb[i] = k_s[1:]

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

count = 0
for item in product([0, 1], repeat=n):
    on = [ind+1 for ind, status in enumerate(item) if status]
    for k, v in bulb.items():
        if p[k-1] != len(set(v).intersection(set(on))) % 2:
            break
    else:
        count += 1

print(count)

Solution (Python):
from itertools import product

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

ans = 0

for state in product([0,1],repeat=N):
  f = True
  for i in range(M):
    tmp = 0
    for s in sw[i]:
      tmp += state[s-1]
    f = tmp % 2 == p[i]
    if not f:
      break
  if f:
    ans += 1
print(ans)

Solution (Python):
N, M = map(int,input().split(' '))
S=[]
for i in range(M):
    tmpk=list(map(int,input().split(' ')))
    S.append(tmpk[1:])
P=list(map(int,input().split(' ')))

Slist=[]
for i in range(pow(2,N)):
    
    Slist.append(format(i,'0'+str(N)+'b'))


ans = 0
for onoff in Slist:
    cnt=0
    for i in range(len(S)):
        tmp=0
        for chk in S[i]:
            
            if onoff[chk-1]=='1':
                tmp+=1
        if tmp%2 == P[i]:
            cnt+=1
    if cnt == M:
        ans+=1
print(ans)

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

def hoge(s,N,ans):
    if sum(s)==N:
        print(ans)
        exit(0)
    for i in range(N-1,-1,-1):
        if s[i]==0:
            s[i]=1
            break
        else:
            s[i]=0
    return s

for i in range(2**N):
    for i in range(M):
        tmp=0
        for k in li[i][1::]:
            if s[k-1]==1:
                tmp+=1
        if tmp%2!=p[i]:
            break
    else:
        ans+=1
    s=hoge(s,N,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=0
for i in range(2**N):
  
  p=[]
  for s in S:
    tmp=0
    for ss in s:
      if i>>(N-ss)&1:
        tmp+=1
    p.append(tmp%2)
  if p==P:
    ans+=1
print(ans)

Solution (Python):
N, M = map(int,input().split())
S = [0] * M
k = [0] * M
for i in range(M):
    KS = list(map(int,input().split()))
    k[i] = KS[0]
    S[i] = KS[1:] 
P = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    global_count = 0
    for j in range(M):
        local_count = 0
        for x in S[j]:
            if (i >> (x-1)) % 2 == 0:
                continue
            else:
                local_count += 1
        if local_count % 2 == P[j]:
            global_count += 1
    if global_count == M:
        ans += 1

print(ans)

Solution (Python):
import itertools as it

N, M = list(map(int, input().split()))
s = []
for i in range(M):
    s_i = [int(a) for a in input().split()]
    s.append(s_i[1:])
p = [int(a) for a in input().split()]
ans = 0
for i in it.product(range(2), repeat=N):
    
    is_flash = []
    for j in range(M):
        
        cond = s[j]  
        num = 0
        for light in cond:
            num += i[light - 1]
        if num % 2 == p[j]:
            is_flash.append(True)
        else:
            is_flash.append(False)
    if all(is_flash):
        ans += 1
print(ans)

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

p = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    global_count = 0
    for j in range(M):
        local_count = 0
        for x in s[j]:
            if (i >> (x - 1)) % 2 == 0:
                continue
            else:
                local_count += 1
        if local_count % 2 == p[j]:
            global_count += 1
    if global_count == M:
        ans += 1

print(ans)

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

ans = 0
for i in range(1<<N):
  for j in range(M):
    rel=0
    for k in swis[j]:
      if i & (1<<(k-1)) != 0:
        rel+=1
        
    if rel%2 != need[j]:
        break
  else:
     ans+=1
      
print(ans)

Solution (Python):
N, M = map(int,input().split(' '))
S=[]
for i in range(M):
    tmpk=list(map(int,input().split(' ')))
    S.append(tmpk[1:])
P=list(map(int,input().split(' ')))

Slist=[]
for i in range(pow(2,N)):
    
    Slist.append(format(i,'0'+str(N)+'b'))


ans = 0
for onoff in Slist:
    cnt=0
    for i in range(len(S)):
        tmp=0
        for chk in S[i]:
            
            if onoff[chk-1]=='1':
                tmp+=1
        if tmp%2 == P[i]:
            cnt+=1
    if cnt == M:
        ans+=1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 9)
N, M = map(int, input().split())

switches = []
for i in range(M):
    temp = list(map(int, input().split()))
    temp = [val-1 for val in temp]
    switches.append(set(temp[1:]))

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

def dfs(s):
    if len(s) == N:
        on = set([])
        for i, num in enumerate(s):
            if num == "1":
                on.add(i)

        for switch, p in zip(switches, ps):
            common = switch & on
            if len(common) % 2 != p:
                return 0
                break
        else:
            return 1
    else:
        return dfs(s + "0") + dfs(s + "1")

ans = dfs("")
print(ans)

Solution (Python):
N,M = map(int,input().split())
target = [[num-1 for num in list(map(int,input().split()))[1:]] for _ in range(M)]
judge = list(map(int,input().split()))
cnt = 0

for i in range(2**N):
  switches = [0]*M
  for k in range(M):
    for j in range(N):
      if ((i>>j)&1) and j in target[k]:
        switches[k] += 1
  switches =  [switch%2 for switch in switches]
  if switches == judge:
    cnt += 1
print(cnt)

Solution (Python):


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

res=0
for i in range(2**n):
    flag=True
    for j in range(m):
        cnt=0
        for e in s[j]:
            if i>>e&1:
                cnt+=1

        if cnt%2!=p[j]:
            flag=False
            break
    if flag:res+=1
print(res)

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


def main():
    N, M = map(int, input().split())
    K = []
    S = [[False]*N for _ in range(M)]
    for i in range(M):
        L = list(map(int, input().split()))
        K.append(L[:1])
        for l in L[1:]:
            S[i][l-1] = True
    P = list(map(int, input().split()))
    
    

    ans = 0
    for i in range(2**N):
        C = [0]*M
        for j in range(N):
            if (i>>j) & 1:
                for k in range(M):
                    if S[k][j]:
                        C[k] += 1
        flg = True
        for j in range(M):
            if C[j]%2!=P[j]:
                flg = False
        if flg:
            ans += 1
        
    
    print(ans)


if __name__ == '__main__':
    main()

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

l=[[int(x) for x in input().split()] for _ in range(m)]
p=[int(x) for x in input().split()]

t=0
for i in range(2**n):
  f = True
  for j in range(m):
     c=0
     for k in range(1,l[j][0]+1):
       if (i>>(l[j][k]-1)) & 1:
         c+=1
     if (c&1)!=p[j]:
        f = False
        break
  if f==True:
    t+=1

print(t)

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

a = [0] * N


for i in range(M):
    l = list(map(int, input().split()))
    k = l[0]
    S = l[1:]
    for j in range(k):
        s = S[j]
        s -= 1
        
        a[s] |= 1 << i

p = 0
l = list(map(int, input().split()))
for i in range(M):
    p |= l[i] << i

ans = 0

for s in range(1 << N):
    t = 0
    for i in range(N):
        
        if s >> i & 1:
            
            t ^= a[i]
    
    if t == p:
        ans += 1

print(ans)

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

a = [0] * N


for i in range(M):
    l = list(map(int, input().split()))
    k = l[0]
    S = l[1:]
    for j in range(k):
        s = S[j]
        s -= 1
        
        a[s] |= 1 << i

p = 0
l = list(map(int, input().split()))
for i in range(M):
    p |= l[i] << i

ans = 0

for s in range(1 << N):
    t = 0
    for i in range(N):
        
        if s >> i & 1:
            t ^= a[i]
    if t == p:
        ans += 1

print(ans)

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

ans = 0
for i in range(2**N):
    status = [0] * N
    for j in range(N):
        if i >> j & 1:
            status[N - 1 - j] = 1

    possible = True
    for j in range(M):
        cnt_sw = sum(1 if status[k-1] == 1 else 0 for k in KS[j][1:])
        if cnt_sw%2 != P[j]:
            possible = False
    if possible:
        ans += 1
    
print(ans)

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):
    i = format(i, "b").zfill(n)
    for j in range(len(s)):
        tmp = 0
        for k in s[j][1:]:
            tmp += int(i[k - 1])
		
        if p[j] != tmp % 2:
            break
        if j == len(s) - 1:
            ans += 1

print(ans)

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):
    i = format(i, "b").zfill(n)
    for j in range(len(s)):
        tmp = 0
        for k in s[j][1:]:
            tmp += int(i[k - 1])
		
        if p[j] != tmp % 2:
            break
        if j == len(s) - 1:
            ans += 1

print(ans)

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):
    i = format(i, "b").zfill(n)
    for j in range(len(s)):
        tmp = 0
        for k in s[j][1:]:
            tmp += int(i[k - 1])

        if p[j] != tmp % 2:
            break
        if j == len(s) - 1:
            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()))

s_cands = [[]]
for i in range(1, n+1):
  temp = []
  for cand in s_cands:
    temp.append(cand + [i])
    temp.append(cand)
  s_cands = temp

correct_pat = 0
for light_pat in s_cands:
  for i, s in enumerate(S):
    swicth_on = len(list(set(light_pat) & set(s)))
    if swicth_on % 2 != P[i]:
      break
  else:
    correct_pat += 1
print(correct_pat)

Solution (Python):
n, m = map(int,input().split())
grid = []
for i in range(m):
    array = list(map(int, input().strip().split(' ')))
    grid.append(array)
plist = list(map(int, input().split()))


checklist = [ [int((format(i, 'b').zfill(n))[j]) for j in range(n)] for i in range(2**n)]
answer = 0

for i in range(2**n):
    light = checklist[i]
    cpoint = 0
    for j in range(m):
        switches = grid[j][1:]
        point = 0
        for k in range(len(switches)):
            point += light[switches[k]-1]
        if point % 2 == plist[j]:
            cpoint += 1
    if cpoint == m:
        answer += 1

print(answer)

Solution (Python):

n,m=map(int,input().split())
ks=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
data=[0 for i in range(n+1)]
s=0
for i in range(2**n):
    for j in range(n):
        if (i>>j&1)==1:
            data[j+1]=1
        else:
            data[j+1]=0
    for k in range(m):
        a=0
        for l in range(1,ks[k][0]+1):
            a=(a+data[ks[k][l]])%2
        if a!=p[k]:
            break
    else:
        s+=1
print(s)

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


def main():
    N, M = [int(x) for x in input().split()]
    k = []
    s = [[] for _ in range(M)]
    for i in range(M):
        A = [int(x) for x in input().split()]
        k.append(A[0])
        s[i].extend(A[1:])

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

    ans = 0
    for i in range(2 ** N):
        switch = bin(i)
        switch = switch[2:]
        switch_len = len(switch)
        switch = '0' * (N - switch_len + 1) + switch
        for j in range(M):
            total = 0
            for l in s[j]:
                total += int(switch[l])
            if total % 2 != p[j]:
                break
            if j == M - 1:
                ans += 1

    print(ans)




if __name__ == '__main__':
    main()

Solution (Python):
n,m = map(int,input().split())
a=[]
for _ in range(m):
    a.append(list(map(int,input().split())))
    a[-1].pop(0)
p = list(map(int,input().split()))
res = 0

for i in range(0,2**n):
    flag = 0
    bis = bin(i)
    bi = bis[2:]
    bi = '0' * (n-len(bi)) + bi
    for k in range(0,len(a)):
        sumk = 0
        for j in range(0,len(a[k])):
            sumk += int(bi[a[k][j]-1])
        if sumk %2 == p[k]:
            flag += 1
    if flag == len(a):
        res += 1

print(res)

Solution (Python):
n,m = map(int,input().split())
time = [0 for _ in range(n)]
def nex(time):
  for i in range(n):
    if time[i] == 0:
      time[i] += 1
      break
    else:
      time[i] = 0
  else:
    time = 'over'
  return time
s = []
for _ in range(m):
  raw = list(map(int,input().split()))
  add = [0 for _ in range(n)]
  for j in range(1,raw[0]+1):
    add[raw[j]-1] = 1
  s.append(add)
p = list(map(int,input().split()))
ans = 0
while time != 'over':
  for k in range(m):
    tmp = p[k]
    for i in range(n):
      tmp ^= time[i] * s[k][i]
    if tmp == 1:
      break
  else:
    ans += 1
  time = nex(time)
print(ans)

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

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

def check(state):
    is_ok = True
    for connect,p in zip(connects, P):
        switch_count = 0
        for switch in connect:
            shift = switch - 1
            switch_bit = 1<<shift
            if (switch_bit & state) > 0:
                switch_count +=1

        if switch_count % 2 != p:
            is_ok = False
            break

    return is_ok


full_state = 2**N

count = 0
for state in range(full_state):
    if check(state):
        count += 1


print(count)

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

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

for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if (i>>j)&1:
            switch[j] = 1
    flag = 0
    for j in range(m):
        count = 0

        for k in range(len(ks[j])-1):
            if switch[ks[j][k+1]-1]==1:
                count+=1
        
        if not count%2 ==p[j]:
            flag = 1
    
    if flag == 0:
        ans +=1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,m=map(int,input().split())
    switch=[0]*n
    for i in reversed(range(m)):
        k,*S=map(int,input().split())
        for s in S:
            switch[s-1]+=1<<i
    p=int(input().replace(' ',''),2)
    
    ans=0
    for k in range(2**n):
        xor=0
        for i in range(n):
            if k&(1<<i):
                xor^=switch[i]
        if xor==p: ans+=1
    print(ans)
resolve()

Solution (Python):
def slove():
    import sys
    import itertools
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    ks = [list(map(int, input().rstrip('\n').split())) for _ in range(m)]
    p = list(map(int, input().rstrip('\n').split()))
    ls = [True, False]
    cnt = 0
    for it in itertools.product(ls, repeat=n):
        b = True
        for j, v in enumerate(ks):
            tc = 0
            for i in range(len(v)):
                if i != 0:
                    if not it[v[i]-1]:
                        tc += 1
            if tc % 2 != p[j]:
                b = False
        if b:
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    slove()

Solution (Python):
import itertools

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

for i in ks:
	i.pop(0)
	
ans=0

for light in itertools.product([0,1], repeat=N):
	ok=True
	for _index, _list in enumerate(ks):
		_sum=0
		for s in _list:
			_sum += light[s-1]
		if _sum%2 != p[_index]:
			ok=False
			break
	if ok is True:
		ans+=1

print(ans)

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

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

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

ans = 0
switch_pattern_num = 2**N

for i in range(switch_pattern_num):
    binary = format(i,'0%ib'%N)
    satisfied = True
    for j,S in enumerate(Ss):
        count = 0
        for e in S:
            if int(binary[e-1]):
                count += 1
        if count % 2 != Ps[j]:
            satisfied = False
    if satisfied:
        ans += 1
print(ans)

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

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

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

ans=0
for i in range(2**n):
  tmp=0
  f=1
  for mm in range(m):
    tmp=0
    for j in info[mm][1:]:
      tmp+=int(str(format(i,'b').zfill(n))[int(j)-1])
    if tmp%2!=p[mm]:
      f=0
  if f==1:
    ans+=1
print(ans)

Solution (Python):
n, m = map(int, input().split())
s = [set()] * m
for i in range(m):
    s[i] = set(list(map(lambda x: int(x)-1, input().split()))[1:])
p = list(map(int, input().split()))

ans = 0

for i in range(2 ** n):
    lights = set()
    for j in range(n):
        if ((i >> j) & 1):
            lights.add(j)
    
    for j in range(m):
        if len(s[j] & lights) % 2 != p[j]: break
    else: ans += 1

print(ans)

Solution (Python):
n, m = map(int, input().split())
arr = []
for i in range(m):
    arr.append(list(map(int, input().split())))
arr = [[0] + list(map(int, input().split()))] + arr
ans = 0
for i in range(2**n):
    light = []
    for j in range(n):
        light.append(i >> j & 1)
    cnt = 0
    for k in range(1, m+1):
        judge = 0
        for s in range(1, len(arr[k])):
            judge += light[arr[k][s]-1]
        judge %= 2
        if judge == arr[0][k]:
            cnt += 1
    if cnt == m:
        ans += 1
print(ans)

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

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

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


def binary_ume(N,K):  
    A = []
    while N >= 2:
        A.append(N%2)
        N = N//2
    A.append(N)
    while len(A) < K:
        A.append(0)
    return A

ans = 0

for i in range(m):
    for j in range(1,len(k[i])):
        k[i][j] -= 1

for i in range(2**n):
    switch = binary_ume(i,n)  
    all_on = 1  
    for j in range(m):
        if sum(switch[l] for l in k[j][1:])%2 != p[j]:
            all_on = 0
            break
    if all_on == 1:
        ans += 1

print(ans)

Solution (Python):


N,M=map(int,input().split())
l=[]*M

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

count=0
s=[-1]*10

for i in range(2):
    s[0]=i
    for ii in range(2):
        s[1]=ii
        for iii in range(2):
            s[2]=iii
            for iiii in range(2):
                s[3]=iiii
                for iiiii in range(2):
                    s[4]=iiiii
                    for iiiiii in range(2):
                        s[5]=iiiiii
                        for iiiiiii in range(2):
                            s[6]=iiiiiii
                            for iiiiiiii in range(2):
                                s[7]=iiiiiiii
                                for iiiiiiiii in range(2):
                                    s[8]=iiiiiiiii
                                    for iiiiiiiiii in range(2):
                                        s[9]=iiiiiiiiii
                                        
                                        for j in range(M):
                                            sum=0
                                            is_success=True
                                            for item in l[j]:
                                                sum=sum^s[item-1]
                                            if sum!=p[j]:
                                                is_success=False
                                                break
                                        if is_success:
                                            count+=1
                                            
print(int(count/2**(10-N)))

Solution (Python):
import numpy as np

def test():
    n,m = map(int,input().split())
    s = []
    count = 0
    for i in range(m):
        a = list(map(int,input().split()))
        s.append(a[1:])
    p = np.array(list(map(int,input().split())))

    for i in range(2**n):
        result = np.array([(i>>j)&1 for j in range(n)])
        if all(p == [sum(result[np.array(i)-1])%2 for i in s]):
            count += 1
    print(count)


if __name__ == "__main__":
    test()

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

s = []
k = []
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()))


def check_switch(ss):
    for i in range(m):
        sum_switch = 0
        for j in range(k[i]):
            sum_switch += ss[s[i][j] - 1]
        if sum_switch % 2 != p[i]:
            return 0
    return 1


def check(switches, l):
    if l == n:
        return check_switch(switches)
    return check(switches+[0], l + 1) + check(switches+[1], l + 1)


print(check([], 0))

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

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

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

def checkMod(binStr,swStr,p):
  return 1 if bin(binStr & swStr).count("1")%2==p else 0

result=0

for i in range(2**n):
  count=1
  for j in range(m):
    count=count*checkMod(i,k[j],p[j])
    if count==0:
      break
  if count==1:
    result+=1

print(result)

Solution (Python):
def main(): 
    
    switch_cnt,bulb_cnt = map(int, input().split())

    k = [list(map(int, input().split())) for _ in range(bulb_cnt)]

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

    cnt = 0
    for i in range(2 ** switch_cnt):

        switch_status = [False for _ in range(switch_cnt)]

        j = 0
        while i > 0b0:
            if i & 0b1 == 0b1:
                switch_status[j] = True
            i = i >> 1
            j += 1

        for ki in range(len(k)):
            on_count = 0
            for kj in range(1,len(k[ki])):
                switch_no = k[ki][kj] - 1
                if switch_status[switch_no]:
                    on_count += 1
            if on_count % 2 != p[ki]:
                break
        else:
            cnt += 1
    print(cnt)          


if __name__ == "__main__":
    main()

Solution (Python):

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


k=[]
for _ in range(m):
  temp = list(map(int,input().split()))[1:]
  inp=0
  for i in temp:
    inp+=2**(i-1)
  k.append(inp)


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






def checkMod(binStr,swStr,p):
  
  
  if bin(binStr & swStr).count("1")%2==p:
    return 1
  else:
    return 0
  

  
result=0

for i in range(2**n):
  count=1
  for j in range(m):
    count=count*checkMod(i,k[j],p[j])
    if count==0:
      break
  if count==1:
    result+=1

print(result)

Solution (Python):
def f_c():
    n, m = map(int, input().split())
    l = []
    for _ in range(m):
        _, *s = map(lambda x: int(x)-1, input().split())
        sb = 0
        for si in s:
            sb |= 1<<si
        l.append(sb)
    *p, = map(int, input().split())

    a, c = 0, 0
    for i in range(1<<n):
        for j, sb in enumerate(l):
            if bin(i&sb).count("1")%2!=p[j]:
                break
            else:
                c += 1
        a = a+1 if c==m else a
        c = 0
    print(a)

if __name__ == "__main__":
    f_c()

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()))
result = 0
for switches in product((0, 1), repeat=N):
    for s, p in zip(S, P):
        num = sum([switches[s_ - 1] for s_ in s[1:]])
        if num % 2 != p:
            break
    else:
        result += 1
print(result)

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):
  on=[0 for _ in range(n)]
  tmp=i
  for j in range(n):
    if tmp%2==1:
      on[j]=1
    tmp//=2
  flag=True
  for j in range(m):
    cnt=0
    for k in range(1,S[j][0]+1):
      cnt+=on[S[j][k]-1]
    if cnt%2!=P[j]:
      flag=False
      break
  if flag:
    ans+=1
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


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

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

count = 0
for i in range(2 ** N):
    switchs = []
    for j in range(N):
        if ((i >> j) & 1):
            
            switchs.append(1)
        else:
            
            switchs.append(0)

    
    switchs = [0] + switchs
    is_on = True
    for x in range(len(KS)):
        k, *s = KS[x]
        
        on = 0
        for z in s:
            if switchs[z] == 1:
                on += 1

        if on % 2 == P[x]:
            pass
        else:
            is_on = False

    if is_on:
        count += 1

print(count)