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:
def is_all_lighting(switch_patten, s_info_list, p_list):
    for i in range(len(s_info_list)):
        s_info = s_info_list[i]
        on_count = 0
        for s in s_info['s_list']:
            on_count += switch_patten // (2 ** (s - 1)) % 2
        if on_count % 2 != p_list[i]:
            return False
    return True


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

for _ in range(M):
    val_list = list(map(int, input().split()))
    s_info_list.append({
        'k': val_list[0],
        's_list': val_list[1:]
    })
p_list = list(map(int, input().split()))

count = 0

for pattern in range(2 ** N):
    count += 1 if is_all_lighting(pattern, s_info_list, p_list) else 0

print(count)

Submission status: Accepted

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

y = [sum([2 ** i for i in range(N) if i + 1 in x[1:]]) for x in X]

ans = 0
for i in range(2 ** N):
  cnt = []
  for j, v in enumerate(y):
    cnt.append(list(bin(v & i)[2:]).count('1') % 2 == p[j])
  ans += 1 if all(cnt) else 0
  
print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
    N,M = list(map(int,input().split(" ")))
    light_l = []
    switch_l = [i for i in range(1,N+1)]
    for _ in range(M):
        light_l.append( list(map(int,input().split(" ")))[1:])
    cheak_l = list(map(int,input().split(" ")))
    ans = 0

    for i in range(N+1):
        for switches in list(itertools.combinations(switch_l,i)):
            for j,light in enumerate(light_l):
                if(cheak_l[j] is not (len(set(switches)&set(light)))%2):
                    break
                if(j is len(light_l)-1):
                    ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

N, M = map(int, input().split())
KS = []
for _ in range(M):
    kss = list(map(int, input().split()))
    KS.append(kss)

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

count = 0
for sw in product((0, 1), repeat=N):
    judge = True
    for i in range(M):
        on = 0
        for s in KS[i][1:]:
            on += sw[s-1]
        if on % 2 != P[i]:
            judge = False
            break
    if judge:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
k = []
s = []
for i in range(M):
    inp = list(map(int,input().split()))
    k.append(inp[0]) # 0 - M-1
    s.append(inp[1:]) # s[i] index: 0 - k-1

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

bits = [format(i,'b').zfill(N) for i in range(2**N)]

count = 0
for bit in bits:
    d = 1
    for i in range(M):
        sum = 0
        for sl in s[i]:
            sum = sum + int(bit[sl-1])
        if sum % 2 != p[i]:
            d = 0
            break
    count += d

print(count)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
switches_list = []
p = []
for index in range(m):
    tmp = list(map(int, input().split()))
    switches_list.append(tmp[1:])

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

# 答え
count = 0

op_cnt = n  # スイッチの個数
for i in range(2 ** op_cnt):
    op = [0] * op_cnt  # あらかじめ [0, 0, 0] というリストを作っておく
    for j in range(op_cnt):
        if ((i >> j) & 1):
            op[op_cnt - 1 - j] = 1  # フラグが立っていた箇所を 1 で上書き
    # print(op)
    # ここで処理する
    flag = True
    for index in range(m):
        tmp = 0
        for switch in switches_list[index]:
            tmp += op[switch - 1]
        if tmp % 2 != p[index]:
            flag = False
            break
    
    if flag == True:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
mat = np.zeros(N*M).reshape(M, N)

for i in range(M):
    k = list(map(int, input().split()))
    for j in k[1:]:
        mat[i, j-1] += 1
p = list(map(int, input().split()))

def two(x):
    a = np.zeros(N)
    for i in range(11):
        if x == 0:
            break
        elif x % 2 == 0:
            x = x // 2
        else:
            a[i] += 1
            x = x // 2
    return a

flag = 0
for i in range(2**N):
    a = two(i)
    mat2 = mat * a
    for j in range(M):
        if np.sum(mat2[j]) % 2 != p[j]:
            break
        if j == M-1:
            flag += 1

print(flag)

Submission status: Accepted

Solution code:
import sys
#import numpy as np

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

import itertools

def main():
    N, M = i2nn()
    KS = ii2nnn(M)
    P = i2nn()
    judges = [[] for _ in range(M)]
    for i, ks in enumerate(KS):
        p = P[i]
        k = ks[0]
        s = ks[1:]
        while True:
            if p > len(s):
                break
            for pattern in itertools.combinations(s, p):
                d = [-1] * N
                for j in s:
                    d[j-1] = 0
                for j in pattern:
                    d[j-1] = 1
                judges[i].append(d)
            p += 2
    #print(judges)
    L = 2 ** N
    n = 0
    for i in range(L):
        sw = getDigits(i, N)
        #print(sw)
        a = True
        for judge in judges:
            b = False
            for ju in judge:
                c = True
                for j, k in zip(sw, ju):
                    if k == -1:
                        continue
                    elif j == k:
                        continue
                    else:
                        c = False
                        break
                if c:
                    b = True
                    break
            if b == False:
                a = False
                break
        if a:
            n += 1
    print(n)

def getDigits(n, maxlen):
    digits = [0] * maxlen
    i = 0
    while True:
        digits[i] = n % 2
        i += 1
        n = int(n / 2)
        if n == 0 or i >= maxlen:
            break
    return digits

main()

Submission status: Accepted

Solution code:
import numpy as np

n,m=map(int,input().split())
A=np.zeros([m,n])
for i in range(m):
    a=list(map(int,input().split()))
    k=a[0]
    for j in range(k):
        A[i][a[j+1]-1]=1
p=list(map(int,input().split()))
count=0
for i in range(2**n):
    ss=bin(i)
    s=ss[2:len(ss)].zfill(n)
    flag=1
    for j in range(m):
        x=0
        for h in range(n):
            x+=int(s[h])*A[j,h]
        if(x%2!=p[j]):
            flag=0
            break
    if(flag==1):
        count+=1
print(count)

Submission status: Accepted

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

ans = 0
for i in range(2 ** N):
    P_ = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            for k in range(M):
                if N - j in switches[k]:
                    P_[k] += 1
    for l in range(M):
        P_[l] = P_[l] % 2
    if P_ == P:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
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= map(int, input().split())

C=[]
for s in S:
    c=0
    for ss in s:
        c += 2**(ss-1)
    C.append(c)
result=0

for i in range(2**N):
    f = 0
    x = 0
    CC= copy.deepcopy(C)
    PP= copy.deepcopy(P)
    for c,p in zip(CC,PP):
        x = i&c
        #print(i,c,p,x)
        if bin(x).count("1")%2 == p:
                f+=1
    if f==len(C):
        result+=1
    #print(i)

print(result)

Submission status: Accepted

Solution code:
import sys
import os



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

KS=[0]*(M)
C=[0]*M
S=[0]*M

for i in range(M):
    KS[i] = list(map(int, input().split()))
    S[i]=KS[i][1:]
p = list(map(int,input().split()))
onsum=0
ans=0
for i in range(2**N):
    x=format(i, 'b')
    x_zero=x.zfill(N)
    s=list(x_zero)
    s=list(map(int,s))#スイッチの状態01010
    onsum=0
    #print(s)
    for j in range(M):#あるスイッチの状態に対して電球jがつくかどうか調べる
        on=0
        for k in S[j]:
            #print(s[k-1])
            on=on+s[k-1]
            #print("on=",on)
        if on%2==p[j]:
            onsum+=1
    if onsum==M:
        ans+=1

#print(N,M)
#print(KS)
#print(S)
print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
Sw = []
for i in range(M):
    k, *ss = list(map(int, input().split()))
    Sw.append((k, ss))
ps = list(map(int, input().split()))
for idx,p in enumerate(ps):
    Sw[idx] = (Sw[idx][0], Sw[idx][1], p)
# print(Sw)

def is_on(sw_i, strbi, pi):
    # print(sw_i, strbi, pi)
    return len(list(filter(lambda x:x, map(lambda i: bool(int(strbi[i-1])), sw_i[1]))))%2 == pi

cnt = 0

for strb in [str(bin(x))[2:] for x in range(0, 2**N)]:
    if all(map(lambda sw: is_on(sw, strb.zfill(N), sw[2]), Sw)):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
hoge=[]
for i in range(m):
  huga=list(map(int,input().split()))
  huga=huga[1:]
  hoge.append(huga)
moge=list(map(int,input().split()))
ans=0
for i in range(2**n):
  hi=0
  light=format(i, '010b')
  #ランプにjこめついて
  for j in range(m):
    kei=0
    #ボタンkこめについて
    for k in range(n):
      #print(light[-(k+1)],hoge[j].count(k+1))
      if(light[-(k+1)]=="1" and hoge[j].count(k+1)>0):
        kei+=1
    if(kei%2==moge[j]):
      hi+=1
  if(hi==m):
    ans+=1
    
print(ans)

Submission status: Accepted

Solution code:
N, M =list(map(int, input().split()))
ks_list = [list(map(int, input().split())) for _ in range(M)]
p_list = list(map(int, input().split()))
cnt = 0
for i in range(2**N):
    cond = bin(i)[2:].zfill(N)
    tmp = 1
    # cond = 11010: スイッチ1,2,4がON
    for j, ks in enumerate(ks_list):
        p = 0
        s_list = ks[1:]
        for s in s_list:
            p += int(cond[s-1])
        if (p%2 != p_list[j]):
            tmp = 0
            break
    if (tmp == 1):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
import itertools

N, M = (int(i) for i in input().split())
ks= [[int(i) for i in input().split()] for i in range(M)]
p = [int(i) for i in input().split()]
count = 0
comb = itertools.product(range(2), repeat = N)
comb = list(comb)
for ci in comb:
    FLAG = 1
    c = list(ci)
    #print(c)
    for i in range(M):
        count2 = 0
        for j in range(1, ks[i][0]+1):
            ##print(c)
            if c[ks[i][j]-1] == 1:
                count2+=1
            #print(count2, p[i])
        if count2%2 == p[i]:
            pass
        else:
            FLAG = 0
    if FLAG == 1:
        count +=1

print(count)

Submission status: Accepted

Solution code:
count = input().split()
switch = int(count[0])
bulb = int(count[1])

condition = []

for i in range(bulb):
    condition.append(input().split()[1:])

# 全ての可能なスイッチの組み合わせ
candidate = []
for j in range(2**switch):
    num = str(bin(j))[2:]
    if len(num) < (switch):
        num = '0'*(switch-len(num)) + num
    candidate.append(num)

wanted = input().split()

bad_count = 0

# 条件に合わないものから消していく
for i in range(len(candidate)):
    judge = 0
    for j in range(len(condition)):
        tasumono = [int(k)-1 for k in condition[j]]
        sum_switch = 0
        for l in tasumono:
            sum_switch += int(candidate[i][l])
        if sum_switch % 2 != int(wanted[j]):
            judge += 1
    if judge != 0:
        bad_count += 1

print(2**switch-bad_count)

Submission status: Accepted

Solution code:
import itertools as it

import copy

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

seq = [0, 1]

sw = list(it.product(seq, repeat=n))
sw_new = copy.copy(sw)

for sp_ele,p_ele in zip(sp, p):
    s = sp_ele[1:]
    for sw_ele in sw:
        cnt = 0
        for s_ele in s:
            cnt = cnt+sw_ele[s_ele-1]
        if cnt % 2 != p_ele and sw_ele in sw_new:
            sw_new.remove(sw_ele)

print(len(sw_new))

Submission status: Accepted

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

ll = [['0' for _ in range(N)] for __ in range(M)]
for i, ks in enumerate(kss):
  for k in ks[1:]:
    ll[i][k-1] = '1'

cnt = 0
for i in range(2**N):
  flag = True
  for j,l in enumerate(ll):
    if not flag: break
    oneNum = format(int(''.join(l), 2) & i, 'b').count('1')
    flag = (p[j]==int(oneNum%2))
  if flag: cnt += 1

print(cnt)

Submission status: Accepted

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

#各電球がつながっているスイッチの数
K = []

#各電球がつながっているスイッチの集合のリスト
S = []

for _ in range(M):
  ks = list(map(int, input().split()))
  K.append(ks[0])
  S.append(set(ks[1:]))
  
#各電球が偶数点灯(0)か奇数点灯(1)か
P = list(map(int, input().split()))
  
#条件を満たす組み合わせの数
cnt = 0

#0～2**N-1 最大1023(2**10)
for i in range(2**N):
  #全部onなら1のまま、1つでもoffになったら0にして次のループへ
  nowflag = 1
  #今回にiにおいてonになっているスイッチの集合をつくる
  nowon = set()
  for k in range(1,N+1):
    if i%(2**k)>=2**(k-1): nowon.add(k)
  
  #スイッチと電球につながっているスイッチの積集合をとり、
  #その集合のlen%2==Pならフラグそのまま、違ったらフラグを落としてループ抜け
  for j in range(M):
    if len(nowon&S[j])%2!=P[j]:
      nowflag = 0
      break
      
  if nowflag == 1: cnt += 1
#ループ終わり

print(cnt)

Submission status: Accepted

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

for i in range(2 ** N):
    hoge = bin(i + 1)
    hoge = str(hoge)
    hoge = hoge[2:]
    hoge = hoge.zfill(len(str(bin((2 ** N)))) - 2)
    result = True
    for j in range(M):
        onon = 0
        for k in s[j][1:]:
            if hoge[k] == "1":
                onon += 1
        if onon % 2 != p[j]:
            result = False
    if result:
        result2 += 1
print(result2)

Submission status: Accepted

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


def main():
    n, m = map(int, input().split())
    bools = [[0 for __ in range(n)] for _ in range(m)]

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

        for sii in si:
            bools[i][sii - 1] = 1

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

    for bit in range(1 << n):
        count = 0

        for mi in range(m):
            # pattern = list()
            total = 0

            for ni in range(n):
                if bit & (1 << ni):
                    total += bools[mi][ni]

            if total % 2 == p[mi]:
                count += 1

        if count == m:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

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

out = 0
for c in product(*[[0, 1]]*N):
    tf = []
    for i in range(M):
        count = sum([c[s-1] == 1 for s in S[i]])
        tf.append(count % 2 == p[i])
    out += int(all(tf))

print(out)

Submission status: Accepted

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

K = []
S = []

for m in range(M):
    X = list(map(int, input().split()))
    K.append(X[0])
    tmp = list(map(lambda x: x-1, X[1:]))
    S.append(tmp)

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

#print(N, M)
#print(K)
#print(S)
#print(P)


def strings2list(strings):
    l =  [int(c) for c in strings]
    size = len(l)
    return [0]*(N-size)+l

L = []
for i in range(2**N):
    bi = bin(i)[2:]
    l = strings2list(bi)
        
    flag = [0]*M
    
    
    
    for m in range(M):
        p = P[m]
        s = S[m]
        counter = 0
        for index in s:
            counter += l[index]
        if counter%2!=p:
            flag[m]=1
        
        
    if sum(flag) == 0:
        L.append(l)

print(len(L))    

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

Submission status: Accepted

Solution code:
n, m = [int(a) for a in input().split()]

S = [[int(i) for i in input().split()[1:]] for _ in range(m)]

mask = [sum([2 ** (x-1) for x in s]) for s in S]

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




count = 0
for j in range(2**n):
    for i in range(m):
        on_switch = [int(k) for k in list(format(j & mask[i], 'b'))]
        if not sum(on_switch) % 2 == p[i]:
            count -= 1
            break
    count += 1

print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from itertools import combinations
N, M = map(int, input().split())
K = [[int(i) for i in input().split()] for i in range(M)]
P = [int(i) for i in input().split()]

A = [0]*N
cnt = 0
a_sum = 0
for m in range(M):
    for y in K[m][1:]:
        a_sum += A[y-1]
    if a_sum % 2 != P[m]:
        break
        a_sum = 0
else:
    cnt += 1
for i in range(N):
    for x in list(combinations(range(N), i+1)):
        for e in x:
            A[e] = 1
        for m in range(M):
            a_sum = 0
            for y in K[m][1:]:
                a_sum += A[y-1]
            if a_sum % 2 != P[m]:
                break
        else:
            cnt += 1
        A = [0]*N
print(cnt)

Submission status: Accepted

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

def JudgeDigitN(x,n):
    return x >> n & 1 == 1
ans = 0
for i in range(2**N):
    can = True
    for line,amari in zip(connect,p):
        count = 0
        for s in line[1:]:
            if JudgeDigitN(i,s-1):
                count += 1
        if count%2 != amari:
            can = False
    if can:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

S = []
for i in range(M):
    s = list(map(int, input().split()))
    S.append(s[1:])
    
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: Accepted

Solution code:
from sys import stdin
import itertools
input = stdin.readline

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

sw=[]
for bits in itertools.product([0,1], repeat=n):
    sw.append(list(bits))

anscnt=0
for i in range(2**n):
    ans=True
    for j in range(m):
        count=0
        for k in range(1,ks[j][0]+1):
            count+=sw[i][ks[j][k]-1]

        if count%2!=p[j]:
            ans=False
    if ans:
        anscnt+=1

print(anscnt)

Submission status: Accepted

Solution code:
N, M = [int(v) for v in input().split()]
lights = []
for _ in range(M):
    lights.append(set([int(v) - 1 for v in input().split()[1:]]))

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

def patterns(n):
    limit = pow(2, n)
    for val in range(limit):
        flags = '{0:b}'.format(val).zfill(n)
        yield [int(v) for v in flags]

def judge(pattern, rule, check):
    summary = sum([pattern[i] for i in rule]) % 2
    return summary == check

cnt = 0
for pattern in list(patterns(N)):
  ok = all([judge(pattern, lights[i], P[i]) for i in range(M)])
  if ok:
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import itertools

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

light = [0 for i in range(n)]

ans = 0
for x in itertools.product(range(2), repeat=n):
    flag = 0
    for i in range(m):
        now = 0
        for j in range(1, len(ks[i])):
            #print(ks[i][j]-1)
            if x[ks[i][j]-1] == 1:
                now += 1
        #print(now)
        #print(x, p[i], now % 2,ks[i])
        if now % 2 != p[i]:
            flag = 1
            #break
    #print(flag)
    #print('')
    if flag == 0:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8
# CCCCCCCCCCCC

import math
import re

def inclement_bi(i):
    return bin(i)

def main(params):
    result = 0
    n,m = params[0]
    ks = params[1:]
    ps = ks.pop(-1).split()
    for i in range(2**n):
        bi = str(inclement_bi(i)).replace('0b','')
        if len(bi) < n:
            bi = '0' * (n-len(bi)) + bi
        cnt = 0
        chk = True
        for j in ks:
            tmp = j.split()
            k = tmp[0]
            s = tmp[1:]
            p = int(ps[cnt])
            total = 0
            for si in s:
                si = int(si) - 1
                if bi[si] == '1':
                    total += 1
            cnt += 1
            if total % 2 != p:
                chk = False
                break
        if chk == True:
            result += 1
    print result

if __name__ == "__main__":
    n,m = [int(i) for i in raw_input().split()]
    cnt = m + 1 # TODO: edit here
    params = [[n,m]]
    for i in range(cnt):
        param = raw_input()
        params.append(param)
    main(params)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
K = []; S = []
for _ 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):
    flag = 0
    stat = str(bin(i)[2:])
    stat = stat.rjust(N, "0")
    for j in range(M):
        p = 0
        for l in S[j]:
            p += int(stat[l-1])
        if p % 2 != P[j]:
            flag = 1
    if flag == 0:
        ans += 1

print(ans)

Submission status: Accepted

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

bulbs = []
for m in range(M):
    ks = map(int, input().split())
    bulbs.append(list(ks)[1:])

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

result = 0
for m in range(2**N):
    switches = list(map(int, list(str(bin(m))[2:])))
    switches = [0]*(N-len(switches)) + switches

    flag = True
    for idx, bulb in enumerate(bulbs):
        count = 0
        for switch in bulb:
            count += switches[switch-1]
        if count % 2 != P[idx]:
            flag = False
            break
    if flag:
        result += 1
print(result)

Submission status: Accepted

Solution code:
def dfs(depth, swich):
    if depth == N:
        global ans
        flg = True
        for i in range(M):
            cnt = 0
            for j in range(s[i][0]):
                if S[s[i][j+1]-1] == 1:
                    cnt += 1
            if cnt % 2 != p[i]:
                flg = False
        if flg:
            ans += 1
    else:
        S[depth] = swich
        dfs(depth+1, on)
        dfs(depth+1, off)

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
S = [None for i in range(N)]
on = 1
off = 0
dfs(0, on)
dfs(0, off)
print(ans//2)

Submission status: Accepted

Solution code:
n,m=map(int,input().split(' '))
ss=[]
for i in range(m):
    ss.append(list(map(lambda x:int(x)-1,input().split(' ')))[1:])
p=list(map(int,input().split(' ')))
c=0
for i in range(2**n):
    state=[1 if i&(2**j)>0 else 0 for j in range(n)]
    flag=1
    for index,j in enumerate(ss):
        if sum([state[x] for x in j])%2!=p[index]:
            flag=0
            break
    if flag==1:
        c+=1
print(c)

Submission status: Accepted

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

count=0
P=[0]*M
DATA=[]
for _ in range (M):
    DATA.append(list(map(int,input().split())))

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

for i in range(2**N):
    s=[0]*N

    for j in range(N):
        if (i >> j) & 1:
            s[j]=1
        else:
            s[j]=0
    for m in range(M):
        k=DATA[m][0]
        si=DATA[m][1:]
        sum=0
        for i in si:
            sum+=s[i-1]
        sum=sum%2
        if sum==P[m] and m==(M-1):
            count+=1
            continue
        elif sum!=P[m]:
            break


print(count)

Submission status: Accepted

Solution code:
def sol():
    n,m=map(int,input().split())
    k=[]
    for i in range(m):
        l=[int(i) for i in input().split()]
        k.append([l[j]-1 for j in range(1,l[0]+1)])
    p=[int(i) for i in input().split()]
    ans=0
    #for i in range(2**10):
    for i in range(2**n):
        s=bin(i)[2:]
        s="0"*(n-len(s))+s
        s=s[::-1]
        for a,j in enumerate(k):
            chk=f=0
            for x in j:
                if s[x]=="1":
                    chk+=1
            if chk%2!=p[a]:
                f=1
                break
        if f==0:
            ans+=1
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
import itertools
target = (0, 1)
N,M = map(int,input().split())
sk_ = [list(map(int,input().split())) for _ in range(M)]
P_ = list(map(int,input().split()))

max_n = 0
state = list(itertools.product(target,repeat=N))

for i in state:
  ons = 0
  #print(i)
  for j in range(M):
    num = 0
    for s in sk_[j][1:]:
      if i[s-1] == 1:
        num += 1
        #print('switch{} : on'.format(i[s-1]))
    #print('num : {}'.format(num))
    if num%2 == P_[j]:
      ons += 1
  #print('ons : {}'.format(ons))
  if ons == M:
    max_n += 1
    
print(max_n)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#ABC128C-Switches.py

from sys import stdin
import itertools

input = stdin.readline

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

switches = [i+1 for i in range(N)]
total = 0

for i in range(N+1):
    onSwitches = list(itertools.combinations(switches,i))
    if i == 0:
        onSwiches = [100]
    for onSwitch in onSwitches:
        i = 0
        for ks in KS:
            sum = 0
            for j in range(1,ks[0]+1):
                s = ks[j]
                if s in onSwitch:
                    sum += 1
            if sum % 2 != P[i]:
                break
            i += 1
        else:
            total += 1

print(total)





"""
switches = [[0 for _ in range(M)] for _ in range(N)]
allSwitches = [i for i in range(N)]
totalNumber = 0

for i in range(M):
    ks = list(map(int, input().split()))
    for j in range(1,len(ks)):
        switches[ks[j]-1][i] = 1

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

def check(list):
    if P == [a%2 for a in list]:
        return 1
    else:
        return 0

for i in range(N+1):
    cList = list(itertools.combinations(allSwitches,i))
    for clist in cList:
        sumList = [0 for _ in range(N)]
        for c in clist:
            sumList = [x+y for (x,y) in zip(sumList,switches[c])]
        totalNumber += check(sumList)
    if cList == []:
        asumList = [0 for _ in range(N)]
        totalNumber += check(asumList)


print(totalNumber)
"""

Submission status: Accepted

Solution code:
n,m=list(map(int, input().split()))
D=[]
for _ in range(m):
    tmp=list(map(int, input().split()))
    D.append(tmp)
P=list(map(int, input().split()))
ans=0
import itertools
for flags in itertools.product([0,1], repeat=n):
    total = 0
    for i in range(m):
        tmp=0
        for sw in D[i][1:]:
            tmp+=flags[sw-1]
        mod=tmp%2
        if mod==P[i]:
            total+=1
    if total==m:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import defaultdict


possible_numbers = [0, 1]
num_switch, num_lamp = map(int, input().split(' '))

lamp_connection = defaultdict(list)
for i in range(0, num_lamp):
    divided_input = input().split(' ')
    del(divided_input[0])
    connected_switches = [int(x)-1 for x in divided_input]

    for switch in connected_switches:
        lamp_connection[switch].append(i)

mods = tuple(map(int, input().split(' ')))

trials = itertools.product(possible_numbers, repeat=num_switch)


num_success = 0
for switch_state in trials:
    sums = defaultdict(int)
    for index, statement in enumerate(switch_state):
        targets = lamp_connection[index]
        for target in targets:
            sums[target] += statement

    for i in range(0, num_lamp):
        if sums[i] % 2 != mods[i]:
            break
    else:
        num_success += 1

print(num_success)
exit(0)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k,s = [],[]

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

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

ans = 0
for bit in range(2 ** n):
    for rep in range(m):
        counter = 0
        for rep2 in s[rep]:
            if((bit >> (rep2-1)) & 1):
                counter += 1

        if counter % 2 != p[rep]:
            break

    else:
        ans += 1

print(ans)