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



Sample input:
2 2
2 1 2
1 2
0 1


Sample output:
1

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[]
for _ in range(m):
    kari=list(map(int,input().split()))
    l.append(kari)
p=list(map(int,input().split()))
num2=[]
def deal1():
    ans=0
    for a in range(2):
        w=[a]
        all=0
        for k in range(m):
            cnt==0
            for q in range(l[k][0]):
                if w[l[k][q+1]-1]==1:
                    cnt+=1
            if p[k]==cnt%2:
                all+=1
        if all==m:
            ans+=1
    return ans
def deal2():
    ans=0
    for a in range(2):
        for b in range(2):
            w=[a,b]
            all=0
            for k in range(m):
                cnt=0
                for q in range(l[k][0]):
                    if w[l[k][q+1]-1]==1:
                        cnt+=1
                if p[k]==cnt%2:
                    all+=1
            if all==m:
                ans+=1
    return ans
def deal3():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                w=[a,b,c]
                all=0
                for k in range(m):
                    cnt=0
                    for q in range(l[k][0]):
                        if w[l[k][q+1]-1]==1:
                            cnt+=1
                    if p[k]==cnt%2:
                        all+=1
                if all==m:
                    ans+=1
    return ans
def deal4():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    w=[a,b,c,d]
                    all=0
                    for k in range(m):
                        cnt=0
                        for q in range(l[k][0]):
                            if w[l[k][q+1]-1]==1:
                                cnt+=1
                        if p[k]==cnt%2:
                            all+=1
                    if all==m:
                        ans+=1
    return ans
def deal5():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        w=[a,b,c,d,e]
                        all=0
                        for k in range(m):
                            cnt=0
                            for q in range(l[k][0]):
                                if w[l[k][q+1]-1]==1:
                                    cnt+=1
                            if p[k]==cnt%2:
                                all+=1
                        if all==m:
                            ans+=1
    return ans
def deal6():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            w=[a,b,c,d,e,f]
                            all=0
                            for k in range(m):
                                cnt=0
                                for q in range(l[k][0]):
                                    if w[l[k][q+1]-1]==1:
                                        cnt+=1
                                if p[k]==cnt%2:
                                    all+=1
                            if all==m:
                                ans+=1
    return ans
def deal7():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            for g in range(2):
                                w=[a,b,c,d,e,f,g]
                                all=0
                                for k in range(m):
                                    cnt=0
                                    for q in range(l[k][0]):
                                        if w[l[k][q+1]-1]==1:
                                            cnt+=1
                                    if p[k]==cnt%2:
                                        all+=1
                                if all==m:
                                    ans+=1
    return ans
def deal8():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            for g in range(2):
                                for h in range(2):
                                    w=[a,b,c,d,e,f,g,h]
                                    all=0
                                    for k in range(m):
                                        cnt=0
                                        for q in range(l[k][0]):
                                            if w[l[k][q+1]-1]==1:
                                                cnt+=1
                                        if p[k]==cnt%2:
                                            all+=1
                                    if all==m:
                                        ans+=1
    return ans
def deal9():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            for g in range(2):
                                for h in range(2):
                                    for i in range(2):
                                        w=[a,b,c,d,e,f,g,h,i]
                                        all=0
                                        for k in range(m):
                                            cnt=0
                                            for q in range(l[k][0]):
                                                if w[l[k][q+1]-1]==1:
                                                    cnt+=1
                                            if p[k]==cnt%2:
                                                all+=1
                                        if all==m:
                                            ans+=1
    return ans

def deal10():
    ans=0
    for a in range(2):
        for b in range(2):
            for c in range(2):
                for d in range(2):
                    for e in range(2):
                        for f in range(2):
                            for g in range(2):
                                for h in range(2):
                                    for i in range(2):
                                        for j in range(2):
                                            w=[a,b,c,d,e,f,g,h,i,j]
                                            all=0
                                            for k in range(m):
                                                cnt=0
                                                for q in range(l[k][0]):
                                                    if w[l[k][q+1]-1]==1:
                                                        cnt+=1
                                                if p[k]==cnt%2:
                                                    all+=1
                                            if all==m:
                                                ans+=1
    return ans
if n==1:
    print(deal1())
if n==2:
    print(deal2())
if n==3:
    print(deal3())
if n==4:
    print(deal4())
if n==5:
    print(deal5())
if n==6:
    print(deal6())
if n==7:
    print(deal7())
if n==8:
    print(deal8())
if n==9:
    print(deal9())
if n==10:
    print(deal10())

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0

for switch in product([True, False], repeat=N):
    for b, p in zip(B, P):
        if sum([switch[b[i]-1] for i in range(1, len(b))]) % 2 == int(p):
            pass
        else:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

def is_light(sw_conn, sw_status, p):
    num_on = 0
    for sw in sw_conn:
        if sw_status[sw] == 1:
            num_on += 1
    return num_on % 2 == p

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

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

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

ans = 0
for sw_status in product(range(2), repeat=N):
    lights = []
    for j in range(M):
        lights.append(is_light(sw_conn[j], sw_status, p[j]))
    if all(lights):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
sw=[]
for i in range(2**n):
    l=list(str(bin(i)))
    t=n-len(l[2:])
    if t!=0:
        L=['0'*t]+l[2:]
    else:
        L=l[2:]
    sw.append(''.join(L))

S=[]
K=[]
for i in range(m):
    a=[int(i) for i in input().split()]
    K.append(a[0])
    s=a[1:]
    S.append(s)
p=[int(i) for i in input().split()]

for j in range(m):
    SW=[]
    for h in sw:
        s=0
        for i in range(K[j]):
            if h[S[j][i]-1]=='1':
                s+=1
        if s%2==p[j]:
            SW.append(''.join(h))
    sw=set(sw)&set(SW)

    
print(len(sw))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l =[]
pl = []
for i in range(m):
  l.append(list(int(i) for i in input().split()))
pl= list((int(i) for i in input().split()))
cnt = 0
sw = [0]*n
for i in range(2**n):
  sw = list(format(i,"b"))
  while len(sw) < n:
    sw.insert(0,"0")
  flag = 1
  for j in range(m):
    tmp = 0
    for k in range(l[j][0]):
      if sw[-l[j][k+1]] == "1":
        tmp += 1
    if tmp % 2 != pl[j]:
      flag = 0
  if flag == 1:
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=[]
for m in range(M):
    newinput=list(map(int,input().split()))
    S.append([s-1 for s in newinput[1:]])
P=list(map(int,input().split()))

def bit(n,N):
    return ('0'*10+bin(n)[2:])[-N:]

def switch_to_light(switch_state):
    light_state=[]
    for m in range(M):
        if sum([switch_state[s] for s in S[m]])%2==P[m]:
            light_state.append(1)
        else:
            light_state.append(0)
    return light_state

count=0
for state in range(2**N):
    switch_state=[int(b) for b in bit(state,N)]
    light_state=switch_to_light(switch_state)
    if sum(light_state)==M:
        count+=1
print(count)

Submission status: Accepted

Solution code:
def gen_switch(i, n):
    ret = []
    str_bin = format(i, '011b')
    for k in range(n):
        ret.append(int(str_bin[-k-1]))
    ret.reverse()
    return ret


input_line = input()
splitted_line = input_line.split(" ")
n = int(splitted_line[0])
m = int(splitted_line[1])


my_mtx = []

for i in range(m):
    my_list = [0] * n
    splitted_line = input().split(" ")

    for j in range(len(splitted_line)):
        if j != 0:
            my_list[int(splitted_line[j])-1] = 1

    my_mtx.append(my_list)

splitted_line = input().split(" ")
my_list = []

for item in splitted_line:
    my_list.append(int(item))


count = 0

# print(my_list)                                                                                                                                                                                                              

for i in range(2 ** n):
    my_switch = gen_switch(i, n)
    for j in range(m):
        my_sum = 0
        for k in range(len(my_switch)):
            my_sum = my_sum + (my_switch[k] * my_mtx[j][k])
        if my_sum % 2 != my_list[j]:
            break
        if j == m - 1:
            count = count + 1

print(count)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
masks = [0] * M

for i in range(M):
    inp = [int(j) for j in input().split()]
    k = inp[0]
    s = inp[1:]
    b = [0] * N
    for j in range(N):
        b[j] = "1" if j+1 in s else "0"
    masks[i] = int("".join(reversed(b)), 2)
    # print(list(reversed(b)))

ps = [int(p) for p in input().split()]
s = 0

for t in range(2**N):
    for i in range(M):
        v = masks[i] & t
        # print("i:", i)
        # print("t: {}\nm: {}\nv: {}\n\n".format(format(t, "b"), format(masks[i], "b"), format(v, "b")))
        if format(v, "b").count("1") % 2 != ps[i]:
            break
    else:
        # print("count")
        s += 1

print(s)

Submission status: Accepted

Solution code:
from itertools import product

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

switches = []
for i in range(m):
  k, *s = map(int, input().split())
  switches.append(s)

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

patterns = product([0, 1], repeat=n)
cnt = 0
for pattern in patterns:
  for switch, onoff in zip(switches, onoffs):
    switch_ons = 0
    for switch_num in switch:
      if pattern[switch_num-1] == 1:
        switch_ons += 1
    if switch_ons % 2 != onoff:
      break
  else:
    cnt += 1
    
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def remain(l_p, sw_p):
    cnt = 0
    for l, on in zip(l_p, sw_p):
        _on = int(on)
        if _on == 0:
            continue
        if l == _on:
            cnt += 1
    return cnt % 2


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

on_table = [[0] * n for _ in range(m)]

for i in range(m):
    line = input().split()
    for j in map(int, line[1:]):
        on_table[i][j-1] = 1


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

pattern = 2 ** n
max_bin = bin(pattern - 1)
bin_len = len(max_bin) - 2
format_pattern = "{:0" + str(bin_len) + "b}"
sw = [format_pattern.format(i) for i in range(pattern)]

cnt = 0
for _sw in sw:
    flag = True
    for _p, lite in zip(p, on_table):
        chk = remain(lite, _sw)
        if chk != _p:
            flag = False
            break

    if flag:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
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()))

cnt = 0
for i in range(2**N):
    light = 0
    switch = format(i, '0'+str(N)+'b')
    for j in range(M):
        pj = p[j]
        kj = ks[j][0]
        on = 0
        for l in range(1, kj+1):
            if switch[ks[j][l]-1] == '1':
                on += 1
        if on % 2 == pj:
            light += 1
        else:
            break
    if light == M:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n, m = (int(i) for i in input().split())

k_s = []
for i in range(m):
    k_s.append([int(x) for x in input().split()])
p = [int(x) for x in input().split()]
ans = 0
sw = [[0]*n for i in range(m)]

for i in range(m):
    for j in range(len(k_s[i])-1):
        sw[i][k_s[i][j+1]-1]=1
for i in range(2**n):
    s = [0]*n
    k=n-1
    while(i>=1):
        s[k] = (i%2)
        i = int(i/2)
        k -= 1
    tmp = [0]*m
    for j in range(m):
        f = 1
        for x in range(n):
            tmp[j] += sw[j][x]*s[x]
        if(tmp[j]%2!=p[j]):
            f = 0
            break
    ans += 1*f
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ks = [list(map(int,input().split())) for x in range(m)]
plis = list(map(int,input().split()))
ans = 0
llis=[]
for x in range(2**n):
    sw_lis = [0]*n
    for y in range(n):
        if ((x >> y)&1):
            sw_lis[y] = 1
    llis.append(sw_lis)
for sw in llis:
    on = 0
    for x in range(m):
        judge = 0
        for i in ks[x][1:]:
            judge += sw[i-1]
        if judge%2 == plis[x]:
            on += 1    
    if on == m:
        ans += 1
print(ans)

Submission status: Accepted

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

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

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

ans = 0
for i in range(pow(2, N)):
    e = '{:010b}'.format(i)[::-1]
    go = True
    for j in range(M):
        if go==False:
            break
        cnt = 0
        for d in S[j]: # d桁目が立っているか確認
            if e[d-1]=="1":
                cnt += 1
        if cnt%2 == P[j]:
            go = True
        else:
            go = False
    if go:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def c_switches(N, M, Switches, P):
    digit = N
    ans = 0
    for b in range(1 << digit):
        cnt = 0
        for i, (_, *switch) in enumerate(Switches):
            count = 0
            for d in range(digit):
                if (((1 << d) & b) != 0) and (d + 1 in switch):
                    count += 1
            if (count % 2) == P[i]:
                cnt += 1
        if cnt == M:
            ans += 1
    return ans

N, M = [int(i) for i in input().split()]
Switches = [[int(i) for i in input().split()] for j in range(M)]
P = [int(i) for i in input().split()]
print(c_switches(N, M, Switches, P))

Submission status: Accepted

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

switches = []
for x in range(m):
	inputs = list(map(int, input().split()))
	switches.append(inputs[1:])
	
remainders = list(map(int, input().split()))

count = 0
for x in range(2 ** n):
	bin_x = '{:010b}'.format(x)
	# print("bin:", bin_x)
	
	flag= True
	for j, indexes in enumerate(switches):
		
		summation = 0
		for i in indexes:
			summation += int(bin_x[-i])
			# print(bin_x[-i])
		# print("sum", summation, "rem",remainders[j])
		if summation % 2 != remainders[j]:
			flag = False
	if flag:
		# print(f"flag: {flag}")
		count += 1

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = []
for i in range(m):
    h.append(list(map(int, input().split())))
    
p = list(map(int, input().split()))
ans = 0
for i in range(2 ** n):
    g = format(i, "010b")
    count = 0
    
    for j in range(m):
        x = 0
        for k in range(len(h[j]) - 1):
            x += int(g[10 - h[j][k+1]])
        if x % 2 != p[j]:
            break
        count+= 1
    
    if count == m:
        ans += 1


print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations, combinations,combinations_with_replacement,product
n,m=map(int, input().split())

a=[list(map(int, input().split())) for i in range(m)]
p=list(map(int, input().split()))
count=0
for sw in product([0,1],repeat=n):
    flag=1
    for i in range(m):
        on=0
        for j in range(a[i][0]):
            on+=sw[a[i][j+1]-1]
        
        if on%2!=p[i]:
            flag=0
        #print(on,sw,p[i],flag, on%2!=p[i])
    count+=flag
print(count)

Submission status: Accepted

Solution code:
import sys
def c():
    p = [[int(t) for t in r.split(' ')] for r in sys.stdin.read().split('\n') if r != '']
    N, M = p[0]
    l = p[1:M + 1]
    cond = p[M + 1]
    count = 0
    for i in range(0, 1<<N):
        cc = 0
        for j in range(0, M):
            b = 0b0
            for k in l[j][1:]:
                if (i >> (k - 1)) & 0b1 == 1:
                    b = ~b
            if b & 0b1 != cond[j]:
                break
            cc = cc + 1
        if cc == M:
            count = count + 1
    print(count)
c()

Submission status: Accepted

Solution code:
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:])
ans=0
p=list(map(int,input().split()))

for i in range(2**n):
    num=str(bin(i))[2:]
    num=num.zfill(n)
    num=num[::-1]
    #print(num)
    judge=1
    for j in range(m):
        cnt=0
        #print(num)
        for q in range(len(s[j])):
            if num[s[j][q]-1]=='1':
                cnt+=1
        if cnt%2!=p[j]:
            judge=0
            break
    if judge:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# スペース区切りの整数の入力
N,M = map(int, input().split())

KS_list=[]

for i in range(M):
  KS_list.append([int(e) for e in input().split()])

P_list = [int(e) for e in input().split()]

#総当たりする
switch_state=[]
switch_stop=[]
ans=0

for i in range(N):
  switch_state.append("0")
  switch_stop.append("1")

while switch_state!=switch_stop:
  #print(switch_state)

  #switch_stateの検査
  for i in range(M):
    k = KS_list[i][0]
    on_number = 0
    for j in range(1,k+1):
      #print("check No.",KS_list[i][j],":",end="")
      if switch_state[KS_list[i][j]-1]=="1":
        #print("on")
        on_number+=1
      #else:
        #print("off")
  
    #print(on_number,",",end="")
    #print(P_list[i])
    
    if on_number%2!=P_list[i]:
      #print("NG")
      break
    elif on_number%2==P_list[i] and i==M-1:
      #print("OK")
      ans+=1
 
  #switch_stateの変更
  if switch_state.pop(-1)=="0":
    switch_state.append("1")
  else:
    i = 1
    while(switch_state.pop(-1)!="0"):
      i = i + 1

    switch_state.append("1")
    for j in range(i):
      switch_state.append("0")

#print(switch_state)
#switch_stateの検査

for i in range(M):
  k = KS_list[i][0]
  on_number = 0
  for j in range(1,k+1):
    #print("check No.",KS_list[i][j],":",end="")
    if switch_state[KS_list[i][j]-1]=="1":
      #print("on")
      on_number+=1
    #else:
      #print("off")
      
  #print(on_number,",",end="")
  #print(P_list[i])

  if on_number%2!=P_list[i]:
    #print("NG")
    break
  elif on_number%2==P_list[i] and i==M-1:
    ans+=1
    #print("OK")
    
print(ans)

Submission status: Accepted

Solution code:
import itertools


sw_n,den_n = list(map(int,input().split()))
dens = []

for _ in range(den_n):
    dens.append(list(map(int,input().split()[1:])))
den_kyo = list(map(int,input().split()))

patt = list(itertools.product([0,1], repeat=sw_n))

res = 0

for pat in patt:
    kyoka = True
    for i,den in enumerate(dens):
        sums = 0
        for j in den:
            sums += pat[j-1]
        if sums%2 != den_kyo[i]:
            break
    else:
        res+=1


print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ksList = [list(map(int, input().split())) for i in range(M)]
pList = list(map(int, input().split()))

ans = 2**N

for i in range(2**N):
 tentouList = format(i,  '0' + str(N) + 'b')
 #print(tentouList)
 for j in range(M):
     tentouSum = 0
     for k in range(1, ksList[j][0]+1):
         tentouSum = tentouSum + int(tentouList[N - ksList[j][k]])
         #print("ksList[j][k]" + str(ksList[j][k]))
     #print("tentoSum =" + str(tentouSum))
     #print("pList = " + str(pList[j]))
     if tentouSum % 2 != pList[j]:
         #print("false")
         ans = ans - 1
         break

#print("ans")
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = []
for i in range(M):
    k = list(map(int, input().split()))
    S.append(k[1:])
P = list(map(int, input().split()))
ans = 0
for i in range(2 ** N):
    a = 0
    for j in range(M):
        t = 0
        for s in S[j]:
            t += (i >> (s - 1)) & 1
        if t % 2 == P[j]: a += 1
    if a == M: ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split(" "))
denQs=[]
count=0
for i in range(m):
	denQ=[]
	line=input().split(" ")
	for j in range(int(line[0])):
		denQ.append(int(line[j+1]))
	denQs.append(denQ)
denQrights=input().split(" ")
ansLst=[[0],[1]]
for i in range(n-1):
	nxtAnsLst=[]
	for a in ansLst:
		nxtAnsLst.append(a+[0])
		nxtAnsLst.append(a+[1])
	ansLst=nxtAnsLst
for a in ansLst:
	isFound=True
	for i in range(m):
		c=0
		for j in denQs[i]:
			c+=a[j-1]
		if c%2!=int(denQrights[i]):
			isFound=False
			break;
	if isFound:
		count+=1
print(count)

Submission status: Accepted

Solution code:
#全探索！
N, M = map(int,input().split())
K = []
for i in range(M):
    k =list(map(int,input().split()))
    K.append(k)
p = list(map(int,input().split()))
ans = 0

for i in range(2**N):
    for k in range(M):#kは電球のindex
        a = 0
        b = True
        for j in K[k][1:]:  # このループが一番のポイント
            if (((i >> (j-1) )& 1)):  # 順に右にシフトさせ最下位bitのチェックを行う
                a += 1
        if a%2 != p[k]:
            b = False
            break
    if b:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
sw = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
ans = 2**n

for i in range(2**n):
  bin_str = format(i, '010b')[::-1]
  for j in range(m):
    sum = 0
    for k in range(sw[j][0]):
      sum += int(bin_str[sw[j][k+1]-1])
    if sum % 2 != p[j]:
      ans -= 1
      break
      
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
K = [0]*M
S = [[0] *N for _ in range(M)]
for i in range(M):
    tmp = list(map(int,input().split()))
    K[i] = tmp[0]
    for s in tmp[1:]:
        S[i][s-1] = 1
P = list(map(int,input().split()))

ptns = list(itertools.product((0,1),repeat=N))
ans = 0
# 全てのON/OFFパターン
for p in ptns:
    # 全ての電球
    for i in range(M):
        # ONになっているスイッチ
        on_count = 0
        for j in range(N):
            on_count += S[i][j] and p[j]
        if on_count%2 != P[i]:
            break
        
    else:
        # print(p)
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
[N,M] = [int(e) for e in input().split()]
s=[]
for i in range(M):
  s.append([int(e) for e in input().split()])

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

ans=0
for i in range(2**N):
  check=1
  for j in range(M):
    sum=0
    for c in range(s[j][0]):
      sum += (i//(2**(s[j][c+1]-1)))%2
    if (sum%2)!=p[j]:
      check = 0
  if check ==1:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = [int(nm) for nm in input().split()]
S = []
for m in range(M):
  KS = [int(ks) for ks in input().split()]
  S.append(KS[1:])
P = [int(p) for p in input().split()]
ans = 0
for n in range(2**N):
  on_off = str(format(n, "b"))
  if len(on_off)<N:
    on_off = "0"*(N-len(on_off)) + on_off
  on_light = 0
  for m in range(M):
    nm_of_light = 0
    for sm in range(len(S[m])):
      nm_of_light += int(on_off[S[m][sm]-1])
    if nm_of_light % 2 == P[m]:
      on_light += 1
  if on_light == M:
    ans += 1
print(ans)

Submission status: Accepted

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

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

res=0
for i in range(pow(2,n)):
    sw=("0000000000000000000000"+bin(i)[2:])[-n:]
    failed=False
    for j in range(m):
        sum=0
        for k in range(len(s[j])):
            sum+=int(sw[s[j][k]-1])
        if sum%2!=p[j]:
            failed=True
            break
    if not failed:
        res+=1
print(res)

Submission status: Accepted

Solution code:
import itertools

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

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

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

ans = 0
for i, s in enumerate(itertools.product([0,1],repeat=N)):
    if all([sum([s[j-1] for j in v])%2==t  for v,t in zip(k, p)]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, M = map(int, input().split())
S = []

for i in range(M):
	k, *ss = map(int, input().split())
	S.append(np.asarray(ss, np.int) - 1)

P = np.fromiter(map(int, input().split()), np.int)

count = 0
for bits in range(1 << N):
	switches = (bits >> np.arange(N)) & 1
	count += all(np.sum(switches[S[i]]) % 2 == P[i] for i in range(M))

print(count)

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
# -*- coding: utf-8 -*-
N, M = [int(x) for x in input().split()]

S =[]
for j in range (M):
    a = [x for x in input().split()]
    k = a[0]
    s = [int(x) for x in a[1:]]
    S.append(s)
P = [int(x) for x in input().split()]
ans = 0
for i in range (2**N):
    n = format(i,'b').zfill(N)
    
    count = 0
    for j in range (M):
        count2 = 0
        for k in range (len(S[j])):
            count2 += int(n[S[j][k]-1])
        if count2 %2 == P[j]:
            count += 1
    if count == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def bi(x):
  global N
  y = []
  for _ in range(N):
    y.append(x%2)
    x = x//2
  return y
N,M = map(int,input().split())
k,s = [],[]
for _ 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):
  x = bi(i)
  k = 0
  for j in range(M):
    y = 0
    for z in s[j]:
      y += x[z-1]
    if y%2!=p[j]:
      break
    k += 1
  ans += 1 if k==M else 0
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
data=[]
for i in range(0,M): #kとｓのimport
  a=list(map(int,input().split()))
  data.append(a)
P=list(map(int,input().split())) #ｐのimport


ans=0
A=[0,1]  
for i in itertools.product(A, repeat=N): #全通り
  S=list(i)

  j=0
  an="continue"
  while an=="continue" and j<M: #スイッチオンか確認
    SS=data[j]
    k=SS[0]
  
    sum=0
    for l in range(1,k+1): #オンの数確認
      if S[SS[l]-1]==0:
        sum=sum+1
        
    if sum%2!=P[j]: #オンの数おかしい 
      an="break"
    
    elif j==M-1: #最後までok
      ans=ans+1
     
      j=j+1
    else: #オンの数正しい
      j=j+1
      
        
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
sList = []
for i in range(m):
  tempList = list(map(int, input().split()))
  k = tempList.pop(0)
  num = 0
  for j in tempList:
    num += 2 ** (j-1)
  sList.append(num)
pList = list(map(int,input().split()))
answer = 0
sw = True

for i in range(2**n):
  for j in range(len(sList)):
    p = i & sList[j]
    tf = (bin(p).count('1') + pList[j]) % 2
    if tf == 1:
      sw = False
      break
  if sw == True:
    answer += 1
  else:
    sw = True
    
print(answer)