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 sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import product
def main():
    n, m = map(int, input().split())
    light_bulbs = {i: [] for i in range(m)}
    for i0 in range(m):
        data = tuple(map(int, input().split()))
        light_bulbs[i0]= data[1:]
    p = tuple(map(int, input().split()))

    pat = tuple(product((0, 1), repeat=n))
    res = 0
    for pate in pat:
        light_on = 0
        for i, bulb in enumerate(light_bulbs.values()):
            turned_switch = 0
            for bulb_switch in bulb:
                turned_switch += pate[bulb_switch - 1]
            if turned_switch % 2 == p[i]:
                light_on += 1
        if light_on == m:
            res += 1
    print(res)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def read(): return sys.stdin.readline() 
def fbit(i, j=-1): return format(i, 'b').zfill(j) 
def popcount(x): 
    x=x-((x>>1)&0x5555555555555555)
    x=(x&0x3333333333333333)+((x>>2)&0x3333333333333333)
    x=(x+(x>>4))&0x0f0f0f0f0f0f0f0f;x=x+(x>>8);x=x+(x>>16);x=x+(x>>32)
    return x&0x0000007f


def solv(N:int, M: int, k:list, s: list, p: list):
    ans = 0
    for bits in range(1<<N):
        flag = True
        for i in range(M):
            mask = 0
            for j in s[i]:
                mask = mask|1<<(j-1)
            if not popcount(bits&mask)%2==p[i]: flag = False
        if flag: ans += 1
    print(ans)

def main():
    [N, M] = list(map(int, read().rsplit()))
    k = []; s = []
    for i in range(M):
        _tmp = list(map(int, read().rsplit()))
        k.append(_tmp.pop(0))
        s.append(_tmp)

    p = list(map(int, read().rsplit()))
    solv(N, M, k, s, p)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
def read(): return sys.stdin.readline() 
def fbit(i, j=-1): return format(i, 'b').zfill(j) 
def popcount(x): 
    x=x-((x>>1)&0x5555555555555555)
    x=(x&0x3333333333333333)+((x>>2)&0x3333333333333333)
    x=(x+(x>>4))&0x0f0f0f0f0f0f0f0f;x=x+(x>>8);x=x+(x>>16);x=x+(x>>32)
    return x&0x0000007f


def solv(N:int, M: int, k:list, s: list, p: list):
    ans = 0
    for bits in range(1<<N): 
        
        
        flag = True
        for i in range(M): 
            
            mask = 0
            
            for j in s[i]:
                mask = mask|1<<(j-1)
            
            
            if not popcount(bits&mask)%2==p[i]: flag = False
        if flag: ans += 1
    print(ans)

def main():
    [N, M] = list(map(int, read().rsplit()))
    k = []; s = []
    for i in range(M):
        _tmp = list(map(int, read().rsplit()))
        k.append(_tmp.pop(0))
        s.append(_tmp)

    p = list(map(int, read().rsplit()))
    solv(N, M, k, s, p)


if __name__ == '__main__':
    main()



2&3

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

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

s_lst = [[False] * N for _ in range(M)]
for i in range(M):
    ks = list(map(int, input().split()))
    for j, value in enumerate(ks):
        if j != 0:
            s_lst[i][value-1] = True
p = list(map(int, input().split()))


ans = 0
for bit in range(2**N):
    cnt = [0] * M
    for i in range(N):
        if (bit>>i) & 1 == 1:
            for j in range(M):
                if s_lst[j][i]:
                    cnt[j] += 1
    flug = True
    for i in range(M):
        if cnt[i] % 2 != p[i]:
            flug = False
    if flug:
        ans += 1
print(ans)

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

smi = [ None ] * m

for i in range(m):
    k, *si = map(lambda x: int(x) - 1, input().split())

    smi[i] = si

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

def emitable(bit_pattern, i):
    si = smi[i]
    px = pi[i]
    py = 0

    for s in si:
        py += (bit_pattern & (2 ** s)) >> s

    return px == (py % 2)

count = 0

for bi in range(2 ** n):
    if all(emitable(bi, i) for i in range(m)):
        count += 1

print(count)

Solution (Python):
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(' ')))
ans = 0
for i in range(2**n):
    light = 0
    for j in range(m):
        sw = 0
        for s in S[j]:
            if (i>>(s-1))&1:
                sw += 1
        if sw%2 == p[j]:
            light+=1
    if light == m:
        ans += 1
print(ans)

Solution (Python):
N, M = list(map(int, input().split()))
S = [0]*M
answer = 0

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

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

for i in range(2**N):
    mb = '0' + str(N) + 'b'
    bi = format(i, mb)
    count = 0
    for j in range(M):
        on = 0
        for k in range(S[j][0]):
            on += int(bi[-S[j][k+1]])
        if on%2 == P[j]:
            count += 1
    if count == M:
        answer += 1

print(answer)

Solution (Python):
n, m = map(int, input().split())
l = [[0]*n for _ in range(m)]
for i in range(m):
  k, *s = map(int, input().split())
  for j in range(k):
    l[i][s[j]-1] = 1
p = list(map(int, input().split()))

ans = 0
str = '{:0'+str(n)+'b}'
for i in range(2**n):
  s = list(map(int, str.format(i)))
  b = True
  for j in range(m):
    if sum([x & y for x, y in zip(s, l[j])]) % 2 != p[j]:
      b = False
  if b:
    ans += 1

print(ans)

Solution (Python):


from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key
from bisect import bisect_left


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


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

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

def bindex(a,x):
    i = bisect_left(a,x)
    if i != len(a) and a[i] == x:
        return i
    return None


class UnionFind:
    def __init__(self, n):
        self.r = [-1]*(n+1)

    def root(self, x):
        if self.r[x] < 0:
            return x
        self.r[x] = self.root(self.r[x])
        return self.r[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.r[x] > self.r[y]:
            x,y = y,x
        self.r[x] += self.r[y]
        self.r[y] = x
        return True

    def size(self, x):
        return -1 * self.r[self.root(x)]


class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N, M = mulinputs()
    ks, ss, ps = [], [], []
    for _ in range(M):
        k, *s = list(mulinputs())
        ks.append(k)
        ss.append(s)
    ps = list(mulinputs())

    cnt = 0
    for n in range((1<<N)):
        state = [0] * N
        for j in range(N):
            state[j] = (n&(1<<j))>>j
        is_light = True
        for j in range(M):
            icnt = 0
            for s in ss[j]:
                icnt += state[s-1]
            if icnt%2 != ps[j]:
                is_light = False
                break
        if is_light:
            cnt+=1

    
    print(cnt)

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):
    s = i
    b = [0]*N
    for j in range(N):
        if s >= (2**(N-j-1)):
            s -= 2**(N-j-1)
            b[j] = 1
    for j in range(M):
        on = 0
        for k in range(ks[j][0]):
            if b[ks[j][k+1]-1] == 1:
                on += 1
        if on%2 != p[j]:
            break
    else:
        ans += 1
print(ans)

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

from itertools import product
iterator=product(range(p),repeat=n)

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

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

ans=0
for idxs in iterator:
    tmp1=0
    for i in range(m):
        tmp2=0
        for j in s[i]:
            tmp2+=idxs[j-1]
        if tmp2%2==p[i]:
            tmp1+=1
    if tmp1==m:
        ans+=1
print(ans)

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

from itertools import product

ans = 0
for a in product([0,1],repeat=n):
    for j,l in enumerate(li):
        t = 0
        for k in l[1:]:
            t += a[k-1]
        t %= 2
        if t != p[j]:break
    else:
        ans += 1

print(ans)

Solution (Python):

import sys
input = lambda: sys.stdin.readline().strip()
n, m = [int(x) for x in input().split()]
s = [[int(x) - 1 for x in input().split()][1:] for i in range(m)]
p = [int(x) for x in input().split()]
print(sum(1 for mask in range(1 << n) if all(sum((mask >> bulb) & 1 for bulb in s[i]) % 2 == p[i] for i in range(m))))

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

input_row = lambda : [int(_) for _ in input().split(' ')]

N, M = input_row()
C = np.zeros((M, N), dtype=np.int32)

for i in range(M):
    s = np.array(input_row()[1:]) 
    C[i, s-1] = 1 

p = input_row()

all_on_num = 0
for S_ in product(*(repeat([1, 0], N))):
    S = np.array(S_)

    L = C.dot(S)%2 == p

    if len(L[L == True]) == M:
        all_on_num += 1
print(all_on_num)

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

input_row = lambda : [int(_) for _ in input().split(' ')]

N, M = input_row()
C = np.zeros((M, N), dtype=np.int32)

for i in range(M):
    s = input_row()[1:]
    for s_ in s:
        C[i, s_-1] = 1

p = input_row()

all_on_num = 0

for S_ in product(*(repeat([1, 0], N))):
    S = np.array(S_)

    L = C.dot(S)%2 == p
    L_on = L[L == True]
    all_on = len(L_on) == M

    if all_on:
        all_on_num += 1
print(all_on_num)

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))




n,m=MI()
lights=[LI() for _ in range(m)]
p_list=LI()

bit_list=[]
count=0
for i in range(2**n):
    bit = [i>>j&1 for j in range(n)]
    flag=0
    for j in range(m):
        ki=lights[j][0]
        onswitch=0
        for k in range(1,ki+1):
            si=lights[j][k]
            onswitch+=bit[si-1]
        if onswitch%2!=p_list[j]:
            flag+=1
    if flag==0:
        count+=1
print(count)

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

ans = 0
for i in range(1<<N):
    ri_count = 0
    for j in range(M):
        sw_count = 0
        for l in range(k[j]):
            if i>>(s[j][l]-1) & 1:
                sw_count += 1
        if sw_count%2 == p[j]:
            ri_count += 1
    if ri_count == M:
        ans += 1
print(ans)

Solution (Python):

n, m = map(int, input().split(' '))
k = []
s = []
for i in range(m):
    a = list(map(int, input().split(' ')))
    k.append(a[0])
    s.append(a[1:])
p = list(map(int, input().split(' ')))
ans = 0
for i in range(2**n):
    ri_cnt = 0
    for j in range(m):
        sw_cnt = 0
        for l in range(k[j]):
            if (i >> (s[j][l]-1)) & 1:
                sw_cnt += 1
        if sw_cnt % 2 == p[j]:
            ri_cnt += 1
    if ri_cnt == m:
        ans += 1
print(ans)

Solution (Python):

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

ans = 0
for i in range(1<<N):
    swiches = [0]*N
    for j in range(N):
        mask = 1<<j
        
        if i & mask != 0:
            swiches[j] = 1
        
        else:
            continue

    
    cnt_light = 0
    for m in range(M):
        cnt_swich = 0
        for s in S[m]:
            if swiches[s] == 1:
                cnt_swich += 1
        if cnt_swich%2 == P[m]:
            cnt_light += 1
    if cnt_light == M:
        ans += 1
print(ans)

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

ans=0

for i in range(2**n):
    All_On=True
    for j in range(m):
        k_on=0
        for k in range(1,lamp[j][0]+1):
            if i>>lamp[j][k]-1 & 1:
                k_on+=1
        if k_on%2!=p[j]:
            All_On=False
            break
    if All_On:
        ans+=1
print(ans)

Solution (Python):

import itertools




INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,m=INTM()
    cnct=[]
    for i in range(m):
        temp=LIST()
        temp=temp[1:]
        cnct.append(temp)
    ps=LIST()
    ans=0
    
    for bit in range(2**n):
        check=[0]*m
        for i in range(n):
            if (bit>>i)&1:
                for k in range(m):
                    if i+1 in cnct[k]:
                        check[k]+=1
        
        flg=True
        for k in range(m):
            if check[k]%2!=ps[k]:
                flg=False
        
        if flg:
            ans+=1
    
    print(ans)


if __name__=='__main__':
    do()

Solution (Python):
N,M = map(int,input().split())
mat = [[int(i) for i in input().split()] for k in range(M)]
p = [int(i) for i in input().split()]
switch = [0]*N
O = [0]*M
L = [False]*M
ans = 0

for i in range(2 ** (N)):
    switchsub = list(format(i,'b'))
    for j in range(len(switchsub)):
        switch[-j-1] = switchsub[-j-1]
    for j in range(N):
        if(switch[j] == "1"):
            for k in range(M):
                for l in range(1,len(mat[k])):
                    if(mat[k][l] == j+1):
                        O[k] += 1
    for j in range(M):
        if(O[j] % 2 == p[j]):
            L[j] = True
    if(False not in L):
        ans += 1
        switch = [0]*N
        O = [0]*M
        L = [False]*M
    if(False in L):
        switch = [0]*N
        O = [0]*M
        L = [False]*M

print(ans)

Solution (Python):



N, M = (int(x) for x in input().split())

S = []
for i in range(M):
    S.append([int(x)-1 for x in input().split()][1:])
P = [int(x) for x in input().split()]

ret = 0
for bit in range(2**N):
    on = [i for i in range(N) if bit & (1 << i)]
    if all(sum(1 for switch in S[i] if switch in on) % 2 == P[i] for i in range(M)):
        ret += 1
print(ret)

Solution (Python):



N, M = (int(x) for x in input().split())

S = []
for i in range(M):
    items = [int(x)-1 for x in input().split()]
    S.append(items[1:])

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

ret = 0
for bit in range(2**N):
    on = [i for i in range(N) if bit & (1 << i)]
    ok = True
    for i in range(M):
        s = S[i]
        p = P[i]
        if sum(1 for switch in s if switch in on) % 2 != p:
            ok = False
            break
    if ok:
        ret += 1
print(ret)

Solution (Python):



import sys

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

k = []
s = []

for i in range(M):
    _k, *_s = map(int, input().split())
    k.append(_k)
    s.append(_s)

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


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

    for m in range(M):
        mod = 0
        for switch in s[m]:
            mod += sw[switch - 1]
        if mod % 2 != p[m]:
            break
    else:
        ans += 1

print(ans)

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

ans=0
for i in range(2**n):
    sw=[]
    on=0
    for j in range(n):
        sw.append(i>>j & 1)
    for k in range(m):
        if (sum( [sw[ks[k][j+1]-1] for j in range(ks[k][0])] ))%2 == p[k]:
            on +=1
    if on==m:
        ans +=1
print(ans)

Solution (Python):
import math
N, M = map(int, input().split())
switch = [0] * N
pattern = 2 ** N
ans = 0
for i in range(M):
  temp = input().split()[1:]
  for j in temp:
    switch[int(j) - 1] += (1 << i )
  
p = list(map(int, input().split()))
pbin = 0
temp = 1
for i in p:
  pbin += i * temp
  temp *= 2

for i in range(pattern):
  temp = 0
  j = 0
  while i > 0:
    if i & 1 == 1 :
      temp = temp ^ switch[j]
    j += 1
    i = i >> 1
  if pbin == temp:
    ans += 1
print(ans)

Solution (Python):
def light(l,i):
    k=1<<(i-1)
    if l&k:
        return 1
    else:
        return 0

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

a=0
for l in range(0,1<<N):
    b=0
    for j in range(0,M):
        c=0
        for i in range(1,s[j][0]+1):
            c+=light(l,s[j][i])
        if c%2==p[j]:
            b+=1
    if b==M:
        a+=1
print(a)

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

Solution (Python):
n, m = map(int,input().split())
k, s = [], []
for i in range(m):
  inp = list(map(int, input().split()))
  k_, s_ = inp[0], inp[1:]
  k.append(k_)
  s.append(s_)
p = list(map(int, input().split()))
ans = 0
for bit in range(1<<n):
  flg = True
  for i in range(m):
    cnt = 0
    for e in s[i]:
      e -= 1
      if bit & 1<<e: cnt += 1
    if cnt%2 != p[i]: flg = False
  if flg: ans += 1
print(ans)

Solution (Python):


def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

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

    ans = 0
    for i in range(2**N, 2**(N+1)):
        b = bin(i)[3:]
        t = [0] * M
        for j, sj in enumerate(s):
            for k, bi in enumerate(list(b)):
                if bi == '1' and k+1 in sj:
                    t[j] += 1
            if t[j] % 2 != p[j]:
                ans -= 1
                break
        ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from itertools import combinations

def getval():
    n,m = map(int,input().split())
    s = [list(map(int,input().split())) for i in range(m)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            s[i][j] -= 1
    p = list(map(int,input().split()))
    return n,m,s,p 

def main(n,m,s,p):
    l = [[] for i in range(n)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            l[s[i][j]].append(i)
    ans = 0
    for i in range(n+1):
        for c in combinations(range(n),i):
            temp = [0 for i in range(m)]
            for j in c:
                for k in l[j]:
                    temp[k] += 1
                    temp[k] %= 2
            if temp==p:
                ans += 1
    print(ans)

if __name__=="__main__":
    n,m,s,p = getval()
    main(n,m,s,p)

Solution (Python):
from itertools import combinations

def getval():
    n,m = map(int,input().split())
    s = [list(map(int,input().split())) for i in range(m)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            s[i][j] -= 1
    p = list(map(int,input().split()))
    return n,m,s,p 

def main(n,m,s,p):
    l = [[] for i in range(n)]
    for i in range(m):
        for j in range(1,s[i][0]+1):
            l[s[i][j]].append(i)
    ans = 0
    for i in range(n+1):
        for c in combinations(range(n),i):
            temp = [0 for i in range(m)]
            for j in c:
                for k in l[j]:
                    temp[k] += 1
                    temp[k] %= 2
            if temp==p:
                ans += 1
    print(ans)

if __name__=="__main__":
    n,m,s,p = getval()
    main(n,m,s,p)

Solution (Python):
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 i in range(2**n):
    bit = [i>>j&1 for j in range(n)]
    for j,k in enumerate(K):
        if p[j] != sum([bit[l-1] for l in k])%2:
            break
    else:
        ans += 1
print(ans)

Solution (Python):




import sys
from io import StringIO
import unittest
from collections import deque


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2 2
2 1 2
1 2
0 1"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2 3
2 1 2
1 1
1 2
0 0 1"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5 2
3 1 2 5
2 2 3
1 0"""
        output = """8"""
        self.assertIO(input, output)


def resolve_bit():
    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 bit in range(1 << N):
        m = 0
        for i in range(M):
            t = 0
            for j in range(1, S[i][0]+1):
                if bit & (1 << (S[i][j]-1)):
                    t += 1
            if t % 2 != P[i]:
                break
            else:
                m += 1
        if m == M:
            ans += 1
    print(ans)


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

    ONS = deque()
    print(dfs(0, ONS))


def dfs(n, T):
    if n == N:
        onm = 0
        for i, ks in enumerate(KS):
            k, s = ks[0], ks[1:]
            onsn = 0
            for t in T:
                if t in s:
                    onsn += 1
            if onsn % 2 != P[i]:
                break
            else:
                onm += 1
        if onm == M:
            return 1
        else:
            return 0

    ans = 0
    T.append(n+1)
    ans += dfs(n+1, T)
    T.pop()
    ans += dfs(n+1, T)
    return ans


if __name__ == "__main__":
    
    resolve()

Solution (Python):
import itertools
N,M = map(int,input().split())
Switch = []
for i in range(M):
    Swi = list(map(int,input().split()))
    S = Swi[0]
    Switch.append(Swi[1:S+1])
Plist = list(map(int,input().split()))
Ans = 0
L = [0,1]
c_list = list(itertools.product(L, repeat=N))
for comb in c_list:
    for i in range(M):
        Jud = 0
        Swi = Switch[i]
        for j in Swi:
            Jud += comb[j-1]
        if Jud%2 != Plist[i]:
            break
        elif i == M-1:
            Ans += 1
print(Ans)

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

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

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

ans=0
for i in range(2**N):
  isOK=True
  for j in range(M):
    stat=0
    for k in l[j]:
      k-=1
      if i&(1<<k):
        stat=(stat+1)%2
    if stat!=p[j]:
      isOK=False
  if isOK:
    ans+=1
print(ans)

Solution (Python):
N, M = list(map(int,input().split()))
K_and_Ss = []
for i in range(M):
    data = list(map(int,input().split()))
    K_and_Ss.append(data)
Ps = list(map(int,input().split()))

flag = False
x = 2**N
sum = 0
for i in range(x):
    for j in range(M): 
        count = 0
        if flag:
            flag = False
            break
        for k in range(len(K_and_Ss[j])-1):
            if (i >> (K_and_Ss[j][k+1]-1) & 1) == 1:
                count += 1
            if k ==len(K_and_Ss[j])-2 and count % 2 == Ps[j]:
                flag = False
                if j == M-1:
                    sum += 1
            if k ==len(K_and_Ss[j])-2 and count % 2 != Ps[j] and j != M-1:
                flag = True
print(sum)

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

from itertools import product
candidate = list(product([0,1], repeat=N))

ans = 0
for cand in candidate:
  flag = True
  for idx, snum in enumerate(switch):
    tmp = 0
    for s in snum:
      tmp += cand[s-1]
    if p[idx] != tmp%2:
      flag = False
      break
  if flag:
    ans += 1
print(ans)

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