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 = [[] for _  in range(M)]
k=[0]*M

for i in range(M):
    temp = list(map(int,input().split()))
    k[i] = temp[0]
    s[i]= temp[1:]
    
p = list(map(int,input().split()))

cnt = 0

for i in range(1<<N):
    
    switch = []
    
    result =[0]*M
    
    
    for j in range(N):
        if (i>>j&1):
            switch.append(j+1)
        else:
            continue
        

    
    for  w in range(len(switch)):
        temp = switch[w]
        for x in range(M):
            if s[x].count(temp)>0:
                result[x]+=1
                    
    flg =  True
    
    for u in range(M):
        if result[u]%2!=p[u]:
            flg = False
            
    if flg ==True:
        cnt+=1
        

print(cnt)

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

ans=0
for i in range(2**n):
    f=1
    for j in range(m):
        c=0
        for x in sw[j][1:]:
            x-=1
            c+=(i>>x)&1
        if c%2!=p[j]:
            f=0
    ans+=1 if f else 0
print(ans)

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

cnt = 0
for i in range(2**N):
    check = [False] * M
    for j, bulb in enumerate(bulbs):
        on_sum = 0
        for b in bulb:
            if i >> (b-1) & 1:
                on_sum += 1
        
        if on_sum%2 == p[j]:
            check[j] = True
        
    if all(check):
        cnt += 1

print(cnt)

Solution (Python):
from itertools import product
 
N, M = map(int, input().split())
switches = [list(map(int, input().split()[1:])) for _ in range(M)]
p = list(map(int, input().split()))
 
num_pattern = 0
for pattern in product(*[range(2) for _ in range(N)]):
    on_switches = [0]*M  
    for i, switch in enumerate(switches):
        for s in switch:
            if pattern[s-1] == 1:
                on_switches[i] += 1
                
    for i, on_num in enumerate(on_switches):
        if on_num % 2 != p[i]:
            break
    else:
        num_pattern += 1
print(num_pattern)

Solution (Python):
from itertools import product

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

num_pattern = 0
for pattern in product(*[range(2) for _ in range(N)]):
    on_switches = [0]*M  
    for i, switch in enumerate(switches):
        for s in switch:
            if pattern[s-1] == 1:
                on_switches[i] += 1
                
    for i, on_num in enumerate(on_switches):
        if on_num % 2 != p[i]:
            break
    else:
        num_pattern += 1
print(num_pattern)

Solution (Python):
N, M  = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(M)]
P = list(map(int, input().split()))
count = 0
for i in range(2**N):
    bit = format(i, 'b').zfill(N)
    light = [0] * M
    for j in range(M):
        num = 0
        for k in range(S[j][0]):
            num += int(bit[S[j][k+1]-1])
        if num % 2 == P[j]:
            light[j] = 1
    if all([on == 1 for on in light]):
        count += 1
print(count)

Solution (Python):

def main():
    import sys
    import itertools as ite
    N, M = map(int, sys.stdin.readline().split())
    Light = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
    P = list(map(int, sys.stdin.readline().split()))
    S = list(ite.product([0,1], repeat=N)) 
    ans = 0
    for s_state in S:
        L_result = [0 for _ in range(M)]
        for m in range(M):
            for s_no in Light[m][1:]:
                L_result[m] += s_state[s_no-1]
        L_result = list(map(lambda x:x%2, L_result))
        if P == L_result:
            ans +=1
    print(ans)

if __name__=='__main__':
    main()

Solution (Python):

def main():
    import sys
    N, M = map(int, sys.stdin.readline().split())
    Light = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
    P = list(map(int, sys.stdin.readline().split()))
    
    
    ans = 0
    for i in range(2**N):
        cnt = [0 for _ in range(M)]
        for m in range(M):
            for s in Light[m][1:]:
                cnt[m] += (i>>N-s)&1
        cnt = list(map(lambda x:x%2, cnt))
        if cnt == P:
            ans +=1
    print(ans)

if __name__=='__main__':
    main()

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

for i in range(m):
    k_input[i],*s_input[i] = map(int,input().split())
p_input = list(map(int,input().split()))


ans=0
for i in range(2**n):
    flag = True
    switch = [0]*n
    for j in range(n):
        if ((i>>j)&1):
            switch[j]=1
    for k in range(m):
        tmp=0
        for s in s_input[k]:
            tmp+=switch[s-1]
        if tmp%2!=p_input[k]:
            flag=False
            break
    if flag:
        ans+=1
print(ans)

Solution (Python):
N,M=[int(x) for x in input().rstrip().split()]
l=[]
for i in range(M):
  ks=[int(x) for x in input().rstrip().split()]
  l.append(ks)
p=[int(x) for x in input().rstrip().split()]

ans=0
onof=[False for i in range(N)]
for i in range(2**N):
  for j in range(N):
    if i>>j & 1:
      onof[j]=True
  
  cnt=0
  
  for s in range(M):
    bulb=l[s]
    now=0
    for t in range(len(bulb)-1):
      if onof[bulb[t+1]-1]==True:
        now+=1
    if now%2==p[s]:
      cnt+=1
  if cnt==M:
    ans+=1
  onof=[False for b in range(N)]

print(ans)

Solution (Python):
N,M=[int(x) for x in input().rstrip().split()]
l=[]
for i in range(M):
  ks=[int(x) for x in input().rstrip().split()]
  l.append(ks)
p=[int(x) for x in input().rstrip().split()]
now_l=[False for i in range(N)]
ans=0

for i in range(2**N):
  for j in range(N):
    if i>>j & 1:
      now_l[j]=True
  cnt1=0
  for s in range(M):
    now=l[s]
    cnt=0
    for t in range(len(now)-1):
      if now_l[now[t+1]-1]==True:
        cnt+=1
    if cnt%2==p[s]:
      cnt1+=1
  if cnt1==M:
    ans+=1
  now_l=[False for b in range(N)]
print(ans)

Solution (Python):
import itertools
import math
import fractions
import functools
import copy

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

result = 0
for i in range(2**n):
    count = 0
    for d in range(m):
        on = 0
        for sw in range(n):
            if i >> sw & 1:
                for o in range(k[d]):
                    if s[d][o] == sw+1:
                        on += 1
        if on % 2 == p[d]:
            count += 1
    if count == m:
        result += 1

print(result)

Solution (Python):
from itertools import combinations
def main():
    N, M = map(int, input().split())
    want = []
    for _ in range(M):
        tmp = list(map(int, input().split()))
        want.append(tmp[1:])
    cond = list(map(int, input().split()))
    
    swith = [i for i in range(N)]
    choice = 0
    cnt = 0
    while choice <= N:
        for comb in combinations(swith, choice):
            inp = [0 for _ in range(M)]
            
            for c in comb:
                for i, w in enumerate(want):
                    if c+1 in w:
                        inp[i] += 1
            
            flag = True
            for i in range(M):
                if inp[i]%2 != cond[i]:
                    flag = False    
            if flag:
                cnt += 1
        choice += 1
    print(cnt)
main()

Solution (Python):
N, M = list(map(int, input().split()))
K = [list(map(int, input().split())) for _ in range(M)]
P = list(map(int, input().split()))
count = 0
for i in range(2 ** N):
    S = [0] * N
    E = [0] * M
    for j in range(N):
        if i >> j & 1:
            S[j] = 1
    for m in range(M):
        SN = [k - 1 for k in K[m][1:]]
        if sum([S[sn] for sn in SN]) % 2 == P[m]:
            E[m] = 1
    if all(E):
        count += 1
print(count)

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


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

Solution (Python):
import math
import copy
from queue import Queue
import heapq
import numpy as np

MOD = 5000000007



n, m = [int(i) for i in input().split()]
table = [[int(i)  for i in input().split()] for j in range(m)]

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












count = 0
for i in range(2 ** n):
    flag = 1
    for j in range(0,m):
        temp = 0
        for k in range(table[j][0]):
            if((i >> (table[j][k+1] - 1)) & 1 ) :
                temp += 1
        if(temp % 2 != p[j]):
            flag = 0
    if(flag == 1):
        count += 1

print(count)

Solution (Python):
N,M = map(int,input().split())
switch = [i for i in range(1,N+1)]
light = {}

for i in range(M):
  ks = list(map(int,input().split()))
  light[i+1] = ks[1:] 
p = list(map(int,input().split()))
res = 0
for i in range(2**len(switch)):  
    li = []
    cnt = 0
    for j in range(len(switch)):
        if (i >> j) &1 == 1:
            li.append(switch[j])
    for j in range(1,M+1):
      if len(set(light[j]) & set(li)) % 2 == p[j-1]:
        cnt += 1
    if cnt == M:
      res += 1
print(res)

Solution (Python):
N,M = map(int,input().split())
K,S=[],[]
for _ in range(M):
    ks = list(map(int,input().split()))
    K.append(ks[0])
    S.append(ks[1:])

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

ans = 0
for i in range(2**N):
    on_cnt = [0]*M
    ok = True
    for j in range(N):
        if (i>>j) & 1:
            for s in range(M):
                if (j+1) in S[s]:
                    on_cnt[s] += 1
    for t in range(M):
        if on_cnt[t] % 2 != p[t]:
            ok = False
    
    if ok:
        ans +=1
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import product

n, m = map(int, readline().split())
ks = [list(map(int, readline().split()))[1:] for _ in range(m)]
p = list(map(int, readline().split()))
ans = 0
for bit in product([0, 1], repeat=n):
    for pp, ksi in zip(p, ks):
        cnt = 0
        for j in range(n):
            if bit[j] == 1 and (j + 1) in ksi:
                cnt += 1
        if cnt % 2 != pp:
            break
    else:
        ans += 1

print(ans)

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


k = []
s = []
ans = 0

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

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

for bit in range(1 << n):
    light_on = 0
    for i in range(m):
        switch_on = 0
        for j in range(k[i]):
            if (bit >> (s[i][j] - 1)) & 1:
                switch_on += 1

        if switch_on % 2 == p[i]:
            light_on += 1

    if light_on == m:
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
ks_mat =  [list(map(int, input().split())) for i in range(M)]
p = list(map(int, input().split()))
import itertools
OnOff_list = itertools.product([True,False],repeat=N)
ans = 0
for OnOff in OnOff_list:
    for i in range(M):
        c = 0
        for k, j in enumerate(OnOff):
            if j and (k+1 in ks_mat[i][1:]):
                c += 1
        if not c % 2 == p[i]:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
s = []
for _ in range(m):
    _, *ss = map(int, input().split())
    s.append(ss)
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    for j in range(m):
        tmp = 0
        for k in s[j]:
            tmp += i>>(k-1)&1
        if tmp%2!=p[j]:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
K = []
S = []
for m in range(M):
    l = list(map(int, input().split()))
    k = l.pop(0)
    K.append(k)
    S.append(l)
P = list(map(int, input().split()))
ans = 0
for n in range(1<<N):
    res = True
    for m in range(M):
        cnt = 0
        for q in range(K[m]):
            if n & (1<<S[m][q]-1):
                cnt += 1
        if cnt % 2 != P[m]:
            res = False
    if res:
        ans += 1
print(ans)

Solution (Python):
import sys


input = sys.stdin.readline


def make_switch_set(i, s):
    if i == N:
        return [s]
    else:
        cs = s.copy()
        cs.add(i+1)
        return make_switch_set(i+1, s) + make_switch_set(i+1, cs)


def main():
    ans = 0
    for ss in switch_set:
        count = 0
        for switches, p in zip(S, P):
            match_num = len(ss & switches)
            if match_num % 2 == p:
                count += 1
        if count == M:
            ans += 1
    print(ans)


if __name__ == "__main__":
    N, M = map(int, input().split())
    S = []
    for _ in range(M):
        ipts = [int(ipt) for ipt in input().split()]
        S.append(set(ipts[1:]))
    P = [int(p) for p in input().split()]
    switch_set = make_switch_set(0, set())
    main()

Solution (Python):
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m=n1()
ks=n3(m)
p=n1()

import itertools
ite=itertools.product([0,1],repeat=n)
ans=0
for line in ite:
    for i in range(m):
        c=0
        light=ks[i][1:]
        for j in light:
            c+=line[j-1]
        if c%2!=p[i]:
            break
    else:
        ans+=1
print(ans)

Solution (Python):

from copy import copy

ans = 0

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

  table = [None] * m
  for i in range(m):
    S = map(lambda x: int(x) - 1, input().split())
    next(S)
    table[i] = tuple(S)

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

  def check(switchs):
    global ans
    for i in range(m):
      S = table[i]
      total = 0
      for s in S:
        total += switchs[s]

      if total % 2 != P[i]:
        return False

    ans += 1
    return True

  default = [0 for _ in range(n)]
  dp = [default]
  check(dp[0])

  for i in range(n):
    for j in range(len(dp)):
      switchs = dp[j]
      new_switchs = copy(switchs)
      new_switchs[i] = 1
      check(new_switchs)
      dp.append(new_switchs)

  print(ans)


main()

Solution (Python):
def main():
    switch_number = []
    N, M = map(int, input().split())
    for _ in range(M):
        k = tuple(map(int, input().split()))
        switch_number.append(k[1:])
    p = list(map(int, input().split()))

    ans = 0
    for i in range(2 ** N):
        binary = list(map(int, format(i, 'b').zfill(N)))
        a = True
        for k, number in enumerate(switch_number):
            count = 0
            for j in number:
                if binary[j - 1] == 1:
                    count += 1
            if count % 2 != p[k]:
                a = False
                break
        if a:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

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

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

ans=0
for i in range(2**n):
    flag=False
    s=[0]*n
    
    for j in range(n):
        if ((i>>j) & 1):
            s[j]=1      
    
    for k in range(m):
        total=0
        judge=switches[k][1:]
        for l in judge:
            total += s[l-1]
            
        if total%2 == p[k]:
            flag=True
        
        if total%2 != p[k]:
            flag=False
            break
        
    if flag:
        ans+=1

print(ans)

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

ans = 0
for c in product([0, 1], repeat=N):
    ok = True
    for m in range(M):
        sm = 0
        for s in S[m]:
            sm += c[s - 1]
        if sm % 2 != P[m]:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

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

ans = 0
for c in product([0,1],repeat=N):
    ok = True
    for m in range(M):
        sm = 0
        for s in S[m]:
            sm += c[s-1]
        if sm % 2 != P[m]:
            ok = False
            break
    if ok:
        ans += 1
print (ans)

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

def judge(switch):            
    for i in range(m):
        k = light_bulb[i][0]
        count = 0
        for j in range(1,k+1):
            on = light_bulb[i][j]-1
            if switch[on] == 1:
                count +=1
        if count % 2 != p[i]:
            return False
    return True
counter = 0
for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if (i>>j)&1:
            switch[j] = 1
    if judge(switch):
        counter += 1
print(counter)

Solution (Python):

def main():
    n, m = map(int, input().split())
    
    s = []; k = [] 
    for _ in range(m):
        tmp = list(map(int, input().split()))
        s.append(tmp[1:]); k.append(tmp[0])
    p = list(map(int, input().split()))

    res = 0
    
    for bit in range(2**n):
        ok = True
        for i in range(m): 
            cnt = 0
            for v in s[i]: 
                if ( bit & 1 << (v - 1) ): 
                    cnt += 1
            if cnt % 2 != p[i]:
                ok = False
        if ok: 
            res += 1

    print(res)

if __name__ == "__main__":
    main()

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()))
ans=0
for i in range(2**n):
  switch=[0]*n
  cnt_on=0
  for j in range(n):
    if (i>>j)&1:
      switch[j]+=1
  for j in range(m):
    cnt=0
    for k in range(ks[j][0]):
      if switch[ks[j][k+1]-1]==1:
        cnt+=1
    if cnt%2==p[j]:
      cnt_on+=1
  if cnt_on==m:
    ans+=1
print(ans)

Solution (Python):
n,m=map(int,input().split())
a,c=[],0
for i in range(m):
    a.append(list(map(int,input().split())))
p=list(map(int,input().split()))
for i in range(2**n):
    i,b='0'*(n-len(bin(i))+2)+bin(i)[2:],0
    for j in range(m):
        f=0
        for k in range(a[j][0]):
            f+=int(i[a[j][k+1]-1])
        if f%2==p[j]:
            b+=1
    if b==m:
        c+=1
print(c)

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

Solution (Python):
from itertools import product

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

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

print(cnt)

Solution (Python):
import sys
import os
from itertools import combinations

def file_input():
    f = open('ABC128/input.txt', 'r')
    sys.stdin = f

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

    out=0
    for i in range(N+1):
        for li in combinations(range(N),i):
            
            on=0
            for m in range(M):
                tmp=0
                for j in range(k[m]):
                    
                    for c in li:
                        if s[m][j]==c+1:
                            tmp+=1
                if tmp%2==p[m]:
                    on+=1
            if on==M:
                
                out+=1

    print(out)


if __name__ == '__main__':
    main()

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

ans=0

for i in range(1<<n):
    
    every_on=True
    for j in range(m):
        
        cnt=0
        for u in range(li[j][0]):
            if i>>(li[j][u+1]-1)&1:
                cnt+=1
        if cnt%2!=p[j]:
            every_on=False
    if every_on:
        ans+=1
print(ans)

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

    kslist.append(list(map(lambda x: int(x)-1, input().split()))[1:])

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


ans = 0

for i in range(1 << N):
    for r in range(M):
        on_sum = 0
        for j in range(N):
            if i >> j & 1 and j in kslist[r]:
                on_sum += 1
        if on_sum % 2 != plist[r]:
            break
    else:
        ans += 1


print(ans)

Solution (Python):



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

answer = 0
for i in range(2**n):
    c = [0 for j in range(m)]
    for j in range(n):
        if ((i >> j) & 1):
            for k,l in enumerate(s[j]):
                if l == 1 and c[k] == 1:
                    c[k] = 0
                elif l == 1:
                    c[k] = 1
            
            
    if ans == c:
        answer += 1
print(answer)

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

need = [None] * m
ans = 0

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

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

for i in range(2 ** n):
    zentou = 1
    status = [0] * n

    for j in range(n):
        if ((i >> j) & 1):
            status[j] = 1

    for j in range(m):
        total = 0
        for t in range(1, len(need[j])):
            if status[need[j][t]-1] == 1:
                total += 1
        
        if total%2 != p[j]:
            zentou = 0

    if zentou == 1:
        ans += 1

print(ans)

Solution (Python):
from itertools import product
n,m = map(int,(input().split()))
sw =[list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))

ans = 0
for bit in product([0, 1], repeat=n):
    ele = True 
    for i in range(m): 
        cnt = 0
        for j in sw[i][1:]: 
            
            cnt += bit[j-1]
        if cnt % 2 != p[i]:
            ele = False
            break
    if ele:
        ans += 1        
print(ans)

Solution (Python):
from itertools import product
n,m = map(int,(input().split()))
sw =[list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))

ans = 0
for bit in product([0, 1], repeat=n):
    ele = True
    for i in range(m):
        cnt = 0
        for j in sw[i][1:]:
            cnt += bit[j-1]
        if cnt % 2 != p[i]:
            ele = False
            break
    if ele:
        ans += 1        
print(ans)

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

switch = [[] for i in range(n)]
for i in range(m):
    line = list(map(int, input().split()))
    del line[0]
    for l in line:
        switch[l - 1].append(i)
p = list(map(int, input().split()))

def make_select(m):
    select = []
    i = 0
    def make_bool(m, i):

        if i > m:
            return 0

        for a in itertools.combinations(range(m), i):
            bool = [False] * m
            for b in a:
                bool[b] = True
            select.append(bool)
        
        i += 1
    
        make_bool(m, i)
    
    make_bool(m, i)
    return select
    
select = make_select(n)

ans = 0
for c in select:
    light = [0] * m
    for i in range(n):
        if c[i]:
            for s in switch[i]:
                light[s] ^= 1
    
    if light == p:
        ans += 1

print(ans)

Solution (Python):
from itertools import product

n,m = list(map(int,input().split()))
swi = []

for _ in range(m):
    k, *sss = list(map(int,input().split()))
    swi.append(sss)
ppp = list(map(int,input().split()))

ans = 0
sta = product((0, 1), repeat=n)

for st in sta:
    flg = True
    for i in range(m):
        cnt = 0
        for j in swi[i]:
            if st[j - 1] == 1:
                cnt += 1
        if cnt % 2 != ppp[i]:
            flg = False
    if flg:
        ans += 1
print(ans)

Solution (Python):
import itertools
n, m = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(m)]
pm = list(map(int, input().split()))
bit = itertools.product([0, 1], repeat=n)
ans = 0
for b in bit:
    flag = True
    for i in range(m):
        on = 0
        for s in ks[i][1:]:
            if b[s-1] == 1:
                on += 1
        if on % 2 != pm[i]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):
import itertools
n, m = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(m)]
pm = list(map(int, input().split()))
bit = itertools.product([0, 1], repeat=n)
ans = 0
for b in bit:
    flag = True
    for i in range(m):
        on = 0
        for s in ks[i][1:]:
            if b[s-1] == 1:
                on += 1
        if on % 2 != pm[i]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
A = [list(map(lambda x: int(x)-1, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
for i in range(1<<n):
    for j in range(m):
        cnt = 0
        for k in range(n):
            if ((i>>k) & 1) and k in A[j]: cnt += 1
        if cnt%2!=p[j]: break
    else: ans += 1
print(ans)

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

ans = 0
for i in range(2**N):
    bi = str(bin(i))[2:]
    bi = bi.zfill(N)
    isAddable = True
    for j in range(M):
        s_sum = 0
        for s in S[j]:
            if bi[s-1] == '1':
                s_sum += 1
        if s_sum % 2 != P[j]:
            isAddable = False
            break
    if isAddable:
        ans += 1
print(ans)

Solution (Python):
import itertools

n, m = map(int, input().split())
lst = []
for _ in range(m):
    item = list(map(int, input().split()))
    item = item[1:]
    lst.append(item)
p = list(map(int, input().split()))

ans = 0
for it in itertools.product([0,1], repeat = n):
    for i, item in enumerate(lst):
        count = 0
        for switch in item:
            if it[switch - 1] == 1:
                count += 1
        if count % 2 != p[i]:
            break
    else:
        ans += 1
print(ans)

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

for _ in range(m):
    k, *sss = list(map(int,input().split()))
    t = 0
    for s in sss:
        t += 1 << (s-1)
    swi.append(t)
ppp = list(map(int,input().split()))
ans = 0

for bit in range(1<<n):
    for s,p in zip(swi,ppp):
        t = bit & s
        c = bin(t).count("1") % 2
        if c != p:
            break
    else:
        ans += 1
print(ans)

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

ans = 0
for i in range(2**n):
    on = []
    for j in range(n):
        if((i >> j) & 1):
            on.append(1)
        else:
            on.append(0)
    count = 0
    for j in range(m):
        total = 0
        for k in range(s[j][0]):
            if on[s[j][k+1]-1] == 1:
                total += 1
    
        if total % 2 == p[j]:
            count += 1
    if count == m:
        ans += 1

print(ans)

Solution (Python):


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

def f(i, on_off):
    if N <= i:
        result = 1
        for i in range(M):
            on = 0
            for j in switches[i]:
                on += on_off[j]
            if on % 2 != lights[i]:
                result = 0
        return result
    return f(i + 1, on_off + [1]) + f(i + 1, on_off + [0])

print(f(0, []))

Solution (Python):
def LI(): 
    return list(map(int,input().split()))

n, m = LI()
ks = [LI() for _ in range(m)]
p = LI()

count_total = 0

for i in range(2**n):
    bit = [(i>>j)&1 for j in range(n)]
    failed = False
    for k in range(m):
        kx = ks[k][0]
        count_on = 0
        for l in range(1, kx + 1):
            skl = ks[k][l]
            count_on += bit[skl - 1]
        if count_on % 2 != p[k]:
            failed = True
    if not failed:
        count_total += 1

print(count_total)

Solution (Python):


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

res = 0
def dfs(i, now):
    global res
    if i == N:
        for j in range(M):
            cnt = 0
            for s in range(k_s[j][0]):
                cnt += now[k_s[j][s+1]-1]
            if cnt % 2 != p[j]:
                break
            if j == M - 1:
                res += 1
    else:
        dfs(i+1, now + [0])
        dfs(i+1, now + [1])

dfs(0, [])

print(res)