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



pos=[None]*N
pattern=0

def check(pos):
    
    count=0
    for i in range(M):
        temp=0
        for j in range(1, len(ks[i])):
            temp+=pos[ks[i][j]-1]
        if temp%2==p[i]:
            
            count+=1
    
    if count==M:
        
        return 1
    else:
        return 0

def set(n):
    global pattern
    if n==N-1:
        for i in range(2):
            pos[n]=i
            pattern+=check(pos)
    else:
        for i in range(2):
            pos[n]=i
            set(n+1)
set(0)

print(pattern)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
from itertools import product
def I(): return [int(iI) for iI in input().split()]
n,m=I() ; a=[]
for i in range(m):
    a.append(I()[1:])
p=I()
l=[list(p) for p in product([0,1], repeat=n)]
ans=0
for i in l:
    flag=0
    for j in range(len(a)):
        s=0
        for k in a[j]:
            if i[k-1]==1: s+=1
        if s%2!=p[j]%2:
            flag=1
            break
    if flag==0:
        ans+=1
print(ans)

Solution (Python):
def mySum(L, indexs):
    result = 0
    for i in indexs:
        if (L >> i & 1):
            result += 1
    return result


N, M = map(int, input().split())
S = []
for _ in range(M):
    S.append(list(map(lambda a: int(a)-1, input().split()))[1:])
P = list(map(int, input().split()))
count = 0
for bi in range(1 << (N)):
    for i, s in enumerate(S):
        if P[i] != (mySum(bi, s)) % 2:
            break
    else:
        count += 1
print(count)

Solution (Python):
import math
import copy
from copy import deepcopy
import sys
import fractions

from functools import reduce

import decimal
import heapq
import collections
import itertools
from operator import mul

sys.setrecursionlimit(100001)







def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList




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

s = getSomeInputListInt(m)
p = getInputListInt()

s_bit = []

for tmp_s in s:
    tmp_bit = 0
    for i in range(1, tmp_s[0] + 1, 1):
        aaa = 1 << (tmp_s[i] - 1)
        tmp_bit = aaa | tmp_bit
    s_bit.append(tmp_bit)

ans = 0
for i in range(int(pow(2, n))):
    flg = True
    for j in range(m):
        cnt = bin(s_bit[j] & i).count("1")
        if cnt % 2 != p[j]:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Solution (Python):



def check_switch_on(S, btn, P):
    for i, s_row in enumerate(S):
        on_cnt = 0
        
        for s in s_row:
            if btn[s-1]:
                on_cnt += 1
        if P[i] != on_cnt % 2:
            return False
    return True


if __name__ == "__main__":
    N, M = map(int, input().split())

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

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

    cnt = 0
    for bit in range(1 << N):
        btn = [False] * N
        for i in range(N):
            if bit & (1 << i):
                btn[i] = True
        if check_switch_on(S, btn, P):
            
            cnt += 1

    print(cnt)

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

ans = 0
for bit in range(2 ** N):
    ons = set([i + 1 for i in range(N) if bit >> i & 1])
    flg = True
    for i in range(M):
        k, *s = X[i]
        p = P[i]
        flg &= len(set(s) & ons) % 2 == p
    ans += int(flg)
    
print(ans)

Solution (Python):
def main():
    from builtins import int, str, map, list, dict, float, print, len, sorted, max, min
    from itertools import accumulate, permutations, combinations
    from collections import deque, defaultdict, Counter
    from operator import itemgetter
    from bisect import bisect_left, bisect_right, bisect
    from heapq import heappop, heappush
    from fractions import gcd
    import sys, re, math, copy
    sys.setrecursionlimit(10 ** 6)

    input = sys.stdin.readline
    input_list = (lambda: input().rstrip().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    N, M = input_number_list()
    k = []
    s = []
    p = []
    for i in range(M):
        ls = input_number_list()
        k.append(ls[0])
        s.append(ls[1:])
    p = input_number_list()
    switch_max = 2 ** N
    ans = 0
    for i in range(switch_max):
        cnt_if = 0
        for j, switchs in enumerate(s):
            cnt = 0
            for sw in switchs:
                h = 1 << (sw - 1)
                if h & i:
                    cnt += 1
            if cnt % 2 == p[j]:
                cnt_if += 1
        if cnt_if == M:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

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


ans = 0
for i in range(2**n):
  ng = 0
  for j in range(m):
    ans_j = 0
    for k in range(n):
      if i >> k & 1 and k+1 in light[j][1:]:
        
        ans_j += 1
    
    if ans_j % 2 != p[j]:
      ng = 1
  if ng == 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()))
 
cnt = 0
 
for i in range(2 ** N):  
    flag = True
    for j in range(M): 
        if not([(i >> k-1) & 1  for k in s[j]].count(1) % 2 == p[j]):
            flag = False
    if flag:
        cnt += 1
 
print(cnt)

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

ans = 0
for n in range(2**N):
  
  alllight = True
  for pi, S in enumerate(Switch):
    mask = n
    swon = 0
    for i in range(N):
      if (mask >> i) & 1:
        if i+1 in S: swon += 1
    
    if swon % 2 != P[pi]:
      alllight = False
      break
  if alllight: 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(2 ** n):

    
    switches = [0] * n
    for j in range(n):
        if ((i >> j) & 1):
            switches[j] = 1
    
    
    lights = [0] * m
    for k in range(m):
        on_num = sum(map(lambda x: switches[x-1], S[k]))
        if on_num % 2 == P[k]:
            lights[k] = 1
    
    
    if all(light == 1 for light in lights):
        count += 1

print(count)

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(2 ** n):

    
    switches = [0] * n
    for j in range(n):
        if ((i >> j) & 1):
            switches[j] = 1
    
    
    lights = [0] * m
    for k in range(m):
        on_num = sum(map(lambda x: switches[x-1], S[k]))
        if on_num % 2 == P[k]:
            lights[k] = 1
    
    
    if all(light == 1 for light in lights):
        count += 1

print(count)

Solution (Python):
N, M = map(int, input().split())
s = []
for _ in range(M):
    kss = list(map(int, input().split()))
    s.append(set([x - 1 for x in kss[1:]]))
p = list(map(int, input().split()))

ans = 0
for bit in range(1 << N):
    on_counts = [0] * M
    for i in range(N):
        if bit & (1 << i):
            for m in range(M):
                if i in s[m]:
                    on_counts[m] += 1
    if [x % 2 for x in on_counts] == 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()))
cnt = 0
for i in range(2**n):
  cnt_on = [0 for i in range(m)]
  for j in range(n):
    if (i >> j) & 1:
      for k in range(m):
        g = ks[k][1:]
        for a in g:
          if a == j+1:
            cnt_on[k] += 1
  for l in range(m):
    if cnt_on[l]%2 != p[l]:
      break
    if l == m-1:
      cnt += 1
print(cnt)

Solution (Python):
from itertools import product
import numpy as np

N, M = map(int, input().split())
liS_all = []
denkyuM = [0 for i in range(M)]
cnt = 0

for j in range(1, M + 1):
    liS = list(map(int, input().split()))
    denkyulist = [0 for k in range(N)]
    for l in liS[1:]:
        denkyulist[l-1] = 1
    liS_all.append(denkyulist)

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

bit_list = list(product([0, 1], repeat = N))

for bit in bit_list:
    n = 0
    judge = True
    for denkyu in liS_all:
        ronriseki = np.logical_and(bit, denkyu)
        if sum(ronriseki) % 2 != liP[n]:
            judge = False
        n += 1
    if judge == True:
        cnt += 1
print(cnt)

Solution (Python):
from itertools import product

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

res = 0
for pattern in product((0, 1), repeat=n):
    for i in range(m):
        cnt = 0
        k, s = ks[i]
        for j in range(k):
            cnt += pattern[s[j] - 1]
        if cnt % 2 != p[i]:
            break
    else:
        res += 1

print(res)

Solution (Python):
n,m = map(int, input().split())
dic_s = {}
for i  in range(n):
    dic_s[i] = []
for i in range(m):
    a = list(map(int, input().split()[1:]))
    for num in a:
        dic_s[num-1].append(i)
p = list(map(int, input().split()))
total = 0

def judge_bright(judge):
    for i,num in enumerate(judge):
        if num%2 != p[i]:
            return False
    return True

for i in range(2 ** n): 
    judge = [0 for i in range(m)]
    for j in range(n):  
        if ((i >> j) & 1):  
            for d in dic_s[j]: 
                judge[d] += 1
    
    if judge_bright(judge):      
        total+=1
print(total)

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

import itertools
L = [0, 1] 
num = N 
bit_list = list(itertools.product([0, 1], repeat=num))
ans = 0

for i in range(len(bit_list)):
    light = 0
    for j in range(len(ks)):
        count = 0
        for k in range(1,len(ks[j])):
            if bit_list[i][ks[j][k]-1] == 1:
                count += 1
        if count%2 == p[j]:
            light += 1
    if light == M:
        ans += 1
        
print(ans)

Solution (Python):

n,m=map(int,raw_input().split())
s=[map(int,raw_input().split()) for i in range(m)]
p=map(int,raw_input().split())
res=0
for i in range(2**n):
 res+=1
 for j in range(len(s)):
  on=0
  for k in range(s[j][0]):
   on+=((i>>(s[j][k+1]-1))%2)
  if on%2!=p[j]:
   res-=1
   break
print res

Solution (Python):

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

l=[list(map(int,input().split())) for i in range(m)]
pl=list(map(int,input().split()))
ans=0
for i in range(2**n):
    b=bin(i)
    switch=[0 for k in range(10)]
    for j in range(n):
        if ((i >> j) & 1):
            switch[j]=1
    flag=True
    for a in range(m):
        templ=l[a]
        k=templ[0]
        count=0
        for t in range(k):
            s=templ[t+1]
            if switch[s-1]==1:
                count+=1
        if count%2!=pl[a]:
            flag=False
            break
    if flag:
        ans+=1
print(ans)

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

pattern=[]
ans=0
for i in range(2**(n)):
  count=0
  tmp=[0]*n
  for j in range(n):
    if i>>j & 1:
      tmp[j]=1
  pattern.append(tmp)
  
  for j in range(m):
    num=0
    for t in range(k[j]):
      num+=pattern[i][s[j][t]-1]
    if (num%2==p[j]%2):
      count+=1
  if (count==m):
    ans+=1
print(ans)

Solution (Python):
N, M = map(int, input().split())
S = []
for _ in range(M):
    arr = list(map(int, input().split()))
    bit = 0
    for i in arr[1:]:
        bit = bit | (1 << (i - 1))
    S.append(bit)
P = list(map(int, input().split()))

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

Solution (Python):
N, M = map(int, input().split())
S = []
for _ in range(M):
    arr = list(map(int, input().split()))
    bit = 0
    for i in arr[1:]:
        
        bit = bit | (1 << (i - 1))
    
    S.append(bit)
    
P = list(map(int, input().split()))



ans = 0
for bit in range(1 << N):
    cnt = 0
    for i in range(M):
        
        p = S[i] & bit
        
        on = 0
        for j in range(N):
            
            if p & (1 << j):
                on += 1
            
            
        
        
        if (on % 2) == P[i]:
            cnt += 1
    if cnt == M:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
S = []
for _ in range(M):
    arr = list(map(int, input().split()))
    bit = 0
    for i in arr[1:]:
        
        bit = bit | (1 << (i - 1))
    
    S.append(bit)
    
P = list(map(int, input().split()))



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

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

ans = 0
for i in range(2**n):
    ls = [0] * n
    
    for j in range(n):
        if (i >> j) & 1:
            ls[j] = 1
            
    am = [0] * m      
    
    for j in range(m):
        for k in s[j][1:]:
            if ls[k-1] == 1:
                am[j] += 1
    
    t = 0
    for j in range(m):
        if am[j] % 2 == p[j]:
            t += 1
        
    if t == m:
        ans += 1
        
print(ans)

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

ans=0
for i in range(2**n):
    on_swich=[]
    for j in range(n):
        if (i>>j)&1:
            on_swich.append(j+1)

    
    for k in range(m):
        set_s=set(ks[k][1:])
        on_num=len(set_s&set(on_swich))
        if on_num%2!=p[k]:break
    else:
        ans+=1
print(ans)

Solution (Python):
def inpl():
    return tuple(map(int, input().split()))


def getPattern(i):
    return {j for j in range(N) if (i >> j) % 2}


def isOn(pattern):
    return all(P[i] == len(pattern & S[i]) % 2 for i in range(M))


N, M = inpl()
S = []
for _ in range(M):
    tmp = inpl()
    tmp = [t - 1 for t in tmp[1:]]
    S.append(set(tmp))
P = inpl()

ans = 0
for i in range(2**N):
    pattern = getPattern(i)
    ans += int(isOn(pattern))
print(ans)

Solution (Python):

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

counter = 0

for i in range(1<<N):
    b = format(i, '0%db'%N)
    flag = True
    for j in range(M):
        c = 0
        for k in S[j]:
            c += int(b[k-1])
        if c % 2 != P[j]:
            flag = False
    if flag:
        counter += 1

print(counter)

Solution (Python):
def roop(onoff, n):
    swit[n] = onoff
    if n == N-1:
        flag = True
        for i in range(M):
            if flag == False: break
            cur = 0
            for s in range(1,data[i][0]+1):
                cur += swit[data[i][s]-1]
            if cur%2 != p[i]:
                flag = False
                break
        if flag:
            return 1
        else:
            return 0
    else:
        return roop(0,n+1) + roop(1,n+1)
        

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

swit = [0]*N
print(roop(0,0) + roop(1,0))

Solution (Python):
n,m = map(int,input().split())
d_s_list = []
for i in range(m):
  d_s = list(map(int,input().split()))
  d_s_p = d_s[1:]
  d_s_list.append(d_s_p)
check_list = list(map(int,input().split()))
s_case = []
for i in range(2**n):
  s = [0 for i in range(n)]
  for j in range(n):
     if ((i >> j) & 1):
        s[j] = 1
  s_case.append(s)
  
ok_list = []
for case in s_case:
  frug = True
  for d_s in range(m):
    checker = 0
    for i in d_s_list[d_s]:
      checker  +=  case[i - 1] 
    if checker % 2 != check_list[d_s]:
      frug = False
  if frug == True:
    ok_list.append(case)
    
print(len(ok_list))

Solution (Python):
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

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

S = defaultdict(set)
for i in range(M):
    k, *s = map(int, input().split())
    for j in s:
        S[j - 1].add(i)

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

ans = 0
for i in range(2 ** N):
    on = [(i & (1 << j)) > 0 for j in range(N)]
    count = defaultdict(int)
    for j, ok in enumerate(on):
        if ok:
            for k in S[j]:
                count[k] += 1
    if all(count[j] % 2 == p[j] for j in range(M)):
        ans += 1
print(ans)

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

ans=0
for bit in range(1<<n):
    for i in range(m): 
        if P[i]!= sum([bit>>(j-1) & 1 for j in A[i]])%2:
            break
        if i==m-1:
            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())))

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

ans = 0

for i in range(2**N):
    flag = True
    for j in range(M):
        tmp = 0
        for h in range(1,s[j][0]+1):
            if (i>>(s[j][h]-1))&1:
                tmp += 1
        if tmp%2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Solution (Python):








import numpy as np



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

lights = [list(map(int,input().split())) for _ in range(m)]
lightflg = list(map(int,input().split()))

ans = 0
for switch_bits in range(0,1<<n):
    allflg = True
    for i in range(m):
        flg = lightflg[i]
        on_count = 0
        for switch in lights[i][1:]:
            switch -= 1
            if switch_bits>>switch & 1:
                on_count += 1
        if on_count%2 != flg:
            allflg = False
            break
    if allflg:
        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()))

cnt = 0

for i in range(2 ** N):
    flag = True
    for j in range(M):
        if not([(i >> k-1) & 1  for k in s[j]].count(1) % 2 == p[j]):
            flag = False
    if flag:
        cnt += 1

print(cnt)

Solution (Python):
n,m = map(int,input().split())
k = []
s = []
for i in range(m):
    kk,*ss = map(int,input().split())
    k.append(kk)
    s.append(ss)
p = [int(x) for x in input().split()]
d = []
ans = 0

for i in range(2**n): 
    flag = True
    for j in range(m): 
        count = 0
        for l in range(len(s[j])): 
            tmp = s[j][l]
            
            if (i >> tmp-1) & 1 == 1:
                count += 1
        
        if count%2 != p[j]:
            flag = False
    
    if flag:
        ans += 1
print(ans)

Solution (Python):
n,m =map(int,input().split())
s_li = []
k_li = []
for i in range(m):
  inp = list(map(int,input().split()))
  k_li.append(inp[0])
  s_li.append(inp[1:])
p_li = list(map(int,input().split()))
cnt = 0 
for bit in range(1<<n): 
  ok = True
  for i in range(m):
    con = 0 
    for j in s_li[i]:
      
      if ((bit >> j-1) & 1) == 1:
        
        con += 1
    if con%2 != p_li[i]:
      ok = False
  if ok == True:
    cnt += 1
print(cnt)

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

answer = 0
for i in range(1 << N):
    for (_, *ss), p in zip(kss, ps):
        okay = True
        if sum([(i >> s-1) & 1 for s in ss]) % 2 != p:
            okay = False
            break
    if okay:
        answer += 1

print(answer)

Solution (Python):
from itertools import product

N, M = map(int, input().split())
kss = [list(map(int, input().split())) for _ in range(M)]
ps = list(map(int, input().split()))

answer = 0
for switches in product(range(2), repeat=N):
    for (_, *ss), p in zip(kss, ps):
        okay = True
        if sum([switches[s-1] for s in ss]) % 2 != p:
            okay = False
            break
    if okay:
        answer += 1

print(answer)

Solution (Python):
from itertools import product

N, M = map(int, input().split())
kss = [list(map(int, input().split())) for _ in range(M)]
ps = list(map(int, input().split()))

answer = 0
for switches in product(range(2), repeat=N):
    for (_, *ss), p in zip(kss, ps):
        okay = True
        if sum([switches[s-1] for s in ss]) % 2 != p:
            okay = False
            break
    if okay:
        answer += 1

print(answer)

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

answer = 0
for i in range(1 << N):
    for (_, *ss), p in zip(kss, ps):
        okay = True
        if sum([(i >> s-1) & 1 for s in ss]) % 2 != p:
            okay = False
            break
    if okay:
        answer += 1

print(answer)

Solution (Python):


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

s=[]

for i in range(m):
    sss=list(map(int,input().split()))
    k=sss[0]
    b=0
    for ss in sss[1:]:
        b+=0b1<<(ss-1)
    s.append(b)


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

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

ans=0

for i in range(2**n):
    ok=True
    for k in range(m):
        cnt=cntbin(i&s[k])
        if cnt%2==p[k]:
            pass
        else:ok=False

    if ok:ans+=1

print(ans)

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

ans=0

for i in range(2**n):
    switch=[None]*n
    for j in range(n):
        if ((i>>j)&1)==1:
            switch[j]=True
    cnt=0
    for x,light in enumerate(k):
        tmp=0
        for i in range(len(light)):
            if i==0:
                continue
            if switch[light[i]-1]==True:
                tmp+=1
        if tmp%2==p[x]:
            cnt+=1
    if cnt==m:
        ans+=1
print(ans)

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

res = 0
for bit in range(2**N):
  sw = [0] * N
  for i in range(N):
    sw[i] = (bit >> i) & 1
  are_shining = True
  for i in range(M):
    cnt_on = 0
    for j in range(k[i]):
      if sw[s[i][j]-1] == 1:
        cnt_on += 1
    if cnt_on % 2 != p[i]:
      are_shining = False
  if are_shining:
    res += 1

print(res)

Solution (Python):
def resolve():
    n, m = map(int, input().split())
    S = [tuple(map(int, input().split()))[1:] for _ in range(m)]
    P = tuple(map(int, input().split()))

    ans = 0
    for ps in range(2**n):
        fl = [False] * m
        for k, v in enumerate(S):
            cnt = 0
            for s in v:
                if ps & 1 << (s-1):
                    cnt += 1

            if cnt % 2 == P[k]:
                fl[k] = True

        if all(fl):
            ans += 1

    print(ans)

if __name__ == '__main__':
    resolve()

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

cnt = 0

for i in range(2 ** N):
    flag = True
    for j in range(M):
        if not([(i >> k-1) & 1  for k in s[j]].count(1) % 2 == p[j]):
            flag = False
    if flag:
        cnt += 1

print(cnt)

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(2**n):
    flag = True
    for j in range(m):
        if not([1 & (i >> k-1) for k in s[j]].count(1) % 2 == p[j]):
            flag = False
    if flag:
        count += 1
print(count)

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

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

ans=0

def dfs(i,f):
    global ans
    if i==n-1:
        a=0
        for j in range(len(l)):
            sw=p[j]+1
            x=l[j][1:]
            for k in x:
                if f[k-1]=="1":
                    sw+=1
            
            if sw%2:
               a+=1
        
        if a==len(p):
            ans+=1
        return 0
    else:
        dfs(i+1,f+"0")
        dfs(i+1,f+"1")

dfs(0,"0")
dfs(0,"1")
print(ans)

Solution (Python):
N,M=map(int,input().split())
A=[0]*M
for i in range(M):
 A[i]=list(map(int,input().split()))
P=list(map(int,input().split()))
F=0
for i in range(2**N):
 E=0
 Sui=[0]*N
 for j in range(N):
  if ((i >> j) & 1):
   Sui[j]+=1
 for k in range(M):
  D=0
  for l in range(1,A[k][0]+1):
   if Sui[A[k][l]-1]==1:
    D+=1
  if D%2==P[k]:
   E+=1
 if E==M:
  F+=1
print(F)

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

s = []
for i in range(m):
  array = list(map(int, input().split()))
  tmp = 0
  for j in range(1, len(array)):
    tmp += 2 ** (array[j]-1)
    
  s.append(tmp)

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

count = 0
for i in range(0, 2**n):
  array = []
  for j in range(len(s)):
    tmp = i & s[j]
    tmp = bin(tmp).replace('0b', '').replace('0', '')
    r = len(tmp) % 2
    array.append(r)
    
  if p == array:
    count += 1
    
print(count)

Solution (Python):
from itertools import product

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


count = 0
for i in product([0,1], repeat=n):
    i = list(i)
    on = True
    for j in range(m):
        score = 0
        for k in s[j]:
            if i[k] == 1:
                score += 1
        if score % 2 == p[j]:
            continue

        else:
            on = False
            break

    if on:
        count += 1

print(count)

Solution (Python):
N,M = map(int,input().split())
L = [[] for _ in range(M)]
for i in range(M):
  L[i] = list(map(int,input().split()))
  L[i].remove(L[i][0])
P = list(map(int,input().split()))
Cand = []
for i in range(2**N):
  res = []
  for j in range(N):
    if ((i>>j) & 1):
      res.append(1)
    else:
      res.append(0)
  Cand.append(res) 
res = 0
for i in range(2**N):
    key = 0
    loop = 0
    for j in range(M):
        loop = 1
        if P[j] == 0:
            Even_counter = 0
            for el in L[j]:
                if Cand[i][el-1] == 1:
                    Even_counter += 1
            if Even_counter % 2 != 0:
                key = 1
                break
        if P[j] == 1:
            Od_counter = 0
            for el in L[j]:
                if Cand[i][el-1] == 1:
                    Od_counter += 1
            if Od_counter % 2 != 1:
                key = 1
                break           
        if key == 0 and j == M-1 and loop == 1:
            res += 1    
print(res)

Solution (Python):
f=lambda:map(int,input().split())
n,m=f()
ll=[[0]*n for _ in range(m)]
for l in ll:
  k,*s=f()
  for i in s: l[i-1]=1
p=list(f())
import itertools as it
print(sum(all(sum(a*b for a,b in zip(l,t))%2==p[i] for i,l in enumerate(ll)) for t in it.product([0,1],repeat=n)))

Solution (Python):
def int_to_list(bit, n):
    l = []
    for i in range(n):
     if bit & (1 << i):
         l.append(i)
    return l

def solve():
    N, M = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(M)]
    p = list(map(int, input().split()))

    c = 0
    for i in range(1 << N):
        partial = int_to_list(i, N)
        b = True
        
        for j in range(M):
            d = 0
            for k in range(A[j][0]):
                if A[j][k+1]-1 in partial:
                    d += 1
            if d % 2 != p[j]:
                b = False

        if b:
            c += 1
        
    return c

print(solve())