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())
grid = []
for i in range(m):
    array = list(map(int, input().strip().split(' ')))
    grid.append(array)
plist = list(map(int, input().split()))


checklist = [ [int((format(i, 'b').zfill(n))[j]) for j in range(n)] for i in range(2**n)]
answer = 0

for i in range(2**n):
    light = checklist[i]
    cpoint = 0
    for j in range(m):
        switches = grid[j][1:]
        point = 0
        for k in range(len(switches)):
            point += light[switches[k]-1]
        if point % 2 == plist[j]:
            cpoint += 1
    if cpoint == m:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
#C switch
n,m=map(int,input().split())
ks=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
data=[0 for i in range(n+1)]
s=0
for i in range(2**n):
    for j in range(n):
        if (i>>j&1)==1:
            data[j+1]=1
        else:
            data[j+1]=0
    for k in range(m):
        a=0
        for l in range(1,ks[k][0]+1):
            a=(a+data[ks[k][l]])%2
        if a!=p[k]:
            break
    else:
        s+=1
print(s)

Submission status: Accepted

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


def main():
    N, M = [int(x) for x in input().split()]
    k = []
    s = [[] for _ in range(M)]
    for i in range(M):
        A = [int(x) for x in input().split()]
        k.append(A[0])
        s[i].extend(A[1:])

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

    ans = 0
    for i in range(2 ** N):
        switch = bin(i)
        switch = switch[2:]
        switch_len = len(switch)
        switch = '0' * (N - switch_len + 1) + switch
        for j in range(M):
            total = 0
            for l in s[j]:
                total += int(switch[l])
            if total % 2 != p[j]:
                break
            if j == M - 1:
                ans += 1

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a=[]
for _ in range(m):
    a.append(list(map(int,input().split())))
    a[-1].pop(0)
p = list(map(int,input().split()))
res = 0

for i in range(0,2**n):
    flag = 0
    bis = bin(i)
    bi = bis[2:]
    bi = '0' * (n-len(bi)) + bi
    for k in range(0,len(a)):
        sumk = 0
        for j in range(0,len(a[k])):
            sumk += int(bi[a[k][j]-1])
        if sumk %2 == p[k]:
            flag += 1
    if flag == len(a):
        res += 1

print(res)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
time = [0 for _ in range(n)]
def nex(time):
  for i in range(n):
    if time[i] == 0:
      time[i] += 1
      break
    else:
      time[i] = 0
  else:
    time = 'over'
  return time
s = []
for _ in range(m):
  raw = list(map(int,input().split()))
  add = [0 for _ in range(n)]
  for j in range(1,raw[0]+1):
    add[raw[j]-1] = 1
  s.append(add)
p = list(map(int,input().split()))
ans = 0
while time != 'over':
  for k in range(m):
    tmp = p[k]
    for i in range(n):
      tmp ^= time[i] * s[k][i]
    if tmp == 1:
      break
  else:
    ans += 1
  time = nex(time)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
connects = []
for _ in range(M):
    connect = list(map(int, input().split()))
    connects.append(connect[1:])

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

def check(state):
    is_ok = True
    for connect,p in zip(connects, P):
        switch_count = 0
        for switch in connect:
            shift = switch - 1
            switch_bit = 1<<shift
            if (switch_bit & state) > 0:
                switch_count +=1

        if switch_count % 2 != p:
            is_ok = False
            break

    return is_ok


full_state = 2**N

count = 0
for state in range(full_state):
    if check(state):
        count += 1


print(count)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
ks = []
for i in range(m):
    b = list(map(int, input().split()))
    ks.append(b)

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

for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if (i>>j)&1:
            switch[j] = 1
    flag = 0
    for j in range(m):
        count = 0

        for k in range(len(ks[j])-1):
            if switch[ks[j][k+1]-1]==1:
                count+=1
        
        if not count%2 ==p[j]:
            flag = 1
    
    if flag == 0:
        ans +=1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,m=map(int,input().split())
    switch=[0]*n
    for i in reversed(range(m)):
        k,*S=map(int,input().split())
        for s in S:
            switch[s-1]+=1<<i
    p=int(input().replace(' ',''),2)
    # calculate
    ans=0
    for k in range(2**n):
        xor=0
        for i in range(n):
            if k&(1<<i):
                xor^=switch[i]
        if xor==p: ans+=1
    print(ans)
resolve()

Submission status: Accepted

Solution code:
def slove():
    import sys
    import itertools
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    ks = [list(map(int, input().rstrip('\n').split())) for _ in range(m)]
    p = list(map(int, input().rstrip('\n').split()))
    ls = [True, False]
    cnt = 0
    for it in itertools.product(ls, repeat=n):
        b = True
        for j, v in enumerate(ks):
            tc = 0
            for i in range(len(v)):
                if i != 0:
                    if not it[v[i]-1]:
                        tc += 1
            if tc % 2 != p[j]:
                b = False
        if b:
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    slove()

Submission status: Accepted

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

for i in ks:
	i.pop(0)
	
ans=0

for light in itertools.product([0,1], repeat=N):
	ok=True
	for _index, _list in enumerate(ks):
		_sum=0
		for s in _list:
			_sum += light[s-1]
		if _sum%2 != p[_index]:
			ok=False
			break
	if ok is True:
		ans+=1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

ans = 0
switch_pattern_num = 2**N

for i in range(switch_pattern_num):
    binary = format(i,'0%ib'%N)
    satisfied = True
    for j,S in enumerate(Ss):
        count = 0
        for e in S:
            if int(binary[e-1]):
                count += 1
        if count % 2 != Ps[j]:
            satisfied = False
    if satisfied:
        ans += 1
print(ans)

Submission status: Accepted

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

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

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

ans=0
for i in range(2**n):
  tmp=0
  f=1
  for mm in range(m):
    tmp=0
    for j in info[mm][1:]:
      tmp+=int(str(format(i,'b').zfill(n))[int(j)-1])
    if tmp%2!=p[mm]:
      f=0
  if f==1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = [set()] * m
for i in range(m):
    s[i] = set(list(map(lambda x: int(x)-1, input().split()))[1:])
p = list(map(int, input().split()))

ans = 0

for i in range(2 ** n):
    lights = set()
    for j in range(n):
        if ((i >> j) & 1):
            lights.add(j)
    
    for j in range(m):
        if len(s[j] & lights) % 2 != p[j]: break
    else: ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
arr = []
for i in range(m):
    arr.append(list(map(int, input().split())))
arr = [[0] + list(map(int, input().split()))] + arr
ans = 0
for i in range(2**n):
    light = []
    for j in range(n):
        light.append(i >> j & 1)
    cnt = 0
    for k in range(1, m+1):
        judge = 0
        for s in range(1, len(arr[k])):
            judge += light[arr[k][s]-1]
        judge %= 2
        if judge == arr[0][k]:
            cnt += 1
    if cnt == m:
        ans += 1
print(ans)

Submission status: Accepted

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

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

p=list(map(int,input().split()))
#以上入力

def binary_ume(N,K):  #Nを2進数表示し、K桁まで0埋めする
    A = []
    while N >= 2:
        A.append(N%2)
        N = N//2
    A.append(N)
    while len(A) < K:
        A.append(0)
    return A

ans = 0

for i in range(m):
    for j in range(1,len(k[i])):
        k[i][j] -= 1

for i in range(2**n):
    switch = binary_ume(i,n)  #スイッチの推し方全部見る
    all_on = 1  #何かひとつでもダメならすぐ切る
    for j in range(m):
        if sum(switch[l] for l in k[j][1:])%2 != p[j]:
            all_on = 0
            break
    if all_on == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,M=map(int,input().split())
l=[]*M

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

count=0
s=[-1]*10

for i in range(2):
    s[0]=i
    for ii in range(2):
        s[1]=ii
        for iii in range(2):
            s[2]=iii
            for iiii in range(2):
                s[3]=iiii
                for iiiii in range(2):
                    s[4]=iiiii
                    for iiiiii in range(2):
                        s[5]=iiiiii
                        for iiiiiii in range(2):
                            s[6]=iiiiiii
                            for iiiiiiii in range(2):
                                s[7]=iiiiiiii
                                for iiiiiiiii in range(2):
                                    s[8]=iiiiiiiii
                                    for iiiiiiiiii in range(2):
                                        s[9]=iiiiiiiiii
                                        #いかれてる
                                        for j in range(M):
                                            sum=0
                                            is_success=True
                                            for item in l[j]:
                                                sum=sum^s[item-1]
                                            if sum!=p[j]:
                                                is_success=False
                                                break
                                        if is_success:
                                            count+=1
                                            
print(int(count/2**(10-N)))

Submission status: Accepted

Solution code:
import numpy as np

def test():
    n,m = map(int,input().split())
    s = []
    count = 0
    for i in range(m):
        a = list(map(int,input().split()))
        s.append(a[1:])
    p = np.array(list(map(int,input().split())))

    for i in range(2**n):
        result = np.array([(i>>j)&1 for j in range(n)])
        if all(p == [sum(result[np.array(i)-1])%2 for i in s]):
            count += 1
    print(count)


if __name__ == "__main__":
    test()

Submission status: Accepted

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

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

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


def check_switch(ss):
    for i in range(m):
        sum_switch = 0
        for j in range(k[i]):
            sum_switch += ss[s[i][j] - 1]
        if sum_switch % 2 != p[i]:
            return 0
    return 1


def check(switches, l):
    if l == n:
        return check_switch(switches)
    return check(switches+[0], l + 1) + check(switches+[1], l + 1)


print(check([], 0))

Submission status: Accepted

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

k=[]
for _ in range(m):
  t = list(map(int,input().split()))[1:]
  j=0
  for i in t:j+=2**(i-1)
  k.append(j)

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

def checkMod(binStr,swStr,p):
  return 1 if bin(binStr & swStr).count("1")%2==p else 0

result=0

for i in range(2**n):
  count=1
  for j in range(m):
    count=count*checkMod(i,k[j],p[j])
    if count==0:
      break
  if count==1:
    result+=1

print(result)

Submission status: Accepted

Solution code:
def main(): 
    
    switch_cnt,bulb_cnt = map(int, input().split())

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

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

    cnt = 0
    for i in range(2 ** switch_cnt):

        switch_status = [False for _ in range(switch_cnt)]

        j = 0
        while i > 0b0:
            if i & 0b1 == 0b1:
                switch_status[j] = True
            i = i >> 1
            j += 1

        for ki in range(len(k)):
            on_count = 0
            for kj in range(1,len(k[ki])):
                switch_no = k[ki][kj] - 1
                if switch_status[switch_no]:
                    on_count += 1
            if on_count % 2 != p[ki]:
                break
        else:
            cnt += 1
    print(cnt)          


if __name__ == "__main__":
    main()

Submission status: Accepted

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

#rule light switch
k=[]
for _ in range(m):
  temp = list(map(int,input().split()))[1:]
  inp=0
  for i in temp:
    inp+=2**(i-1)
  k.append(inp)

#number of on/off 
p=list(map(int,input().split()))

#print(k)

#binStr is status of switch
#swStr is target of switch 
#p is odd or even
def checkMod(binStr,swStr,p):
  #print(bin(binStr),bin(swStr))
  #print(">>",bin(binStr & swStr))
  if bin(binStr & swStr).count("1")%2==p:
    return 1
  else:
    return 0
  

  
result=0

for i in range(2**n):
  count=1
  for j in range(m):
    count=count*checkMod(i,k[j],p[j])
    if count==0:
      break
  if count==1:
    result+=1

print(result)

Submission status: Accepted

Solution code:
def f_c():
    n, m = map(int, input().split())
    l = []
    for _ in range(m):
        _, *s = map(lambda x: int(x)-1, input().split())
        sb = 0
        for si in s:
            sb |= 1<<si
        l.append(sb)
    *p, = map(int, input().split())

    a, c = 0, 0
    for i in range(1<<n):
        for j, sb in enumerate(l):
            if bin(i&sb).count("1")%2!=p[j]:
                break
            else:
                c += 1
        a = a+1 if c==m else a
        c = 0
    print(a)

if __name__ == "__main__":
    f_c()

Submission status: Accepted

Solution code:
from itertools import product
N, M = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(M)]
P = list(map(int, input().split()))
result = 0
for switches in product((0, 1), repeat=N):
    for s, p in zip(S, P):
        num = sum([switches[s_ - 1] for s_ in s[1:]])
        if num % 2 != p:
            break
    else:
        result += 1
print(result)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
S=[list(map(int,input().split())) for _ in range(m)]
P=list(map(int,input().split()))

ans=0
for i in range(2**n):
  on=[0 for _ in range(n)]
  tmp=i
  for j in range(n):
    if tmp%2==1:
      on[j]=1
    tmp//=2
  flag=True
  for j in range(m):
    cnt=0
    for k in range(1,S[j][0]+1):
      cnt+=on[S[j][k]-1]
    if cnt%2!=P[j]:
      flag=False
      break
  if flag:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

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

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

count = 0
for i in range(2 ** N):
    switchs = []
    for j in range(N):
        if ((i >> j) & 1):
            # ON
            switchs.append(1)
        else:
            # OFF
            switchs.append(0)

    # 1-index に
    switchs = [0] + switchs
    is_on = True
    for x in range(len(KS)):
        k, *s = KS[x]
        # onの数
        on = 0
        for z in s:
            if switchs[z] == 1:
                on += 1

        if on % 2 == P[x]:
            pass
        else:
            is_on = False

    if is_on:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N, M=map(int, input().split())
switches=[list(map(int, input().split())) for _ in range(M)]
p=list(map(int, input().split()))
ans=0
for i in range(2**N):
  on=[0 for _ in range(N)]
  tmp=i
  for j in range(N):
    if tmp%2==1:
      on[j]=1
    tmp=tmp//2
  flag=True
  for j in range(M):
    switch=switches[j]
    cnt=0
    for k in range(1, switch[0]+1):
      cnt+=on[switch[k]-1]
    if cnt%2!=p[j]:
      flag=False
      break
  if flag:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
num_of_switch,num_of_denkyu = map(int,input().split())

denkyu_switch_connection = []
for denkyu in range(num_of_denkyu):
    denkyu_switch_connection.append(list(map(lambda x:int(x)-1,input().split())))
    del denkyu_switch_connection[denkyu][0]

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


ans=0
for pattern in range(2**num_of_switch):#スイッチのオンオフを全ての通り＝（2のスイッチの数乗）通り考える
    denkyu_True_or_False=[False for _ in range(num_of_denkyu)]#電球がそれぞれ点灯するかどうか
    switch_on_off = list(map(int,list(str(bin(pattern)).replace("0b","").zfill(num_of_switch))))#スイッチのonoff
    
    for i in range(num_of_denkyu):#電球
        count=0#電球iに繋がっているスイッチのうち、オンのものの数
        for j in range(len(denkyu_switch_connection[i])):#電球iに繋がっているスイッチ
            if switch_on_off[denkyu_switch_connection[i][j]]==1:#電球iに繋がっているスイッチijがonのとき
                count += 1
        
        if count%2 == surplus[i]:
            denkyu_True_or_False[i]=True
        else:break

    if False not in denkyu_True_or_False:#電球がすべてオンの時
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
num_of_switch,num_of_denkyu = map(int,input().split())
denkyu_switch = []
for denkyu in range(num_of_denkyu):
    denkyu_switch.append(list(map(lambda x:int(x)-1,input().split())))
    del denkyu_switch[denkyu][0]
surplus = list(map(int,input().split()))


ans=0
for i in range(2**num_of_switch):
    denkyu_on_off=[False for _ in range(num_of_denkyu)]
    switch_on_off = list(map(int,list(str(bin(i)).replace("0b","").zfill(num_of_switch))))


    for denkyu in range(len(denkyu_switch)):
        count=0
        for switch in range(len(denkyu_switch[denkyu])):
            
            if switch_on_off[denkyu_switch[denkyu][switch]]==1:
                count += 1
        
        if count%2 == surplus[denkyu]:
            denkyu_on_off[denkyu]=True
        else:break

    if False not in denkyu_on_off:
        ans+=1
print(ans)

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

Submission status: Accepted

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

ans=0
baai=2**n

for i in range(baai):
  sta=str(bin(i)[2:].zfill(n))
  #print(sta)
  temp=0
  for t,j in enumerate(k): #各k列に対し
    wa=0
    for x in j[1:]:
      wa+=int(sta[x-1])
    if wa%2==p[t]: #電球の点灯判定
      #print("おｋ")
      temp+=1
  if temp==m:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ans = 0
lights = []
for i in range(m):
  lights.append(list(map(lambda x: int(x)-1, input().split()[1:])))
p = list(map(int, input().split()))

from copy import copy
on_off = []
def search(l, on):
  new_l = copy(l)  
  new_l.append(on)
  if len(new_l) < n:
    search(new_l, 1)
    search(new_l, 0)
  else:
    on_off.append(new_l)
search([], 0)
search([], 1)

ans = 0
for states in on_off:
  for j in range(m):
    s = 0
    for i in range(n):
      if states[i] == 1 and i in lights[j]:
        s += 1
    if s % 2 != p[j]:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = (int(i) for i in input().split())
s = [0] * M
for i in range(M):
    s[i] = list(map(int,input().split()))
p = list(map(int,input().split()))
cnt = 0
sw = [1] * N
tmp = 0
ans = 0
for i in range(1,N):
    sw[i] = sw[i-1] * 2
while cnt < 2**N:
    flag = 1
    for i in range(M):
        tmp = 0
        for j in range(s[i][0]):
            x = cnt % (2**(s[i][j+1]))
            if x >= 2**(s[i][j+1]-1):
                tmp += 1
        tmp %= 2
        if tmp != p[i]:
            flag = 0
            break
    cnt += 1
    if flag == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
k=[]
for j in range(0,M):
    k.append([int(x) for x in input().split()])
    k[j]=k[j][1:]
p=[int(x) for x in input().split()]
condition=[0]*M
sum_=0
for u in range(0,2**N):
    switch=list(bin(u)[2:].zfill(N))
    for i in range(0,M):
        condition[i]=0
        for j in k[i]:
            condition[i] += int(switch[j-1])
        condition[i] = condition[i] % 2
    #print(switch,condition)
    sum_ += (condition==p)
print(sum_)

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
K =[list(map(int,input().split())) for _ in range(M)]
P = list(map(int,input().split()))

prod = list(itertools.product([0,1], repeat = N))
cnt = 0
for i in range(len(prod)):
  judge = True
  for j in range(M):
    temp = 0
    for k in range(K[j][0]):
      if prod[i][K[j][k+1]-1] == 1:
        temp += 1
    if temp % 2 != P[j]:
      judge = False
  if judge == True:
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
L = [list(map(int,input().split()))[1:] for _ in range(m)]
P = list(map(int,input().split()))
ans = 0
for i in range(2 ** n):
  on = bin(i)[2:].zfill(n)
  for s,p in zip(L,P):
    if sum(int(on[sij-1]) for sij in s) % 2 != p:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
K = []
S = []
N,M = map(int,input().split())
for i in range(M):
    tmp = [int(i) for i in input().split()]
    K.append(tmp[0])
    tmp.pop(0)
    S.append(tmp)
P = [int(i) for i in input().split()]
List = []
for i in range(2**N):
    tmp = []
    for j in range(N):
        if ((i>>j) & 1):
            tmp.append('1')
        else:
            tmp.append('0')
    List.append(tmp)

for i in range(M):
    kouho = []
    for j in range(len(List)):
        cnt = 0
        for k in range(len(List[j])):
            if List[j][k] == '1':
                if k+1 in S[i]:
                    cnt += 1
        if cnt % 2 != P[i] and not List[j] in kouho:
            kouho.append(List[j])
    for x in kouho:
        List.remove(x)
print(len(List))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
K = []
S = []
ans = 0
for _ in range(M):
    tmp = list(map(int, input().split()))
    k, s = tmp[0], tmp[1:]
    K.append(k)
    S.append(s)
P = [int(p) for p in input().split()]
for i in range(2**N):
    cnt = [0]*M
    f = 0
    for m, s in enumerate(S):
        for j in s:
            if ((i >> (j-1)) & 1):
                cnt[m] += 1
        for m in range(M):
            if cnt[m] % 2 != P[m]:
                f = 0
                break
            f = 1
    if f:
        ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
B = {}
for i in range(1,M+1):
    row = list(map(int,input().split()))
    row.pop(0)
    B[i] = row
P = list(map(int,input().split()))
P.insert(0,-1)
cnt = 0
for x in itertools.product((0,1),repeat=N):
    ind = 1
    for i in range(1,M+1):
        sw = 0
        for j in B[i]:
            if x[j-1]==1:
                sw += 1
        if sw%2!=P[i]:
            ind = 0
            break
    if ind==1:
        cnt += 1
print(cnt)

Submission status: Accepted

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

res = 0
for i in range(2 ** N):
    is_ok = True
    for j in range(M):
        bit_sum = 0
        r_bin = list(map(int, reversed(bin(i)[2:].rjust(N, '0'))))
        for s in ks[j][1:]:
            bit_sum += r_bin[s - 1]
        if bit_sum % 2 != p[j]:
            is_ok = False
    if is_ok:
        res += 1

print(res)

Submission status: Accepted

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

ans = 0
for patterns in range(2**n):
    ptn = bin(patterns)[2:].rjust(n, '0')
    light = True
    for i in range(m):
        num = 0
        for j in range(len(k[i])):
            num += int(ptn[k[i][j] - 1])
        if ((num+p[i]) % 2 == 1):
            light = False
    if light:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s = [list(map(lambda s: int(s) - 1, input().split()))[1:] for _ in range(M)]
p = list(map(int, input().split()))
# print(s)
# print(p)
ret = 0
for i in range(2 ** N):
    on = list(map(int, bin(i)[2:]))
#     print(on)
    on = ([0] * N + on)[-N:]
#     print(on)
    for si, pi in zip(s, p):
        if sum(on[sij] for sij in si) % 2 != pi:
            break
    else:
        ret += 1
print(ret)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
switch = [format(i, '010b') for i in range(2**n)]
s = [[int(j) for j in input()[1:].split()] for i in range(m)]
p = [int(i) for i in input().split()]
ans = 0

for sw in switch:
    for pi, si in zip(p, s):
        total = 0
        for x in si:
            total += int(sw[-x])
        if total % 2 != pi:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

ret = 0
for i in range(2 ** N):
    on = list(map(int, bin(i)[2:]))
    on = ([0] * N + on)[-N:]
    for si, pi in zip(s, p):
        if sum(on[sij] for sij in si) % 2 != pi:
            break
    else:
        ret += 1
print(ret)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = [list(map(int, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
count = 0

for _ in range(2 ** n):
    pattern = list(map(int, list(bin(_)[2:].zfill(n))))
    if all(sum(pattern[sw2 - 1] for sw2 in ss ) % 2 == pp for ss, pp in zip(s, p)):
        count += 1
print(count)

Submission status: Accepted

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

a = [0 for _ in range(N)]
ans = 0
p = 0

# pを2進数で表示(電球のラベルの番号が大きい方が2進数で左にくるので注意(以下もそうなっている))
for i in range(M):
    x = plist[i]
    p |= x << i


# aにスイッチと電球の繋がりの情報を入れる(1なら繋がっている,0なら繋がっていない)
for i in range(M): # iは電球のラベル
    k = ks[i][0]
    for j in range(1, k+1): # jは繋がりのラベル
        s = ks[i][j] - 1 # sは電球iと繋がっているスイッチ(0からに直しておく)
        a[s] |= 1 << i # 元のa[s]と1<<iのORをとったものを新たにa[s]に代入


for s in range(1 << N): # sはスイッチの全ての状態をとる(0以上1<<N未満。N=3のとき1<<Nは1000=8であり、sは000=0,001,010,...,111=7までとれる。つまり1<<Nを2**Nとかいても同じこと。)
    t = 0
    for i in range(N): # 0以上N未満
        if s >> i & 1: # s >> iの最下位bitが立っているか(s>>1を右から見てi番目が1かどうか),0のときFalseそれ以外でTrue
            t ^= a[i]
    if t == p:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
S = []
for _ in range(M):
  s_list = ['0' for _ in range(N)]
  for s in list(map(int, input().split()))[1:]:s_list[s-1] = '1'
  S.append(int(''.join(s_list),2))

P = list(map(int, input().split()))
ans = 0
for i in range(2**N):
  flag = True
  for idx, s in enumerate(S):
    if bin(i&s)[2:].count('1')%2 != P[idx]:
      flag = False
      break
  if flag is True: ans += 1
print(ans)

Submission status: Accepted

Solution code:
#coding utf-8
N,M=map(int,input().split())
S =[[int(i) for i in input().split()] for i in range(M)]
p =list(map(int,input().split())) 
ans=0
for i in range(2**N):
  x=bin(i)[2:]
  x="0"*(N-len(x))+x
  for j in range(M):
    tmp=0
    for k in range(1,S[j][0]+1):
      tmp+=int(x[N-S[j][k]:N-S[j][k]+1])
    if tmp%2 != p[j]:
      break
    if j==M-1:
      ans+=1
    
print(ans)

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

n_pattern = 2 ** n
count = 0
for i in range(n_pattern):
    for j in range(m):
        current = 0
        for k in range(ks[j][0]):
            current += 2 ** (ks[j][k + 1] - 1)
        mod = bin(i & int(current)).count('1') % 2
        if mod != p[j]:
            break
        if j == m - 1:
            count += 1
print(count)

Submission status: Accepted

Solution code:
while True:
    try:
        N, M = map(int, input().split())
        
        K = []
        S = []
        for _ in range(M):
            k, *s = map(int, input().split())
            K.append(k)
            S.append(list(map(lambda x:x-1, s)))
        
        p = list(map(int, input().split()))
        ans = 0
        # N switches have 2**N combinations of "on"/"off" state
        for i in range(1<<N):
            flag = True
            for j in range(M):
                cnt = 0
                for k in S[j]:
                    if (i >> k) & 1:
                        cnt += 1
                if cnt%2 != p[j]:
                    flag = False
                    break
            if flag:
                ans += 1
                
        print(ans)
    except:
        break