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: Runtime Error

Solution code:
n, m = map(int, input().split())
switch = [0] * n
for i in range(m):
    s = list(map(int, input().split()))
    for j in s[1:]:
        switch[i] |= 1 << (j - 1)
p = list(map(int, input().split()))
ans = 0
for bit in range(1 << n):
    for i in range(m):
        if bin(bit & switch[i]).count('1') % 2 != p[i]:
            break
    else:
        ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
switch = [0] * n
for m_ in range(m):
    s = list(map(int, input().split()))
    for s_ in s[1:]:
        switch[m_] |= 1 << s_ - 1
p = list(map(int, input().split()))
ans = 0
for bit in range(1 << n):
    for i in range(m):
        if bin(bit & switch[i]).count('1') % 2 != p[i]:
            break
    else:
        ans +=1
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
x = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2 ** m):
    bag = [0]*n
    cnt = 0
    for j in range(m):  
        if ((i >> j) & 1):  
            bag[j]+=1
    for l in range(m):
        res = 0
        for h in range(1,len(x[l])):
            res += bag[x[l][h]-1]
        if res%2!=p[l]:
            break
        else:
            cnt += 1
    if cnt==m:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
N, M = map(int, input().split())
lists = []
for _ in range(M):
    lists.append(list(map(int, input().split()))[1:])
p_list = list(map(int, input().split()))
num = 0
len_m = N
for n in range(2 ** N):
    flag = True
    for p, lis in zip(p_list, lists):
        flag = flag & ((sum([f'{n:0{len_m}b}'[l - 1] == '1' for l in lis]) % 2) == p)
    num += flag
print(num)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

def switch_on_off(n, keta):
    bin_str = format(n, f'0{keta}b')
    return list(bin_str)

def check_light(n, N, s, index, P):
    switch = switch_on_off(n, N)
    sum = 0
    for v in s:
        sum += int(switch[int(v) - 1])
    if sum % 2 == P[index - 1]:
        return 1
    return 0

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


ans = 0
for n in range(2 ** N):
    sum = 0
    for index, s in enumerate(S):
        sum += check_light(n, N, s, index, P)
    if sum == M:
        ans += 1

print(ans)

Submission status: Runtime Error

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

p = list(map(int, input().split()))
ans = 0
for i in range(1<<n):
    p_ = p[:]
    for j in range(n):
        if not (i & (1<<j)):
            continue
        for k in range(m):
            if j+1 in a[k]:
                p_[k] ^= 1
    ans += (max(p_) == 0):
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
li_ord = [0 for _ in range(m)]
dic = defaultdict(list)

for i in range(m):
    s = list(map(int, input().split()))[1:]
    for j in s:
        dic[j].append(i)
p = list(map(int, input().split()))
dic = sorted(dict(dic).items())
ans = 0

if dic == []:
    if 1 in p:
        print(0)
    else:
        print(2**n)
    exit()

for i in range(2**n):
    tmp_num = bin(i)[2:].zfill(n)
    li = li_ord
    for j in range(n):
        digit = tmp_num[j]
        #print(digit, dic[j][1])
        if digit == '1':
            for k in dic[j][1]:
                #print(li[k], k)
                li[k] ^= 1
    #print(tmp_num, p, li)
    if p == li:
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import itertools
 
N, M = map(int, input().split())
 
S = []
for i in range(M):
    k, *s = map(int, input().split())
    S.append([s])
    
P = [int(i) for i in input().split()]
 
A = [0, 1]
ans = 0
for i in itertools.product(A, repeat = N):
    flag = 0
    for j in range(M):
        cnt = 0
        for s in S[j]:
            if i[s - 1] == 1:
                cnt += 1
        if cnt % 2 != P[j]:
            flag = 1
    if flag == 0:
        ans += 1
        
print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# coding: UTF-8

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

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

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

ret = 0
all = [(str(bin(i)))[2:].zfill(m) for i in range(2 ** n),]
all = [[int(i) for i in case] for case in all,]
for case in all:
    # print("------------------------------------------------")
    # print("[case = ",case,"]")
    flag = 0
    for num,i in enumerate(s):
        if flag == 1:
            continue

        # print("  [case = ",i[1:],"]")

        sw = [0 for z in range(n),]
        # print("sw",sw)
        for k in i[1:]:
            sw[k-1] = 1

        # print(sw,case)
        # print(sum(i*j for i,j in zip(sw,case)) % 2," =? ",p[num])
        if (sum(i*j for i,j in zip(sw,case),) % 2) != p[num]:
            flag = 1
        # print("flag is ",flag)
           
    if flag == 0:
        # print(case," is ok.")
        ret += 1

print(ret)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
X=[]
for i in range(M):
    X.append(list(map(int, input().split())))
P=list(map(int, input().split()))
ans=0

key='{:0'+str(N)+"b}"
for k in range(2**N):
    
    switch=list(key.format(k))
    for i in range(M):
        
        odd=1
		even=0
        if P[i]==1:
            odd=0
            for j in range(X[i][0]):
                odd+=int(switch[ X[i][j+1]-1] )
            if odd%2==0:
                break
            
        else:
            even=0
            for j in range(X[i][0]):
                even+=int(switch[ X[i][j+1]-1] )
            if even%2==1:
                break
    
    if odd%2==1 and even%2==0:
        ans+=1
        #print(X[i],switch,odd,even)
            
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools as ittr

def test_switch(e_balls, sw, p):
    for i, e_ball in enumerate(e_balls):
        si = sw[eb - 1]
        
        if p[i] != (np.sum(si == 1) % 2):
            return False
    
    return True

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

e_balls = []

for m in range(M):
    i = input().split()
    s = [int(si) for si in i[1:]]
    e_balls.append(s[:])

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

cnt = 0

for sw in ittr.product([0, 1], repeat = N):
    if test_switch(e_balls, np.array(sw), p):
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools as ittr

def test_switch(e_balls, sw, p):
    for i, e_ball in enumerate(e_balls):
        eb = np.asarray(e_ball)
        si = sw[eb - 1]
        
        if p[i] != (np.sum(si == 1) % 2):
            return False
    
    return True

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

e_balls = []

for m in range(M):
    i = input().split()
    s = [int(si) for si in i[1:]]
    e_balls.append(s[:])

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

cnt = 0

for sw in ittr.product([0, 1], repeat = N)
    if test_switch(e_balls, sw, p):
        cnt += 1

print(cnt)

Submission status: Runtime Error

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

li=[]
for i in (1, m+1):
    s=list(map(int, input().split()))
    s.pop(0)
    li.append(s)

p = list(map(int, input().split()))
#print(li)
#print(p)

def check(g,en):
    stack = ["1", "0"]
    candi = []
    while stack:
        cur = stack.pop()
        if len(cur) == en:
            candi.append(cur)
            continue
        for i in g[len(cur)+1]:
            tmp = cur+i
            stack.append(tmp)
    return candi

g={}
for i in range(0,n+1):
    g[i]=["1", "0"]

ans = 0
print(check(g,n))
for i in check(g,n):
    flag=0
    for j in range(m):
        tmp=0
        for k in range(0,len(li[j])):
            tmp += int(i[li[j][k]-1])
        if tmp % 2  != p[j]:
            flag=1
            break
    if flag==0:
        print(i)
        ans += 1

print(ans)

Submission status: Runtime Error

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

li=[]
for i in (1, m+1):
    s=list(map(int, input().split()))
    s.pop(0)
    li.append(s)

p = list(map(int, input().split()))
#print(li)
#print(p)


def check(g,en):
    stack = ["1", "0"]
    checked = []
    candi = []
    while stack:
        cur = stack.pop()
        checked.append(cur)
        if len(cur) == en:
            candi.append(cur)
            continue
        for i in g[len(cur)]:
            tmp = cur+i
            if tmp in checked:
                continue
            if tmp in stack:
                continue
            stack.append(tmp)
    return candi

g={}
for i in range(0,n+1):
    g[i]=["1", "0"]

ans = 0
for i in check(g,n):
    flag=0
    for j in range(m):
        tmp=0
        for k in range(0,len(li[j])):
            tmp += int(i[li[j][k]-1])
        if tmp % 2  != p[j]:
            flag=1
            break
    if flag==0:
        #print(i)
        ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import itertools


N, M = map(int, input().split())
connected_switches = [[int(x) - 1 for x in input().split()[1:]] for x in range(M)]
conditions = list(map(int, input().split()))

ok = 0
for patterns in itertools.product((0, 1), repeat=M):
    patterns = list(patterns)
    is_lighting = True
    for i, lights in enumerate(connected_switches):
        turned_sw = sum([patterns[x] for x in lights])
        if turned_sw % 2 != conditions[i]:
            is_lighting = False
            break
    if is_lighting:
        ok += 1

print(ok)

Submission status: Runtime Error

Solution code:
from numpy import*
n,m=map(int,input().split())
l=[]
for i in range(m):
    *a,=map(int,input().split())
    l.append(a[1:])
*p,=map(int,input().split())

ans=0
for t in range(2**m):
    tmp=array([t>>s&1 for s in range(m)])
    if p==[sum(tmp[array(i)-1])%2for i in l]:
        ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/abc128
# -*- coding: utf-8 -*-

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

k = []
s = []
for i in range(m):
    x = list(map(int,input().split()))
    k.append(x[0])
    y = []
    for j in range(x[0]):
        y.append(x[j+1])
    s.append(y)

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

cnt = 0
for i in range(1024):
    x = format(i,"08b")[::-1]
    if x[n] == "1":
        break

    for j in range(m):
        tmpSum = 0
        for k in s[j]:
            tmpSum += int(x[k-1])
        if tmpSum%2 is not p[j]:
            break
    else:
        cnt += 1
        
print(cnt)

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/abc128
# -*- coding: utf-8 -*-

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

k = []
s = []
for i in range(m):
    x = list(map(int,input().split()))
    k.append(x[0])
    y = []
    for j in range(x[0]):
        y.append(x[j+1])
    s.append(y)

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

cnt = 0
for i in range(1024):
    x = format(i,"08b")[::-1]
    if x[n] == "1":
        break

    for j in range(m):
        tmpSum = 0
        for k in s[j]:
            tmpSum += int(x[k-1])
        if tmpSum%2 is not p[j]:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Runtime Error

Solution code:
#C問題
N,M = map(int,input().split())
K = []
S = []
for i in range(M):
    ks =list(map(int,input().split()))
    ss = []
    kk = ks[0]
    K.append(kk)
    for j in range(kk):
        ss.append(ks[j+1])
    
    S.append(ss)
P = list(map(int,input().split()))
Bit = 2**N
ans = 0
for i in range(Bit):
    b = bin(i)
    b = b.lstrip("0b")
    lenb = len(b)
    j = 0
    for j in range(N-lenb):
        b = "0"+b
        
    sw = []
    j = 0

    for j in range(M):
        if b[j] == "1":
            sw.append(1)
        else:
            sw.append(0)
    
    j = 0
    flag = 0
    for j in range(M):
        cond = P[j]
        now = 0
        for k in range(K[j]):
            now+=sw[S[j][k]-1]
            
        if now%2 == cond:
            pass
        else:
            flag = 1
            break
            
    if flag == 0:
        ans+=1
    
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

combi = 0
for i in range(1<<N):
    flag = True
    for j, switch in enumerate(lights):
        if sum([1 for s in switch if (i>>(s-1)) & 1 == 1])%2 != p[j]:
            flag = False
            break
    if flag:
        combi += 1

print(combi)

Submission status: Runtime Error

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


ans=0
key='{:0'+str(N)+"b}"
for k in range(2**N):
    
    switch=list(key.format(k))
    for i in range(M):
        if P[i]==1:
            odd=0
            for j in range(X[i][0]):
                odd+=int(switch[ X[i][j+1]-1] )
            if odd%2==0:
                break
            #print(X[i],switch,odd)
        else:
            even=0
            for j in range(X[i][0]):
                even+=int(switch[ X[i][j+1]-1] )
            if even%2==1:
                break
    if odd%2==1 and even%2==0:
        ans+=1
        
print(ans)

Submission status: Runtime Error

Solution code:
import itertools

def main():
    n,m=list(map(int,input().split(' ')))
    swich_all=list(itertools.product([0,1],repeat=n))
    swich=[]
    cnt=0
    for i in range(m):
        swich.append(list(map(int,input().split(' '))))
    check_p=list(map(int,input().split(' ')))
    for i in swich_all:
        tmp=0
        check =True
        for j in range(m):
            for k in swich[j][1:]:
                tmp += i[k-1]
            if tmp%2 != check_p[j]:
                check = False
                break
        if check == True:
            cnt +=1

    print(cnt)

main()

main()

Submission status: Runtime Error

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


ans=0
key='{:0'+str(N)+"b}"
for i in range(2**N):
    
    switch=list(key.format(i))
    for i in range(M):
        if P[i]==1:
            odd=0
            for j in range(X[i][0]):
                odd+=int(switch[ X[i][j+1]-1] )
            if odd%2==0:
                break
            #print(X[i],switch,odd)
        else:
            even=0
            for j in range(X[i][0]):
                even+=int(switch[ X[i][j+1]-1] )
            if even%2==1:
                break
    if odd%2==1 and even%2==0:
        ans+=1
        
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
#N, M = list(map(int, input().split()))
N = 2
M = 2
tmp = [[int(i) for i in input().split()] for i in range(M)]
p = list(map(int, input().split()))
ans = 0
for switch in itertools.product(range(2),repeat=N):
    #print(switch)
    num_clear_light = 0
    for i in range(M):
        count = 0
        for j in range(tmp[i][0]):
            #print(tmp[i][j+1])
            if(switch[tmp[i][j+1] - 1] == 1):
                count += 1
        if(count % 2 == p[i]):
            num_clear_light += 1
    if(num_clear_light == M):
        ans += 1
    num_clear_light = 0

print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split(" "))
botlist = []
ans = 0
for n in range(M):
    bot = list(map(int, input().split(" ")))
    
    botlist.append(bot)
#botlist
plist = list(map(int, input().split(" ")))

pushlist = [[]for i in range(2**N)]

for p in range(N):
    M = (2**N)/(p+1)
    for q in range(M):
        for r in range(p+1):
            if q%2 == 0:
                pushlist[r*q] = 0
            else:
                pushlist[r*q] = 1

for A in pushlist:
    g = 0
    for B in botlist:
        cou = 0
        for c in range(B[0]):
            cou += A[B[c]]
        if cou % 2 == plist[g]:
            ans += 1
    g +=1

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

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


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

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

print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
s = []
for i in range(m):
    s.append(list(map(int,input().split())))
    
p = list(map(int,input().split()))
ans = 0
for i1 in range(2):
    for i2 in range(2):
        for i3 in range(2):
            for i4 in range(2):
                for i5 in range(2):
                    for i6 in range(2):
                        for i7 in range(2):
                            for i8 in range(2):
                                for i9 in range(2):
                                    for i10 in range(2):
                                        switches = [i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                                        flag_temp = 0
                                        for i in range(m):
                                            temp = 0
                                            for l in range(s[i][0]):
                                                temp += switches[s[i][l+1]-1]
                                            if temp % 2 == p[i]:
                                                flag = 1
                                                flag_temp += 1
                                        if flag == 1 and flag_temp == m:
                                            ans += 1

print(int(ans/2**(10-n)))

Submission status: Runtime Error

Solution code:
import itertools

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


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

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

print(ans)

Submission status: Runtime Error

Solution code:
N,M=input().strip().split()
l1=[]
while True:
    try:
        l1.append(list(map(int,input().split())))
    except:
        break;
l2=l1[-1]
del l1[-1]
n=0
tate=0
yoko=1
count1=0
count2=0
count3=0
while True:
    while True:        
        sw=str(bin(n))
        del sw[0]
        a=l1[tate][yoko]
        if int(sw[a])==1:
            count1=count1+1
        yoko=yoko+1
        if yoko==l1[tate][0]:
            yoko=1
            if count1%2==l2[tate]:
                count2=count2+1
            break
    tate=tate+1
    if tate==M:
        if count2==N:
            count3=1
        n=n=1
        break

Submission status: Runtime Error

Solution code:
import itertools

n, m = [int(i) for i in input().split()]
s = []
k = []
for i in range(m):
    moyo = input().split()
    k.append(int(moyo[0]))
    s.append(moyo[1:])
p = input().split()
switch = ("on", "off")
ans = list(itertools.product(['on', 'off'], repeat = n))
for i in range(m):
    if(p[i] == 0):
        ans.delete(ans.count("on") & 2 == 1)
    else:
        ans.delete(ans.count("on") & 2 == 0)
print(len(ans))

Submission status: Runtime Error

Solution code:
import itertools
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N, M = input().split()
N = int(N)
M = int(M)
S_list = []
S_list = []
for h in range(M):
    list = []
    list = input().split()
    for y in range(int(len(list[0]))):
        s_list[y] = list[y+1]
        S_list.append(s_list)
p_list = []
p_list = input().split()
p_list = [int(s) for s in p_list]


count = 1

for i in range(M):
    if p_list[i] == 0:
        x = int(k_list[i]/2 + 1)
        for l in range(x):
            c = list(itertools.combinations(S_list[i],2*l))
            count = count*len(c)
    else:
        x = int((k_list[i]-1)/2 + 1)
        for l in range(x):
            c = list(itertools.combinations(S_list[i],2*l+1))
            count = count*len(c)

print(count)

Submission status: Runtime Error

Solution code:
N, M = (int(i) for i in input().split())
  
dict_rel = dict()
for i in range(M):
  dict_rel[i+1] = [int(j) for j in input().split()][1:]
list_cond = [int(i) for i in input().split()]

#print(dict_rel)
#print(list_cond)

list_pattern = list()

for i in range(N):
  for j in [0,1]:
    list_pattern.append([i, j])

#print(list_pattern)
#print(list_pattern)

num_full = 0
for pattern in list_pattern:
  flg = True
  for light in dict_rel.keys():
    num_on = 0
    for i in range(len(dict_rel[light])):
      if pattern[i] == 1:
        num_on += 1
    if list_cond[light-1] != num_on%2:
      flg = False
      break
  if flg == True:
    num_full += 1

print(num_full)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
k_s = [[int(i) for i in input().split()] for i in range(m)]
p = [int(i) for i in input().split()]

tmp = 2**n
isAll = 0
ans = 0

for i in range(tmp):
    for j in range(m):        
        #ONの時
        if ((i >> m-1-j) & 1):
            if k_s[j][0]%2 == p[j]:
                
        #OFFの時
        else:
            if k_s[j][0]%2 == p[j]:
                isAll += 1
    if isAll==n:
        ans+=1
            
print(ans)

Submission status: Runtime Error

Solution code:
n, m = (int(_) for _ in input().split())  
skp = [[int(i) for i in input().split()] for i in range(m+1)]
sk, p = skp[:-1], skp[-1]

def judge(sw_status, sk, p):
  sk = np.array(sk) - 1
  num = sw_status[sk[1:]].sum()%2
  if num == p:
    light = 1
  else:
    light = 0
  return light

# sw_status = np.array([0 for i in range(n)])
ans = 0
for i in range(2**n):
  sw_status = [j for j in bin(i)][2:]
  for SK, P in zip(sk, p):
  	j = judge(sw_status, SK, P)
    if j==0:
      break
    else:
      ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

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

p = input().split()

onoff = [0, 1]
kouho = list(itertools.product(onoff, repeat=N))

ans = 0
for li in kouho:
    for i in range(N):
        if p[i] == 0:
            li[i].count(0) % 2 == 0
            ans += 1
        else:
            li[i].count(0) % 2 == 1
            ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

N, M = map(int, input().split())
p = []
matrix = np.zeros((M, N))

for m in range(M):
    row = [int(v)-1 for v in input().split()]
    row = row[1:]
    for n in range(N):
        if n in row: matrix[m, n] = 1

p = [int(v) for v in input().split()]
p = np.array([p]).T
matrix = np.hstack([matrix, p])
rank = np.linalg.matrix_rank(matrix)

if N < rank:
    if not any(p): print(1)
    else print(0)
else:
    print(2**(N-rank))

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split()) #nがスイッチ、mが電球の数
s = []
swi = []

for i in range(m):
  x = list(map(int,input().split()))
  s.append(x)
p = list(map(int,input().split()))
print(s,p)

for i in range(1,2**n):
  x = format(i, 'b')
  x = x.zfill(n)
  swi.append(x)
#print(swi[-1])

for j in range(m):
  for i in range(len(swi)-1):
    x = 0
    for k in range(s[j][0]):
      x += int(swi[i][s[j][k]-1])
    if x % 2 != p[j]:
      del swi[i]
print(swi)

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
switch=[]
for i in range(pow(2,M)):
    app=format(i,"b")
    app=app.zfill(M)
    switch.append(app)
cond=[]
for i in range(M):
    cond.append(list(map(int,input().split())))
p=list(map(int,input().split()))

count=0
for sw in switch:
    cond_list=[]
    for i in range(M):
        for k in cond[i]:
            cond_num+=sw[i][k]
            cond_list.append(cond_num)
    cond_list=[co % 2 for co in cond_list]
    if set(cond_list)==p:
        count+=1
print(count)

Submission status: Runtime Error

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

lst = []
for i in range(N):
    ks = list(map(int,input().split()))
    lst.append(ks[1:])

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

c = 0

for j in range(2**N):
    for k, l in enumerate(p):
        msk = 0
        for b in lst[k]:
            msk += 2**(b-1)
        if bin(j&msk).count('1') % 2 != l:
            break
    else:
        c += 1

print(c)

Submission status: Runtime Error

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

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

i = 0



list_func = []#スイッチ点灯の全組み合わせを入れる
cnt=0

def func(i):
    if (i == N):
        flag = True
        for k in range(M):
            sum = 0
            for j in list_A[k]:
                sum += j
            sum = sum - list_A[k][0]
            if sum %2 != list_p[k]:
                flag = False
        if flag == True:
            cnt+=1
        return
    list_func.append(1)
    func(i+1)
    list_func.pop(-1)

    list_func.append(0)
    func(i+1)
    list_func.pop(-1)

    return


func(0)
print (cnt)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
import numpy as np
import itertools
input = sys.stdin.readline
N, M = map(int, input().split())
l = [list(map(int, input().split())) for i in range(M+1)]


# In[ ]:


"""
5 2
3 1 2 5
2 2 3
1 0
"""


# In[4]:


#print(l)
import numpy as np


# In[9]:


s = range(N)
cnt = 0
# N個がonになる
for e in range(1, N+1):
    c = list(itertools.combinations(s,e))# N個onになる通り
    o = list(range(N))
    for b in c:
        #print(b)
        a = np.zeros((N))
        for d in b:
            a[d] = 1
        #print(a)
        for i in range(M):
            sum_ = 0
            for j in range(l[i][0]):
                ind = l[i][j+1]-1
                #print(ind)
                sum_ += a[ind]
            o[i] = sum_%2==l[-1][i]
        if np.all(o):
            cnt += 1
#0個on
o = list(range(N))
a = np.zeros((N))
for i in range(M):
    sum_ = 0
    for j in range(l[i][0]):
        ind = l[i][j+1]-1
        sum_ += a[ind]
    o[i] = sum_%2==l[-1][i]
if np.all(o):
    cnt += 1
print(cnt)


# In[ ]:


"""
2 2
2 1 2
1 2
0 1
"""

Submission status: Runtime Error

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