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

A = [0, 1]
lt = list(itertools.product(A, repeat=N))
count = 0
for elem in lt:
	for i in range(M):
		sum = 0
		for j in range(len(ks[i])-1):
			sum += elem[ks[i][j+1]-1]
		if sum % 2 != p[i]:
			break
	else:
		count += 1
print(count)

Solution (Python):
import numpy as np
N,M  = map(int,input().split())
coeff = np.zeros((M,N))
for i in range(M):
    inputs = list(map(int,input().split()))
    for switch in inputs[1:]:
        coeff[i][switch-1] = 1
onlist = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    vec = [int(num) for num in bin(i)[2:]]
    fill = N - len(vec)
    vec = np.append(np.zeros(fill),np.array(vec))

    if sum(onlist == np.dot(coeff,vec)%2) == M:
        ans +=1
print(ans)

Solution (Python):
n, m = [int(_) for _ in input().split()]
b = [[int(_) for _ in input().split()] for __ in range(m)]
p = [int(_) for _ in input().split()]
ans = 0
for i in range(2**n):
    s = format(i, '0'+str(n)+'b')
    for j in range(m):
        on = 0
        for k in range(b[j][0]) : on += int(s[b[j][k+1]-1])
        on %= 2
        if p[j] != on : break
    else : ans += 1
print(ans)

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

oh = list(itertools.product(range(0, 2), repeat=n))
re = 0
for i in oh:
    for j in range(m):
        c = 0
        for k in swi[j][1:]:
            c += i[k - 1]
        if c % 2 != p[j]:
            break
    else:
        re += 1
print(re)

Solution (Python):
import itertools

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


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

ans = 0
for way in all_way:
    light = 0
    for i, s in enumerate(S):
        small_sum = 0
        for ss in s:
            for sss in ss:
                if way[sss - 1] == 1:
                    small_sum += 1
            if small_sum % 2 == P[i]:
                light += 1
        if light == M:
            ans += 1

print(ans)

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

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

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

ok = 0
for i in range(2**N):
    s = format(i,'010b')
    s = s[-N:]
    s = [int(s[i]) for i in range(len(s))]

    
    for j in range(M):
        l = s_list[j]
        cnt = 0
        for ll in l:
            if s[ll-1] == 1:
                cnt += 1
        if cnt % 2 != p[j]:
            break
        if j == M-1:
            ok += 1

print(ok)

Solution (Python):
N, M = map(int, input().split())
switch_list=[input().split() for i in range(M)]
switch_list=[[int(i[m+1]) for m in range(len(i)-1)] for i in switch_list]
P_list=input().split()
P_list=[int(i) for i in P_list]
count=0
z=N
for i in range(1 << z):
    switch=[0 for i in range(N)]
    for j in range(z):
        if ((i >> j) & 1) == 1:
            switch[j]=1
    count+=sum([sum([switch[m-1] for m in switch_list[x]])%2==P_list[x] for x in range(M)])==M
print(count)

Solution (Python):
n,m = map(int,input().split())
ls = []
for _ in range(m):
  tmp = list(map(int,input().split()))[1:]
  lls = []
  for i in range(1,n+1):
    lls += [int(i in tmp)]
  ls += [lls]
p = list(map(int,input().split()))
count = 0
yyy = [0]*n
while True:
  if yyy[-1] == 2:
    break
  dd = 0
  for mi in range(m):
    c = 0
    for ni in range(n):
      c += ls[mi][ni] * yyy[ni]
    d = c%2
    dd += 1-int(d==p[mi])
  if dd == 0:
    count += 1
  yyy[0] += 1
  for j in range(0,n-1):
    if yyy[j] == 2:
      yyy[j] = 0
      yyy[j+1] += 1
print(count)

Solution (Python):










import sys


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


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


def input(): return sys.stdin.readline().strip()


def binary(n):
    global length
    op = []
    bit = 1 << length - 1
    while (bit):
        if n & bit == 0:
            op.append(0)
        else:
            op.append(1)
        bit >>= 1
    return op


def main():
    global length
    length, m = get_ints()
    d = {}
    for i in range(m):
        tmp = get_array()
        d[i] = tmp[1:]
    p = get_array()
    ans = 0
    x = 1 << length
    combinations = []
    for i in range(x):
        combinations.append(binary(i))

    for i in combinations:
        flag = True
        for j in range(m):
            cnt = 0
            for k in d[j]:
                if i[k - 1] == 1:
                    cnt += 1
            if cnt % 2 != p[j]:
                flag = False
                break
        if flag == True:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
import itertools

N, M = map(int, input().split())
a = np.zeros((M,N), dtype='int8')
for n in range(M):
    for c in input().split()[1:]:
        a[n, int(c) - 1] = 1
p = np.array(list(map(int, input().split())))
count = 0
for case in itertools.product(range(2), repeat=N):
    np_case = np.array(case)
    b = np.sum(a * np_case, axis=1) % 2
    if all(p == b):
        count += 1
print(count)

Solution (Python):
n, m = map(int, input().split())
h = 1
for i in range(n):
	h *= 2
t = [[] for i in range(m)]
for i in range(m):
	a = [int(x) for x in input().split()]
	k = a[0]
	for j in range(1, k + 1):
		t[i].append(a[j])
p = [int(x) for x in input().split()]
ans = 0
for i in range(h):
	g = []
	for j in range(n):
		x = (i&(1<<j))
		if x == 0:
			g.append(0)
		else:
			g.append(1)
	f = True
	for j in range(m):
		cnt = 0
		for x in t[j]:
			if g[x - 1] == 1:
				cnt += 1
		if cnt % 2 != p[j]:
			f = False
	if f:
		ans += 1
print(ans)

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]
def mi(n): return [wi() for _ in range(n)]
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n, m = wi()
ks = [None] * m
for i in range(m):
    ks[i] = wi()

p = wi()

nums = [0, 1]
for balls in itertools.product(nums, repeat=n):
    tmp = 0
    for i in range(m):
        tmp = 0
        for j in range(1, len(ks[i])):
            tmp += balls[ks[i][j] - 1]
        if tmp % 2 == p[i]:
            pass
        else:
            break
    else:
        ans += 1

print(ans)

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

for i in range(2**n):
    now = set()
    for j in range(n):
        if (i>>j)&1:
            now.add(j+1)
    t  = True
    for j in range(m):
        if len(ks[j][1]&now)%2!=p[j]:
            t = False
            break
    if t:
        ans += 1

print(ans)

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

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

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

result = 0
for m in range(2**N):

    flag = True
    for idx, bulb in enumerate(bulbs):
        count = 0
        for switch in bulb:
            count += (m >> (switch-1)) & 1
        if count % 2 != P[idx]:
            flag = False
            break
    if flag:
        result += 1
print(result)

Solution (Python):
n, m = [int(_) for _ in input().split()]
b = [[int(_) for _ in input().split()] for __ in range(m)]
p = [int(_) for _ in input().split()]
ans = 0
for i in range(2**n):
    s = format(i, '0'+str(n)+'b')
    for j in range(m):
        on = 0
        for k in range(b[j][0]) : on += int(s[b[j][k+1]-1])
        on %= 2
        if p[j] != on : break
    else : ans += 1
print(ans)

Solution (Python):
N, M = map(int, raw_input().split())
ks_list = []
p_list = []
for i in range(M):
    ks_list.append(map(int, raw_input().split()))
p_list.append(map(int, raw_input().split()))

ans_count = 0
for i in range(2**N):
    
    cond = 0
    switch_list = [0]*N
    for j in range(N):
        switch_list[j]=(i>>j)&1

    for m in range(M):
        tmp_count = 0
        for k in range(ks_list[m][0]):
            if switch_list[ks_list[m][1+k]-1] == 1:
                tmp_count = tmp_count + 1

        if p_list[0][m] == (tmp_count % 2):
            cond = 1
        else:
            cond = 0
            break
    if cond == 1:
        ans_count = ans_count + 1
print ans_count

Solution (Python):

import sys;
import string;
sys.setrecursionlimit(20000) 

import copy
import itertools

from functools import lru_cache







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



a = []
for x in range(m):
  a.append([int(x) for x in input().split()])
p = [int(x) for x in input().split()]













def doit(s):
  ok = True
  for x in range(m):
    res = 0
    for y in range(a[x][0]):
      if s[a[x][y+1]-1] == 1:
        res = res + 1
    
    if res % 2 != p[x]:
      ok = False
      break
  
  return ok

def createSw(n):
  if n <= 1:
    return [[0,], [1,]]

  ret = []
  for x in createSw(n-1):
    
    ret.append(x + [0])
    ret.append(x + [1])
    
  
  return ret


try:
  res = 0
  for x in createSw(n):
    if doit(x):
      res = res + 1
  print(res)
except Exception as e:
  print("e", e, file=sys.stderr)

Solution (Python):

import itertools
import numpy as np
ls_S = []
N,M = map(int,input().split())
for m in range(M):
    S = list(map(int,input().split()))
    S = [s-1 for s in S]
    ls_S.append(S[1:])
ptns = list(itertools.product(range(0,2), repeat=N))
ptns = np.array(ptns)


P = list(map(int,input().split()))
def check(P,ls):
    for i in range(len(P)):
        if P[i] == ls[i]:
            pass
        else:
            return 0
    return 1
sm = 0        
for ptn in ptns:
    ans = []
    for S in ls_S:
        
        ans.append(sum(ptn[S])%2)
    
    sm += check(P,ans)
print (sm)

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

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

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

def calc(n,aaa):
    if n == N:
        abc = 0
        for i in range(M):
            ans = 0
            for j in range(1,ks[i][0]+1):
                ans += int(aaa[ks[i][j]-1])
            if p[i] == ans % 2:
                abc += 1

        if abc == M:
            return 1
        else:
            return 0

    ans1 = calc(n+1,aaa + '0')
    ans2 = calc(n+1,aaa + '1')

    return ans1 + ans2

print(calc(0,''))

Solution (Python):
import numpy as np
n,m = map(int,input().split())
x = []
for _ in range(m):
  k = list(map(int,input().split()))
  x.append(k[1:])
p = list(map(int,input().split()))
count = 0
for i in range(2**n):
  code = "0"*(n-len(bin(i))+3) + bin(i)[2:]
  c = np.array([])
  for j in range(n+1):
    c = np.append(c,int(code[j]))
  for i in range(m):
    if int(sum(c[x[i]]))%2 != p[i]:
      count += 1
      break
print(2**n - count)

Solution (Python):
import numpy as np
import itertools

N, M = map(int, input().split())
a = np.zeros((M,N), dtype='int8')
for n in range(M):
    for c in input().split()[1:]:
        a[n, int(c) - 1] = 1
p = np.array(list(map(int, input().split())))
count = 0
for case in itertools.product(range(2), repeat=N):
    np_case = np.array(case)
    b = np.sum(a * np_case, axis=1) % 2
    if all(p == b):
        count += 1
print(count)

Solution (Python):
N,M=map(int,input().split())
A=[]
for i in range(M):
    A.append(list(map(int,input().split())))
P=list(map(int,input().split()))
ans=0
for i in range(2**N,2**(N+1)):
        B=bin(i)
        count=0
        for j in range(M):
            tet=0
            for l in range(A[j][0]):
                tet+=int(B[A[j][l+1]+2])
            if tet%2==P[j]:
                  count+=1
        if count==M:
            ans+=1
print(ans)

Solution (Python):
from itertools import product
n,m = map(int,input().split())
S = []
for i in range(m):
    A = [int(i)-1 for i in input().split()]  
    S.append(A[1:])
P = list(map(int,input().split()))
ass = ["1","0"]
for i in range(n-1):
    ass2 = []
    for x in ass:
        ass2.append(x+"1")
        ass2.append(x+"0")
    ass = ass2[::]
res = 0
for a in ass:   
    cnt = 0 
    for i in range(m):
        tmp = 0
        for j in S[i]:
            if a[j] == "1":
                tmp += 1
        if tmp%2 == P[i]:
            cnt +=1
    if cnt == m:
        res += 1
print(res)

Solution (Python):
import itertools

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

ans = 0
switches = 0b1111111111 >> (10 - N)
for _ in range(0, switches + 1):
    flag = True
    for i in range(M):
        s = 0
        for j in range(1, lights[i][0] + 1):
            s += (_ & (0b1 << (lights[i][j] - 1))) >> (lights[i][j] - 1)
        if s % 2 != p[i]:
            flag = False
    if flag:
        ans += 1

print(ans)

Solution (Python):

from itertools import product

n, m = list(map(int, input().rstrip().split()))
lst = [list(map(int, input().rstrip().split())) for _ in range(m)]
con = list(map(int, input().rstrip().split()))
ans = 0
for i in product(range(2), repeat=n):
    cnt = 0
    for j in range(m):
        ons = 0
        for k in lst[j][1:]:
            if i[k - 1] == 1:
                ons += 1
        if ons % 2 == con[j]:
            cnt += 1
    if cnt == m:
        ans += 1
print(ans)

Solution (Python):
import itertools
import pprint
import numpy as np

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

    data = list()
    for _ in range(M):
        status = [0 for i in range(N)]
        tmp = list(map(int, input().split()))
        for i in tmp[1:]:
            status[i-1] = 1
        data.append(status)

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

    seq = (0, 1)
    candidates = list(itertools.product(seq, repeat=N))

    result = 0
    for candi in candidates:
        candi = np.array(candi)
        
        i = 0
        for bulb in data:
            bulb = np.array(bulb)
            tmp = list(bulb * candi)
            if sum(tmp)%2 != bulbs_on[i]:
                result -= 1
                break
            i+=1
        result += 1
    
    print(result)
            

if __name__ == "__main__":
    main()

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

klist = []
sdict = {}
for m in range(M):
    tmp = list(map(int, input().split()))
    klist.append(tmp[0])
    sdict[m] = tmp[1:]
plist = list(map(int, input().split()))

def solve(N, plist, switch_num):
    global M
    num = 0

    if N == 1:
        idx = []
        idx2 = []
        count = 0
        for m in range(M):
            if switch_num in sdict[m]:
                count += 1
                idx.append(plist[m])
            else:
                idx2.append(plist[m])
        if sum(idx) == len(idx) or sum(idx) == 0:
            if sum(idx2) == 0:
                if count == 0:
                    return 2
                else:
                    return 1
            else:
                return 0
        else:
            return 0

    
    new_plist = plist
    num += solve(N-1, new_plist, switch_num+1)
    
    
    new_plist = []
    for i in range(M):
        if switch_num in sdict[i]:
            new_plist.append(1 - plist[i])
        else:
            new_plist.append(plist[i])
    num += solve(N-1, new_plist, switch_num+1)

    return num

print(solve(N, plist, 1))

Solution (Python):
import itertools
N,M = input().split()
N = int(N)
M = int(M)
line_list = []
for i in range(M):
    line = input().split()
    new_list=[]
    for l in line:
        new_list.append(int(l))
    new_list.pop(0)
    line_list.append(new_list)
old_p_list = input().split()
p_list = []
for p in old_p_list:
    p_list.append(int(p))

A = []
for n in range(N):
    A.append([True,False])
pattern_list = list(itertools.product(*A))
pattern_num = 0
for pattern in pattern_list:
    ok_flug = 1
    for i, line in enumerate(line_list):
            on_num = 0
            for l in line:
                if pattern[l-1]:
                    on_num += 1
            if on_num%2 != p_list[i]:
                ok_flug = 0
    if ok_flug == 1:
        pattern_num += 1
print(pattern_num)

Solution (Python):
import copy


args = input().split()
N, M = int(args[0]), int(args[1])
args_list = [list(map(lambda x: int(x), input().split())) for i in range(M)]
p_list = list(map(lambda x: int(x), input().split()))

count = 0
for i in range(2**N):
  continue_state = True
  args_i = copy.deepcopy(args_list)
  bin_str = format(i, "0{}b".format(N))
  bin_list = [int(bin_str[i]) for i in reversed(range(N))]
  bin_list = [i+1 for i, bit in enumerate(bin_list) if bit == 1]
  for j, current_list in enumerate(args_i):
    on_switchs = 0
    del current_list[0]
    for bin in bin_list:
      if bin in current_list:
        on_switchs += 1
    if on_switchs % 2 != p_list[j]:
      continue_state = False
      break
  if continue_state is False:
    continue
  count += 1
print(count)

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


def main():
    N, M = map(int, input().split())
    k = []
    s = []
    for _ in range(M):
        input_list = list(map(int, input().split()))
        k.append(input_list[0])
        s.append(input_list[1:])
    ps = list(map(int, input().split()))
    candidates = np.array(list(product([0, 1], repeat=N)))
    for i in range(M):
        index = s[i]
        p = ps[i]
        candidates = list(map(partial(is_match, index=index, p=p), candidates))
        candidates = [c for c in candidates if not isinstance(c, type(None))]
        if candidates == None:
            candidates = []
            break
    print(len(candidates))


def is_match(candidate, index, p):
    if sum(candidate[np.array(index) - 1]) % 2 == p:
        return candidate


if __name__ == '__main__':
    main()

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

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

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

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

ans_sum = 0
pre_ = 0
for i1 in [0, 1]:
    for i2 in [0, 1]:
        for i3 in [0, 1]:
            for i4 in [0, 1]:
                for i5 in [0, 1]:
                    for i6 in [0, 1]:
                        for i7 in [0, 1]:
                            for i8 in [0, 1]:
                                for i9 in [0, 1]:
                                    for i10 in [0, 1]:
                                        p_ = [i1, i2, i3, i4, i5, i6, i7, i8, i9, i10]
                                        pre = p_[:N]
                                        if pre == pre_:
                                            break
                                        ans_ = 0
                                        for q in range(M):
                                            ans = 0
                                            for r in range(sk[q][0]):
                                                ans+=pre[sk[q][r+1]-1]
                                            if ans%2 == p[q]:
                                                ans_ +=1
                                        
                                        if ans_ == M:
                                            ans_sum += 1
                                            

                                        pre_ = pre

print(ans_sum)

Solution (Python):
import numpy as np
NM= list(map(int,input().split()))
N = NM[0]
M = NM[1]

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

P = list(map(int,input().split()))
Pt = np.zeros((len(P),1))
for i in range(len(P)):
    Pt[i,0]=P[i]

ta = np.zeros((M,N))
for i in range(M):
    for j in range(len(S[i])):
        ta[i,S[i][j]-1]=1

sta = np.zeros((N,1))

count = 0
def func(k):
    global count
    global sta
    global ta
    global Pt
    global N
    for i in range(2):
        sta[k]=i
        if k+1 < N:
            func(k+1)
        if (np.dot(ta,sta)%2==Pt).all() and k==N-1:
            count+=1

func(0)
print(int(count))

Solution (Python):
import copy
N,M=map(int,input().split())
linkedBulb=[[] for i in range(N)]
for i in range(M):
    S=[int(_) for _ in input().split()]
    for n,s in enumerate(S):
        if n==0:continue
        else:
            linkedBulb[s-1].append(i)
s=[1-int(i) for i in input().split()]
ans=0
for bit in range(2**N):
    start=copy.deepcopy(s)
    for j in range(N):
        if (bit>>j)&1:
            for todo in linkedBulb[j]:
                start[todo]=1-start[todo]
    if all(start):ans+=1
print(ans)

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

bins = []
for i in range(2**N):
    bins.append(format(i,'b').zfill(N))

cnt = 0
for j in range(2**N):
    b = bins[j]
    accept = 0
    for k in range(M):
        Li = List[k]
        ones = 0
        for l in range(Li[0]):
            if b[Li[l+1]-1]=='1':
                ones+=1
        if ones%2==ps[k]:
                accept+=1
    if accept==M:
        cnt+=1

print(cnt)

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

all_list = []
for i in range(2**N):
    all_list.append([])
    num_str = bin(i)[2:]
    if len(num_str) < N:
        for j in range(N - len(num_str)):
            all_list[i].append(0)
    for k in range(len(num_str)):
        all_list[i].append(int(bin(i)[2:][k]))


ans_num = 0
a = 0
for ans in all_list:
    flag = True

    for i, ks in enumerate(ks_list):
        middle_ans = 0
        for j in range(1,len(ks)):
            
            middle_ans += ans[ks[j]-1]
        
        if middle_ans % 2 == p_list[i]:
            a += 1
        else:
            flag = False
        
    if flag == True:
        ans_num += 1
print(ans_num)

Solution (Python):
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
a=[bin(j)[2:].zfill(n) for j in range(2**n)]
ans=0
for jj in range(2**n):
  b=0
  for i in range(m):
    num=0
    for ii in range(1,s[i][0]+1):
      num+=int(a[jj][s[i][ii]-1])
    if num%2!=p[i]:
      b+=1
  if b==0:
    ans+=1
print(ans)

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

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

def dfs(swi):
    global  ans
    
 
    if len(swi) == n:
        flag = True
        for i in range(m):
            cnt = 0
            for pos in switch[i]:
                if swi[pos-1] == "1":
                    cnt += 1
            if cnt % 2 != p[i]:
                flag = False
        if flag == True:
            ans += 1
    else:

        dfs(swi+"1")

        dfs(swi+"0")




dfs("")
print(ans)

Solution (Python):

if __name__ == '__main__':
    n,m = list(map(int, input().split()))
    ks = []
    bitnums = []
    for i in range(m):
        ks.append(list(map(int, input().split())))
        bitnum = 0
        for j in range(1, ks[i][0]+1):
            bitnum += 1 << (ks[i][j]-1)
        bitnums.append(bitnum)
    p = list(map(int, input().split()))

    np = [1] * (2**n)

    for i in range(len(np)):
        for j in range(m):
            cnt = bin(i & bitnums[j]).count("1")
            if(cnt % 2 != p[j]):
                np[i] = 0
                break
    
    
    
        
    print(sum(np))

Solution (Python):






import sys
import math
import array


class mymath:
    
    pi = 3.14159265358979323846264338

    
    def pnum_eratosthenes(self, n):
        ptable = [0 for i in range(n+1)]
        plist = []

        for i in range(2, n+1):
            if ptable[i]==0:
                plist.append(i)
                for j in range(i+i, n+1, i):
                    ptable[j] = 1
        return plist

    
    def gcd(self, a, b):
        if b == 0:
            return a
        return self.gcd(b, a%b)

    
    def lcm(self, a, b):
        return (a*b)//self.gcd(a,b)

mymath = mymath()


class output:
    
    def list(self, l):
        l = list(l)
        print(" ", end="")
        for i, num in enumerate(l):
            print(num, end="")
            if i != len(l)-1:
                print(" ", end="")
        print()

output = output()
















def main():
    N, M = [int(x) for x in input().split()]
    K = []
    S = []
    
    for i in range(M):
        temp = [int(x) for x in input().split()]
        K.append(temp.pop(0))
        S.append(temp)

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

    ans = 0

    for i in range(2**N):
        tentoucount = 0
        swich = []
        num = bin(i).lstrip('0b').zfill(N)
        for j in num:
            swich.append(int(j))

        for j in range(M):
            onswich = 0
            for k in S[j]:
                onswich += swich[k-1]
            if onswich%2 == P[j]:
                tentoucount += 1

        if tentoucount == M:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin
import itertools

def main():
    n,m = [int(x) for x in stdin.readline().rstrip().split()]
    ss = []
    for x in range(m):
        ks = tuple(map(int, stdin.readline().rstrip().split()))
        ss.append(ks[1:])
    ps = [int(x) for x in stdin.readline().rstrip().split()]

    ans = 0
    for cond in itertools.product((0,1), repeat=n):
        ok = 1
        for s,p in zip(ss,ps):
            total = 0
            for c in s:
                total += cond[c-1]
            if total % 2 != p:
                ok = 0
                break
        ans += ok

    print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):
from itertools import product
n, m = map(int,input().split())
li = []
for i in range(m):
    li_buf = list(map(int,input().split()))
    li.append(li_buf)

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


li_com = []
li_flag = [[True, False] for i in range(10)]
for a, b, c, d, e, f, g, h, i, j in product(li_flag[0], li_flag[1], li_flag[2], li_flag[3], li_flag[4], li_flag[5], li_flag[6], li_flag[7], li_flag[8], li_flag[9]):
    li_com.append([a, b, c, d, e, f, g, h, i, j])

for i in range(m):
    buf = []
    for j in range(len(li[i])):
        if j == 0:
            continue
        buf.append(li[i][j])
    li_com_2 = []
    for k in range(len(li_com)):
        buf_2 = []
        for l in range(len(buf)):
            buf_2.append(li_com[k][buf[l]-1])
        if buf_2.count(True) % 2 == p[i]:
            li_com_2.append(li_com[k])
    li_com = li_com_2
print(int(len(li_com)/ 2 ** (10 - n)))

Solution (Python):
n, m = map(int, input().split())
ans = 0
ss = []
for i in range(m):
    k, *s = map(int, input().split())
    ss.append(s)
ps = list(map(int, input().split()))
for i in range(2**n):
    status = format(i, 'b').zfill(n)
    areAllLit = True
    for j in range(m):
        amount = 0
        for k in ss[j]:
            if status[k-1] == '1':
                amount += 1
        if amount % 2 != ps[j]:
            areAllLit = False
    if areAllLit:
        ans += 1
print(ans)

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

num=2**n
count=0
for i in range(num):
    lump=1
    x=[]
    for j in range(n):
        x.append((i*2//(2**(j+1)))% 2)
    for k in range(m):
        sum=0
        for k1 in range(len(list1[k][1:])):
            if x[list1[k][k1+1]-1]==1:
                sum=sum+1
        if sum % 2!=p[k]:
            lump=0
    if lump==1:
        count=count+1
print(count)

Solution (Python):
import math


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

    s = [0] * N
    ans = 0
    
    for j in range(2 ** N):
        
        temp = j
        for i in range(N):
            s[i] = temp % 2
            temp = temp >> 1

        lamp = [0] * M
        for i in range(M):
            temp = 0
            for k in state[i][1:]:
                temp += s[k - 1]
            if temp % 2 == p[i]:
                lamp[i] = 1

        if all(lamp):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()