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())
l = [list(map(lambda x:int(x)-1, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))

res = 0
for i in itertools.product(range(2), repeat=n):
  i = list(i)
  flg = 0
  for j in range(m):
    now = 0
    for k in l[j]:
      if i[k] == 1:
        now += 1
    if now % 2 == p[j]:
      continue
    else:
      flg += 1
      break
  if flg == 0:
    res += 1
    
print(res)

Solution (Python):
from sys import stdin

N, M = map(int, stdin.readline().split())
light = [None] * M
for i in range(M):
    light[i] = list(map(int, stdin.readline().split()))[1:]
P = list(map(int, stdin.readline().split()))

ans = 0
for i in range(2 ** N):
    on_switch = [0] * N
    for j in range(N):
        if int(format(i, 'b').zfill(N)[j]) == 1:
            on_switch[j] = 1

    on_bulb = 0
    for j in range(M):
        num_of_on_switch = 0
        for index in light[j]:
            num_of_on_switch += on_switch[index - 1]
        if num_of_on_switch % 2 == P[j]:
            on_bulb += 1
    if on_bulb == M:
        ans += 1

print(ans)

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

sw = list(product([True, False], repeat=N))
cnt, ans = 0, 0
for pat in sw:
  flag = True
  for i in range(M):
    cnt = 0
    for j in range(ks[i][0]):
      if pat[ks[i][j+1]-1]:
        cnt += 1
    if cnt % 2 != p[i]:
      flag = False
      break
  if flag:
    ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
light = [0 for _ in range(m)]
for i in range(m):
  key = [int(x) for x in input().split()]
  light[i] = key[1:]

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

ans = 0
for i in range(2**n):
  switch = [0]*n
  for j in range(n):
    if (i >> j) & 1:
      switch[j] = 1
  for j in range(m):
    x = 0
    for k in light[j]:
      if switch[k-1]:
        x += 1
    if x % 2 == p[j]:
      pass
    else:
      break
    if j == m-1:
      ans += 1
      
print(ans)

Solution (Python):

n, m = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    d = [0]*n
    flag = True
    for j in range(n):
        if ((i>>j)&1):
            d[j] = 1
    for k in range(m):
        count = 0
        for l in range(1,s[k][0]+1):
            if d[s[k][l]-1]:
                count += 1
        if count%2!=p[k]:
            flag = False
    if flag:
        ans += 1
print(ans)

Solution (Python):
n_switch, n_light = [int(i) for i in input().split()]
l_s = [[int(i)-1 for i in input().split()][1:] for _ in range(n_light)]
pp = [int(i) for i in input().split()]

ans = 0
for bit in range(1 << n_switch):
    on_switch = {i for i in range(n_switch) if (bit >> i) & 1}
    for i, p in enumerate(pp):
        ok = set(l_s[i]).intersection(on_switch)
        if len(ok) % 2 != p:
            break
    else:
        ans += 1

print(ans)

Solution (Python):


def main():
    N, M = list(map(int, input().split()))
    ks = [list(map(int, input().split())) for _ in range(M)]
    p = list(map(int, input().split()))
    ans = 0

    for condition in ks:
        condition[1:] = list(map(lambda x: x-1, condition[1:]))
    
    for i in range(1 << N):
        switch = [None] * N
        for j in range(N):
            switch[j] = 1 if ((i >> j) & 1) else 0
        
        flag = True
        for m in range(M):
            s = ks[m][1:]
            if sum(switch[idx] for idx in s) % 2 != p[m]:
                flag = False
                break
        if flag:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):


def main():
    N, M = list(map(int, input().split()))
    ks = [list(map(int, input().split())) for _ in range(M)]
    p = list(map(int, input().split()))
    ans = 0
    
    for i in range(1 << N):
        switch = [None] * N
        for j in range(N):
            switch[j] = 1 if ((i >> j) & 1) else 0
        
        flag = True
        for m in range(M):
            tmp = 0
            k = ks[m][0]
            s = list(map(lambda x: x-1, ks[m][1:]))
            for idx in s:
                tmp += switch[idx]
            if tmp % 2 != p[m]:
                flag = False
                break
        if flag:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import bisect
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  
nl = lambda: list(map(int, stdin.readline().split()))

n, m = na()
l = []
for i in range(m):
    s = na()
    l.append(s[1::])
p = na()
ans = 0
for i in range(2**n):
    tmp = [0] * n
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            tmp[j] = 1
    for s, pi in zip(l, p):
        total = 0
        for si in s:
            if tmp[si-1]:
                total += 1
        if total % 2 != pi:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):
n, m = [int(_) for _ in input().split()]
l = []
for i in range(m):
    l.append([int(_) for _ in input().split()])
p_l = [int(_) for _ in input().split()]


ans = 0
for i in range(2**n):
    i_bin = format(i, '0' + str(n) + 'b')
    flag = True

    

    for i in range(m):

        

        k = l[i][0]

        

        c = 0
        for j in range(k):
            c += int(i_bin[l[i][j + 1] - 1])

            
            

        

        if c % 2 != p_l[i]:
            flag = False
            break

        

    if flag:
        ans += 1

    
print(ans)

Solution (Python):
n, m = map(int, input().split())
ls = []
for _ in range(m):
    k, *s, = map(lambda x: int(x)-1, input().split())
    ls.append(s)
p = list(map(int, input().split()))
ans = 0


def dfs(x, s):
    global ans
    if x == n:
        for j in range(m):
            switchs = ls[j]
            cond = p[j]
            on_cnt = 0
            for switch in switchs:
                if int(s[switch]):
                    on_cnt += 1
            if on_cnt % 2 != cond:
                break
        else:
            ans += 1
    else:
        for c in "01":
            dfs(x+1, s+c)


dfs(0, "")
print(ans)

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

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

ans = 0
for i in range(2**n):
    i = bin(i)[2:].zfill(n)
    for k, si in enumerate(s):
        on_n = 0
        for sik in si:
            on_n += int(i[sik - 1])
        if on_n % 2 != p[k]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
from itertools import product
n, m = map(int, input().split())
ls = []
for _ in range(m):
    k, *s, = map(lambda x: int(x)-1, input().split())
    ls.append(s)
p = list(map(int, input().split()))
it = ["01"]*n

ans = 0
for b in product(*it):
    base_2 = "".join(b)
    for j in range(m):
        switchs = ls[j]
        cond = p[j]
        on_cnt = 0
        for switch in switchs:
            if int(base_2[switch]):
                on_cnt += 1
        if on_cnt % 2 != cond:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
n, m = [int(i) for i in input().split()]
ss = []
for _ in range(m):
    s = [int(i)-1 for i in input().split()][1:]
    ss.append(s)
p = [int(i) for i in input().split()]

ans =0
for i in range(2 ** n):
    ok = True
    for j,k in zip(ss,p):
        l = 0
        for m in j:
            if (2 ** m) & i != 0:
                l += 1
        if l % 2 != k:
            ok = False


    if ok:
        ans += 1
print(ans)

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


def base_n(x, n, zero_padding=8):
    retval = [[], ['0']][x == 0]
    while x > 0:
        x, r = divmod(x, n)
        retval.append(str(r))
    cnt = zero_padding - len(retval)
    pad = ['', '0'*cnt][cnt > 0]
    return pad+''.join(retval[::-1])


ans = 0
for i in range(2**n):
    base_2 = base_n(i, 2, n)
    for j in range(m):
        switchs = ls[j]
        cond = p[j]

        on_cnt = 0
        for switch in switchs:
            if int(base_2[switch]):
                on_cnt += 1
        if on_cnt % 2 != cond:
            break

    else:
        ans += 1
print(ans)

Solution (Python):
n,m = map(int,input().split())
li = []
kli = []
for i in range(m):
    s = list(map(int,input().split()))
    k = s[0]
    kli.append(k)
    s.pop(0)
    li.append(s)
p = list(map(int,input().split()))
def judge():
    light = [0]*m
    for i in range(m):
        cnt = 0
        for j in range(kli[i]):
            if switch[li[i][j]-1] == 1:
                cnt += 1
        if cnt%2 == p[i]:
            light[i] = 1
    if sum(light) == m:
        return True
        
ans = 0
for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if (i>>j)&1:
            switch[n-1-j] = 1
    if judge():
        ans+=1
print(ans)

Solution (Python):

def main():
    N, M = map(int, input().split())
    ks = [list(map(int, input().split())) for _ in range(M)]
    p = list(map(int, input().split()))
    
    ans = 0

    for i in range(1<<N):
        isConflict = False

        for j in range(M):
            tmp = 0
            for k in ks[j][1:]:
                k -= 1
                tmp += (i>>k)
            if tmp%2 != p[j]:
                break
        else:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

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

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

ans=0  
for i in li1:
  light=True
  for j in range(m):
    cnt=0
    for k in range(1,ks[j][0]+1):
      if i[ks[j][k]-1]==1:
        cnt+=1
        
    if cnt%2!=p[j]:
      light=False
      
  if light:
    ans+=1
      
print(ans)

Solution (Python):
N, M = map(int,input().split())
right = {}
for i in range(M):
    li = list(map(int,input().split()))
    right[i] = li[1:]

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


ans = 0

for pattern in range(2**N):
    ri = 0
    for i, v in right.items():
        cnt = 0
        for sw in v:
            if pattern & (1 << (sw-1)) != 0:
                cnt += 1
        if cnt % 2  == p[i]:
            ri += 1

    if ri == M:
        ans += 1

print(ans)

Solution (Python):
n, m = map(int, input().split())
km = [0]*m
sm = [0]*m
for i in range(m):
    inp = input().split()
    km[i] = int(inp[0])
    sm[i] = list(map(int, inp[1:]))
    
pm = list(map(int, input().split()))

cnt = 0
for i in range(2**n):
    m_state = [0]*m
    for j in range(n):
        if (i>>j)&1:
            for k in range(m):
                if j+1 in sm[k]:
                    m_state[k]+=1
    all_flg = 1
    for x in range(m):
        if m_state[x]%2!=pm[x]:
            all_flg = 0
            break
    if all_flg:
        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()))

switch = [False] * n

def valid():
  for i, indices in enumerate(s):
    if sum((switch[index-1] for index in indices)) % 2 != p[i]:
      return False
  return True

cnt = 0
def dfs(start):
  global cnt
  if valid():
    cnt += 1  
  for i in range(start, n):
    if not switch[i]:
      switch[i] = True
      dfs(i+1)
      switch[i] = False
      
      
dfs(0)
print(cnt)

Solution (Python):
n, m = map(int, input().split())
ks = []
for i in range(m):
    ks.append(list(map(int, input().split())))
p = list(map(int, input().split()))
ans = 0
for i in range(1<<n):   
    all_flug = True
    for j in range(m):  
        cnt = 0
        for k in range(n):   
            
            if (i & (1<<k)) and (k+1 in ks[j][1:]):   
                cnt += 1
        
        
        if cnt % 2 != p[j]:
            all_flug = False
            
    
    if all_flug:
        ans += 1
print(ans)

Solution (Python):
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

sys.setrecursionlimit(10 ** 6)

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

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


def switch(bit, ans):
    check = [(bit >> i) & 1 for i in range(N)]
    light = 0
    for i in range(M):
        num = 0
        for l in s[i]:
            if check[l - 1] == 1:
                num += 1
        if num % 2 == p[i]:
            light += 1
    if light == M:
        ans += 1
    if bit == 1:
        return ans
    else:
        return switch(bit - 1, ans)


print(switch(2 ** N, 0))

Solution (Python):
N, M = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
blst = []
cnt = 0
for i in range(2 ** N):
    slst = []
    for j in range(N):
        if i >> j & 1:
            slst.append(j)
    blst.append(slst)

for i in blst:
    ansF = False
    for j in range(M):
        ctmp1 = 0
        for k in i:
            if ks[j][1:].count(k + 1) == 1:
                ctmp1 += 1
        if ctmp1 % 2 == p[j]:
            ansF = True
        else:
            ansF = False
            break
    if ansF:
        cnt += 1

print(cnt)

Solution (Python):
n, m = map(int, input().split())
s = [[int(i) for i in input().split()] for j in range(m)]
p = [int(i) for i in input().split()]
count = 0
for i in range(1 << n):
    light_bulbs = 0
    for j in range(m):
        on_switches = 0
        for k in range(s[j][0]):
            if (i >> s[j][k + 1] - 1) & 1:
                on_switches += 1
        if on_switches % 2 == p[j]:
            light_bulbs += 1
    if light_bulbs == m:
        count += 1
print(count)

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

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

ans = 2**N
for n in range(2**N):
  
  
  
  for i in range(M):
    
    
    hantei = 0
    for j in range(k[i]):
      hantei = hantei + ((n >> (s[i][j]-1))&1)

    if hantei%2 != p[i]:
      ans += -1
      break
print(ans)

Solution (Python):
N,M=map(int,input().split())
S=[[] for i in range(M)]
K=[]
for m in range(M):
     kS=[int(i) for i in input().split()]
     K.append(kS[0])
     for k in range(kS[0]):
         S[m].append(kS[k+1])
P=[int(i) for i in input().split()]


ans=0
for i in range(1<<N):
    on=set()
    for j in range(N):
        if ((i >> j) & 1) == 1:
            on.add(j+1)
    
    for m in range(M):
        on_num=0
        for k in range(K[m]):
            if S[m][k] in on:
                on_num+=1
        if on_num%2 != P[m]:
            break
        if m ==M-1:
            ans+=1
print(ans)

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

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

ans = 0
for bit in range(2**N):
    counts = [0] * M
    for i in range(N):
        if bit & 1<<i:
            for m in range(M):
                for s in k[m]:
                    if s-1 == i:
                        counts[m] += 1
    all = True
    for m in range(M):
        if counts[m] % 2 != p[m]:
            all = False
    if all:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
k = [input().split() for _ in range(M)]
p = list(map(int, input().split()))
ans = 0
for n in range(2 ** N):
    is_mismatch = False
    for i in range(M):
        cnt = 0
        for si in k[i][1:]:
            if (n >> (int(si) - 1)) & 1:
                cnt = (cnt + 1) % 2
        if cnt != p[i]:
            is_mismatch = True
            break
    if not is_mismatch:
        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()))
switch = [ [0] * m for i in range(n)]
ans = 0
for i in range(m):
         for j in range(1,len(ks[i])):
                  switch[ks[i][j]-1][i] += 1
for i in range(2 ** n):
         lampcount = [ 0 ] * m
         for j in range(n):
                  if ((i >> j) & 1):
                           for k in range(m):
                                    if switch[j][k] == 1:
                                             lampcount[k] += 1
         for l in range(m):
                  lampcount[l] = lampcount[l] % 2
         if lampcount == p:
                  ans += 1
print(ans)

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

ans = 0

for i in range(2 ** n):
    b = bin(i)
    sb = str(b)[2:].zfill(n)
    onoff = list(sb)

    cnt = [0] * m

    for j in range(m):
        for k in lss[j][1:]:
            if onoff[k - 1] == '1':
                cnt[j] += 1
    
    for l in range(m):
        if cnt[l] % 2 == lsp[l]:
            if l == m - 1:
                ans += 1
        elif cnt[l] % 2 != lsp[l]:
            break

print(ans)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
ks = [LIST() for _ in range(m)]
p = LIST()
ans = 0
for i in range(2 ** n):
    bit = format(i, 'b').zfill(n)
    flag = True
    for j in range(m):
        k = ks[j][0]
        s = ks[j][1:]
        tmp = 0
        for l in s:
            tmp += int(bit[l - 1])
        if tmp % 2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):
N, M = map(lambda x: int(x), input().split())
mask_list = []
for i in range(M):
    ks = list(map(lambda x: int(x), input().split()))
    k, s = ks[0], ks[1:]
    mask = 0
    for j in s:
        mask += (1 << (j - 1))
    mask_list.append(mask)
p_list = list(map(lambda x: int(x), input().split()))

count = 0
for i in range(2 ** N):
    tmp = 1
    for j in range(M):
        def count_bit(val):
            result = 0
            while val > 0:
                result += val & 1
                val = val >> 1
            return result
        if count_bit(i & mask_list[j]) % 2 != p_list[j]:
            tmp = 0
            break
    count += tmp
print(count)

Solution (Python):
def inpl(): return list(map(int, input().split()))
N, M = inpl()
L = [0]*M
for i in range(M):
    for s in inpl()[1:]:
        L[i] += pow(2, s-1)
P = inpl()
print(sum([sum([bin(L[j]&i).count("1")%2 == P[j] for j in range(M)]) == M for i in range(pow(2, N))]))

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

ans=0

for i in range(2**n):
    B=[]
    b=format(i,'b')
    b=b.zfill(n)
    for j in range(n):
        B.append(int(b[j]))
    flag=True
    for k in range(m):
        cnt=0
        for l in range(X[k][0]):
            cnt+=B[X[k][l+1]-1]
        if cnt%2!=P[k]:
            flag=False
    if flag:
        ans+=1
        
print(ans)

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

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

for i in range(2 ** N):
    on = []
    for j in range(N):
        if i >> j & 1 == 1:
            on.append(N - j)
    for i in range(M):
        if len(set(on) & set(S[i])) % 2 != P[i]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
def main():
    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()))

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


if __name__ == '__main__':
    main()

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

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


if __name__ == '__main__':
    main()

Solution (Python):
def ma():
  import sys
  input = sys.stdin.readline
  n,m=map(int,input().split())
  ans=0
  e=[set(list(map(int,input().split()))[1:]) for i in range(m)]
  f=list(map(int,input().split()))
  for i in range(2**n):
    l={a for a,b in zip(range(1,n+1),bin(i)[2:].zfill(n)) if b=="1"}
    for j in range(1,m+1):
      if len(e[j-1]&l)%2!=f[j-1]:break
    else:ans+=1
  print(ans)

if __name__=="__main__":
  ma()

Solution (Python):
def ma():
  n,m=map(int,input().split())
  ans=0
  e=[ ]
  for i in range(m):
    e.append(set(list(map(int,input().split()))[1:]))
  f=list(map(int,input().split()))
  for i in range(2**n):
    l=set()
    for a,b in zip(range(1,n+1),bin(i)[2:].zfill(n)) :
      if b=="1":l.add(a)
    for j in range(1,m+1):
      if int(len(e[j-1]&l)%2!=f[j-1]):break
    else:ans+=1
  print(ans)

if __name__=="__main__":
  ma()

Solution (Python):
def ma():
  n,m=map(int,input().split())
  ans=0
  e=[set(list(map(int,input().split()))[1:]) for i in range(m)]
  f=list(map(int,input().split()))
  for i in range(2**n):
    l={a for a,b in zip(range(1,n+1),bin(i)[2:].zfill(n)) if b=="1"}
    if sum({int(len(e[j-1]&l)%2 !=f[j-1]) for j in range(1,m+1)})==0:ans+=1
  print(ans)

if __name__=="__main__":
  ma()

Solution (Python):
def ma():
  n,m=map(int,input().split())
  ans=0
  e=[set(list(map(int,input().split()))[1:]) for i in range(m)]
  f=list(map(int,input().split()))
  for i in range(2**n):
    l={a for a,b in zip(range(1,n+1),bin(i)[2:].zfill(n)) if b=="1"}
    if sum({int(len(e[j-1]&l)%2 !=f[j-1]) for j in range(1,m+1)})==0:ans+=1
  print(ans)

if __name__=="__main__":
  ma()

Solution (Python):
def ma():
  n,m=map(int,input().split())
  ans=0
  e=[set(list(map(int,input().split()))[1:]) for i in range(m)]
  f=list(map(int,input().split()))
  for i in range(2**n):
    l={a for a,b in zip(range(1,n+1),bin(i)[2:].zfill(n)) if b=="1"}
    if sum([int(len(e[j-1]&l)%2 !=f[j-1]) for j in range(1,m+1)])==0:ans+=1
  print(ans)

if __name__=="__main__":
  ma()

Solution (Python):
def ma():
  n,m=map(int,input().split())
  ans=0
  e=[set(list(map(int,input().split()))[1:]) for i in range(m)]
  f=list(map(int,input().split()))
  for i in range(2**n):
    l={a for a,b in zip(range(1,n+1),bin(i)[2:].zfill(n)) if b=="1"}
    for j in range(1,m+1):
      if len(e[j-1]&l)%2!=f[j-1]:break
    else:ans+=1
  print(ans)

if __name__=="__main__":
  ma()

Solution (Python):
n,m=map(int,input().split())
ans=0
e=[set(list(map(int,input().split()))[1:]) for i in range(m)]
f=list(map(int,input().split()))
for i in range(2**n):
  l={a for a,b in zip(range(1,n+1),bin(i)[2:].zfill(n)) if b=="1"}
  for j in range(1,m+1):
    if len(e[j-1]&l)%2!=f[j-1]:break
  else:ans+=1
print(ans)

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

for i in range(m):
    a = list_data[i]
    a.pop(0)

ans = 0

for i in range(2**n):
    list_ans = [0] * m
    for l in range(m):
        for j in range(n):
            if ((i >> j) & 1):
                if j+1 in list_data[l]:
                    list_ans[l] += 1
    a = list(map(lambda x:x % 2, list_ans))
    if a == list_condition:
        ans += 1

print(ans)

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

k = []
s = []
for i in range(len(ks)):
    k.append(ks[i][0])
    s.append(ks[i][1:])

ans = 0
for x in itertools.product([0, 1], repeat=N):
    total = 0
    for i in range(M):
        count = 0
        for j in range(k[i]):
            if x[s[i][j]-1]:
                count += 1
        if p[i] == count % 2:
            total += 1
    if total == M:
        ans += 1
print(ans)

Solution (Python):




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

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

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

    cnt = 0

    for i in range(2 ** N):
        bin_i = '{:010b}'.format(i)[::-1]

        for i in range(M):
            ks = KSS[i]
            k = ks[0]
            s = ks[1:]

            sum_s = 0

            for j in range(k):
                sum_s += int(bin_i[s[j] - 1])

            if sum_s % 2 != P[i]:
                break
        else:
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):
import math
n,m = map(int, input().split())
switch = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int, input().split()))
count = 0
for j in range(2**n):

    flag = True
    for i in range(m):
        on = 0
        for k in switch[i][1:]:
            if (j >> k-1) & 1:
                on += 1
        if on % 2 != p[i]:
            flag = False
            
    if flag:
        count +=1
print(count)

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

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

on_offs = [i for i in range(2 ** n)]

count = 0
for i in range(2 ** n):
    ng = False
    for p, s_list in zip(values, switches):
        
        on_count = 0
        
        for s in s_list:
            if (i >> (s - 1)) & 1:
                
                on_count += 1
        
        if on_count % 2 != p:
            ng = True
            break
    if not ng:
        
        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()))

res = 0

for i in range(2**N):
    sw = []
    for j in range(N):
        if (i>>j) & 1:
            sw.append(True)
        else:
            sw.append(False)
    for j in range(M):
        c = 0
        for y in s[j]:
            if sw[y-1]:
                c += 1
        if c%2 != p[j]:
            break
    else:
        res += 1

print(res)

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

for i in range(m):
    a = list_data[i]
    a.pop(0)

ans = 0

for i in range(2**n):
    list_ans = [0] * m
    for l in range(m):
        for j in range(n):
            if ((i >> j) & 1):
                if j+1 in list_data[l]:
                    list_ans[l] += 1
    a = list(map(lambda x:x % 2, list_ans))
    if a == list_condition:
        ans += 1

print(ans)

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

for bit in range(2 ** n):
	ans = []
	for i in range(n):
		if (bit >> i) & 1:
			ans.append(1)
		else:
			ans.append(0)
	
	f = [0] * m
	for j in range(len(ks)):
		b = 0
		for i in ks[j][1:]:
			if ans[i-1] == 1:
				b += 1

		if b % 2 == p[j]:
			f[j] = 1

	if f.count(1) == len(ks):
		c += 1
	
print(c)

Solution (Python):
N, M = map(int, input().split())
switches = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
ans = 0
for i in range(2 ** N):
    tmp = [0]*N
    for k in range(N):
        if 1 & i>>k:
            tmp[k] = 1
    flg = True
    for k in range(M):
        count = 0
        for l in range(1,switches[k][0]+1):
            if tmp[switches[k][l]-1] == 1:
                count += 1
        if count % 2 != p[k]:
            flg = False
    if flg:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
b = [None] * m
for i in range(m):
    _, *b[i] = map(lambda x: int(x)-1, input().split())
p = list(map(int, input().split()))
ans = 0
for x in range(2**n):
    light = 0
    for i, j in enumerate(b):
        switch = 0
        for k in j:
            switch += x >> k & 1
        if switch % 2 == p[i]:
            light += 1
    if light == m:
        ans += 1
print(ans)