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())
S=[list(map(int,input().split()))[1:] for i in range(m)]
P=list(map(int,input().split()))
cnt=0
for i in range(2**n):
    pattern=format(i,"b").zfill(n)
    point=0
    for j in range(m):
        swi=0
        for k in S[j]:
            if pattern[k-1]=="1":
                swi +=1
        if swi%2==P[j]:
            point +=1
    if point==m:
        cnt +=1

print(cnt)

Submission status: Accepted

Solution code:
from itertools import product
n, m = (int(x) for x in input().split())
s = [[int(x) for x in input().split()[1:]] for _ in range(m)]
p = [int(x) for x in input().split()]
ans = 0
for combo in product([0, 1], repeat=n):
    for i, bulb in enumerate(s):
        on = 0
        for switch in bulb:
	        if (combo[switch-1] == 1):
                    on += 1
        if (on % 2) != p[i]:
            break
    else:
      ans += 1
print(ans)

Submission status: Accepted

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

MOD = 2  # type: int



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

    ans = 0
    
    for i in range(1<<N):
        t = [0] * M
        for j in range(N):
            if i>>j & 1:
                for r in range(M):
                    # print(j+1, s[r])
                    if j+1 in s[r]:
                        t[r] += 1
        f = True
        for j in range(M):
            if t[j]%2 != p[j]:
                f = False
        
        if f:
            ans += 1

    print(ans)
    
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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**n):
    tmp=array([t>>s&1 for s in range(n)])
    if p==[sum(tmp[array(i)-1])%2for i in l]:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
binlist=[]
for j in range(2**n):
    binlist.append(format(j,"0%ib"%n))
lista=[]
for i in range(k):
    a=list(map(int,input().split()))
    lista.append(a)
modlist=list(map(int,input().split()))
ans=0
for some in binlist:
    flag=True
    for j in range(k):
        checker=lista[j][1:]
        p=modlist[j]
        count=0
        for nums in checker:
            if some[nums-1]=="1":
                count+=1

        if count%2!=p:
            flag=False
            break
    if flag:
        ans+=1     
print(ans)

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
temp = [0]*N
for i in range(2**N):
    for j in range(N):
        if((i >> j) & 1):
            temp[j] = 1

    for k in range(M):
        count = 0
        for l in range(1, len(S[k])):
            if temp[S[k][l] - 1] == 1:
                count += 1
        if count % 2 != p[k]:
            break
    else:
        ans += 1
    temp = [0]*N

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
switch = []
for idx in range(M):
	tmp = [ int(x) - 1 for x in input().split()]
	tmp = tmp[1:]
	switch.append(set(tmp))
P = list(map(int, input().split()))

ans = 0
for combi in range(2**N):
	ok = True
	for idx in range(len(switch)):
		count = 0
		for i in range(N):
			if((combi>>i)&1 and  i in switch[idx]):
				count += 1
		if(count%2 != P[idx]):
			ok = False

	if(ok):
		ans += 1
print(ans)

Submission status: Accepted

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

ans = 0

for x in range(2 ** N):
    for m in range(M):
        c = 0
        for k in range(1, L[m][0]+1):
            ks_mk = -L[m][k]
            if int(format(x,'b').zfill(10)[ks_mk]) == 1:
                c += 1
        if c % 2 != P[m]:
            break
        if m == M-1:
            ans +=1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

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

for x in range(2 ** N):
#     print("===========", x, ans)
    for m in range(M):
        c = 0
        for k in range(1, ks_list[m][0]+1):
            ks_mk = -ks_list[m][k]
            if int(format(x,'b').zfill(10)[ks_mk]) == 1:
                c += 1
#             print(ks_list, ks_list[m][k], ks_mk, format(x,'b').zfill(10), format(x,'b').zfill(10)[ks_mk])
#         print(c, p[m])
        if c % 2 != p[m]:
#             print("break")
            break
        if m == M-1:
            ans += 1
#     print(ans, ks_list, c, p)

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
list1 = [list(map(int,input().split())) for i in range(m) ]
p_list = list(map(int,input().split()))
binary_list = []
switch_count = 0
ans = 0
for i in range(2**n):
	binary_list = list(format(i,"b").zfill(n))
	switch_count = 0
	for j in range(m):
		for k in range(list1[j][0]):
			if binary_list[list1[j][k+1]-1] == "1":
				switch_count += 1
		if (switch_count % 2 == p_list[j]):
			if j == m-1:
				ans += 1
				switch_count = 0
			else:
				switch_count = 0
				continue
		else:
			break

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
K = []
for i in range(M):
    tes = list(map(int,input().split()))[1:]
    K.append( int("".join(["1" if i in tes else "0" for i in range(1,N+1)]),2) )
P = list(map(int,input().split()))

isOn = lambda n,k,p: bin(n&k).count("1")%2 == p

ans = 0
for i in range(2**N):
    ks = [not(isOn(i,K[e],P[e])) for e in range(M)]
    if sum(ks) == 0:
       ans += 1 
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import product

n, m = map(int, stdin.readline().rstrip().split())
switches = [list(map(int, stdin.readline().rstrip().split())) for _ in range(m)]
ps = list(map(int, stdin.readline().rstrip().split()))
res = 0
for p in product([0,1], repeat=n):
    flag = 0
    for i, s in enumerate(switches):
        total = 0
        for j in s[1:]:
            total += p[j-1]
        if total % 2 != ps[i]:
            flag = 1
            break
    if flag == 0:
        res += 1
print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import stdin


def main():
    input = lambda: stdin.readline()
    N, M = map(int, input().split())
    KS = [list(map(int, input().split())) for _ in [0] * M]
    P = tuple(map(int, input().split()))

    sw = defaultdict(list)
    for i, ks in enumerate(KS, start=1):
        for s in ks[1:]:
            sw[s].append(i)

    ans = 0
    for mask in range(1 << N):
        light = [0] * M
        sum_ = []
        for i in range(N):
            if mask & 1 << i:
                sum_ += sw[i+1]
        for i in sum_:
            light[i-1] ^= 1
        if P == tuple(light):
            ans += 1
    print(ans)


main()

Submission status: Accepted

Solution code:
def slove():
    import sys
    import bisect
    import collections
    import fractions
    import heapq
    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()))
    a_cnt = 0
    for v in itertools.product([True, False], repeat=n):
        b = True
        for j, vv in enumerate(ks):
            cnt = 0
            for i in range(vv[0]):
                if v[vv[i+1]-1]:
                    cnt += 1
            if cnt % 2 != p[j]:
                b = False
                break
        if b:
            a_cnt += 1
    print(a_cnt)


if __name__ == '__main__':
    slove()

Submission status: Accepted

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


def switches():
    n, m = map(int, input().split())
    states = [input().split() for _ in range(m)]
    p = list(map(int, input().split()))

    ans = 0
    for i in range(2 ** n):
        on_off = ['off'] * n
        count = [0] * m
        for j in range(n):
            if i >> j & 1:
                on_off[j] = 'on'
        for k in range(len(states)):
            v = states[k]
            for l in range(len(v)):
                if l == 0:
                    continue
                if on_off[int(v[l])-1] == 'on':
                    count[k] += 1
        count = [w % 2 for w in count]
        if count == p:
            ans += 1

    print(ans)


if __name__ == '__main__':
    switches()

Submission status: Accepted

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

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

p = list(map(int, input().split()))
ans = 0
state = [i for i in itertools.product((0, 1), repeat=n)]

for case in state:
    flag = True
    for i in range(m):  # 電球iにおいて
        sum = 0
        for j in s[i]:
            sum += case[j-1]
        if sum % 2 != p[i]:
            flag = False
        if not flag:  # 電球消えてたら次のケースに移る
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(pow(2, n)):
    switch = [i>>j&1 for j in range(n)]
    light = 0
    for j in range(m):
        on = 0
        for k in s[j][1:]:
            if switch[k-1]==1:
                on += 1
        if on%2 == p[j]:
            light += 1
    if light == m:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s = [list(map(int, input().split())) for i in range(M)]
p = list(map(int, input().split()))
ans = 0
for i in range(2 ** N):  # all comb
    for j in range(M):  # k loop
        c = 0
        for k in range(N):  # s loop
            if ((i >> k) & 1) and (k + 1) in s[j][1:]:
                c += 1
        if c % 2 != p[j]:
            break
        elif j == M - 1:
            ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for bit in range(2 ** n):
    q = 1
    for i in range(m):
        sum = 0
        for j in range(k[i]):
            if (bit >> (s[i][j] - 1)) & 1:
                sum += 1
        if sum % 2 != p[i]:
            q = 0
    if q == 1:
        ans += 1

print(ans)

Submission status: Accepted

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


ans = 0
for i in range(2**N, 2**(N+1)):
    b = bin(i)
    temp = [0]*M
    for j in range(3, N+3):
        if b[j] == "1":
            for k in range(M):
                switch = L[k][1:]
                if j-2 in switch:
                    temp[k] += 1
    jud = 0
    for j in range(M):
        if temp[j]%2 != P[j]:
            jud = 1
    if jud == 0:
        ans += 1
        
print(ans)

Submission status: Accepted

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

count = 0
for i in range(2 ** N):
    add = True
    for j in range(M):
        k = KS[j]
        cnt = 0
        for s in k[1:]:
            if (1 << (s - 1)) & i > 0 :
                cnt += 1
        if cnt % 2 != P[j]:
            add = False
            break
    if add :
        count += 1
 
print(count)

Submission status: Accepted

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

ans = 0
for bit in range(1<<n):
    q = 1
    for i in range(m):
        sum = 0
        for j in range(k[i]):
            if (bit >> (s[i][j] - 1)) & 1:
                sum += 1
        if sum % 2 != p[i]:
            q = 0
    if q == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [0 for i in range(M)]
for i in range(M):
	k, *s = map(int, input().split())
	for j in range(k):
		a[i] = a[i] | (1 << (s[j] - 1))
p = list(map(int, input().split()))
ans = 0
for bit in range(1 << N):
	ok = True
	for i in range(M):
		x = a[i] & bit
		if bin(x).count("1") % 2 != p[i]:
			ok = False
			break
	if ok:
		ans += 1
print(ans)

Submission status: Accepted

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

suc = 0
for i in range(2**N):
	judge = 1
	s = []
	n = i
	for j in range(N):
		if n >= 2**(N-1-j):
			s.append(1)
			n -= 2**(N-1-j)
		else:
			s.append(0)
	for j in range(M):
		cnt = 0
		for k in range(lst[j][0]):
			if s[N-lst[j][k+1]] == 1:
				cnt += 1
		if cnt%2 != p[j]:
			judge = 0
	if judge == 1:
		suc += 1

print(suc)

Submission status: Accepted

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

import itertools

cnt=0
for i in itertools.product([0,1],repeat=n):
    tn_arr=[]
    for j in range(m):
        on_cnt=0
        for k in range(len(s[j])):
            on_cnt+=i[s[j][k]-1]
        if on_cnt%2==p[j]:
            tn_arr.append(True)
        else:
            tn_arr.append(False)
    if all(tn_arr):
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:

N,M = map(int,input().split())
target = [[num-1 for num in list(map(int,input().split()))[1:]] for _ in range(M)]
#各sについてのリストを元にした配列を、それぞれの値から1を引いて作成
judge = list(map(int,input().split()))
#2で割った余り=最終判定のリスト
cnt = 0

for i in range(2 ** N):
#スイッチの状態について全探索
#N = 2の時、スイッチは[00,01,10,11]の4 = 2^N通り
	switches = [0] * M
	for k in range(M):
	#各電球についてfor文を回す
		for j in range(N):
		#各スイッチについてfor文を回す
			if ((i >> j) & 1) and j in target[k]:
			#jビット右シフト(ex:6 = 0b110 >> 1 → 0b11 = 3)かつ、1と論理積をとる
			#⇨下位1ケタのビットが立っているか = j番目スイッチが押されているかどうかに対応を判定
			#j番目のスイッチが押されており、かつj番目のスイッチが電球Kの点灯条件であれば
			#+1カウント
				switches[k] += 1

	switches =	[switch % 2 for switch in switches]
	#2で割ったあまりを算出し、点灯するかどうかのリストに
	if switches == judge:
		cnt += 1
		
print(cnt)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

N,M = map(int,readline().split())
lines = readlines()
S = [list(map(int,line.split()))[1:] for line in lines[:-1]]
P = list(map(int,lines[-1].split()))

answer = 0
for switch in itertools.product([0,1],repeat=N):
    on = sum(sum(switch[x-1] for x in s) % 2 == p for s,p in zip(S,P))
    if on == M:
        answer += 1
print(answer)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = [list(map(int, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
answer = 0
## k = sorted(k, reverse=True, key=lambda x: len(x))

all = [] # 全てのスイッチの状態
for i in range(0, 2**n):
  all.append(list(str(format(i, 'b').zfill(n))))

for a in all:
  for index in range(len(k)):
    switch_count = 0 
    for switch in k[index]: #1,2
        switch_count+=int(a[switch-1])
    #一つの電球に繋がってる全てのスイッチ確認終了
    if switch_count%2 == p[index]:
      if index == len(k)-1:
      	answer+=1
      continue
    break

print(answer)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = [list(map(int, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
answer = 0
## k = sorted(k, reverse=True, key=lambda x: len(x))

all = [] # 全てのスイッチの状態
for i in range(0, 2**n):
  all.append(list(str(format(i, 'b').zfill(n))))

for a in all:
  for index in range(len(k)):
    switch_count = 0 
    for switch in k[index]: #1,2
      if a[switch-1] == "1":
        switch_count+=1
      else:
        continue
    #一つの電球に繋がってる全てのスイッチ確認終了
    if switch_count%2 == p[index]:
      if index == len(k)-1:
      	answer+=1
      continue
    break

print(answer)

Submission status: Accepted

Solution code:
"""
n,m<=10
"""

n,m = map(int, input().split( ))
s = []

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

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

ans = 0

for i in range(2**n):
    flag = True
    for k in range(m):
        tst = 0
        for sm in s[k]:
            tst ^= i>>(sm-1)&1
        if tst^p[k]:###
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

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

for i in range(2**n):
    addable = True
    for j in range(m):
        d = sum(2 ** (k - 1) for k in s[j])
        if bin(i & d).count('1') % 2 != p[j]:
            addable = False
            break
    if addable:
        c += 1
print(c)

Submission status: Accepted

Solution code:
from sys import stdin


def f(s, p, P, i):
    # 再帰
    # 順にスイッチを見ていく
    if len(s) == i:
        return 1 if P == p else 0
    # 場合の数
    # そのスイッチを使用しなかった場合 + 使用した場合
    return f(s, p, P, i + 1) + f(s, p, P ^ s[i], i + 1)


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    sn = [[int(j) for j in i.split()[1:]] for i in lines[1:-1]]
    pn = (int(i) for i in lines[-1].split())
    # s[スイッチID]
    # 二進法で表した数における各桁はそのスイッチを使用している電球
    s = [0] * N
    for i in range(M):
        for j in sn[i]:
            s[j - 1] |= (1 << i)
    # p
    # 二進法で表した数における各桁は電球
    # MOD 2 におけるゼロイチをそのまま2進数とする
    p = 0
    for i, j in enumerate(pn):
        p |= (1 << i) if j == 1 else 0
    print(f(s, p, 0, 0))


main()

Submission status: Accepted

Solution code:
from sys import stdin

lines = stdin.readlines()
N, M = map(int, lines[0].split())
sn = [[int(j) for j in i.split()[1:]] for i in lines[1:-1]]
pn = (int(i) for i in lines[-1].split())
# s[スイッチID]
# 2進数における桁はそのスイッチを使用している電球
s = [0] * N
for i in range(M):
    for j in sn[i]:
        s[j - 1] |= (1 << i)
# p
# 2進数における桁は電球 ゼロイチをそのまま2進数とする
p = 0
for i, j in enumerate(pn):
    p |= (1 << i) if j == 1 else 0


def f(P, i):
    # 再帰
    # 順にスイッチを見ていく
    if len(s) == i:
        return 1 if P == p else 0
    # 場合の数
    # そのスイッチを使用しなかった場合 + 使用した場合
    return f(P, i + 1) + f(P ^ s[i], i + 1)


def main():
    print(f(0, 0))


main()

Submission status: Accepted

Solution code:
from sys import stdin


def f(s, p, P, i):
    # 再帰
    # 順にスイッチを見ていく
    if len(s) == i:
        return 1 if P == p else 0
    # 場合の数
    # そのスイッチを使用しなかった場合 + 使用した場合
    return f(s, p, P, i + 1) + f(s, p, P ^ s[i], i + 1)


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    sn = [[int(j) for j in i.split()[1:]] for i in lines[1:-1]]
    pn = (int(i) for i in lines[-1].split())
    # s[スイッチID]
    # 2進数における桁はそのスイッチを使用している電球
    s = [0] * N
    for i in range(M):
        for j in sn[i]:
            s[j - 1] |= (1 << i)
    # p
    # 2進数における桁は電球 ゼロイチをそのまま2進数とする
    p = 0
    for i, j in enumerate(pn):
        p |= (1 << i) if j == 1 else 0
    print(f(s, p, 0, 0))


main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
bits = '0b' + '1' * n
s = []

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

p = [int(i) for i in input().split()]
c = 0
for i in range(2**n):
    l = bin(i)[2:]
    b = (n - len(l)) * '0' + l
    addable = True
    for h, j in enumerate(s):
        d = 0
        for k in j:
            d += int(b[k - 1])
        if addable:
            addable = d % 2 == p[h]
    if addable:
        c += 1
print(c)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import combinations_with_replacement,product

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
p = list(map(int,stdin.readline().rstrip().split()))

hai = [0,1]
hai = list(product(hai, repeat=n))

point = 0

for i in range(len(hai)):
    h = list(hai[i])
    kai = 0
    for j in range(m):
        gou = 0
        for k in range(1,len(li[j])):
            if h[li[j][k]-1] == 1:
                gou += 1
        if p[j] != gou%2:
            kai += 1
    if kai == 0:
        point += 1
print(point)

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    print(sum(1
              for i in range(1 << N)
              if sum(1
                     for s, p in zip(
                         (sum(1 << int(j) - 1
                              for j in i.split()[1:])
                          for i in lines[1:-1]),
                         (int(i)
                          for i in lines[-1].split()))
                     if bin(i & s).count("1") % 2 == p) == M))
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    print(sum(1
              for i in range(1 << N)
              if sum(1
                     for s, p in zip(
                         (sum(1 << int(j) - 1
                              for j in i.split()[1:])
                          for i in lines[1:-1]),
                         (int(i) for i in lines[-1].split()))
                     if bin(i & s).count("1") % 2 == p) == M))
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    print(sum([1
               for i in range(1 << N)
               if sum([1
                       for s, p in zip(
                           [sum(1 << int(j) - 1
                                for j in i.split()[1:])
                            for i in lines[1:-1]], lines[-1].split())
                       if bin(i & s).count("1") % 2 == int(p)]) == M]))
    return


main()

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()))
a=2**n
on=0
cnt=0
light=True
s = [bin(i)[2:] for i in range(a)]
for i in range(a):
    s[i]='0'*(n-len(s[i]))+s[i]
    s[i]=s[i][::-1]
for i in range(a):
    for j in range(m):
        for l in range(1,k[j][0]+1):
            #print(s[i][k[j][l]-1], i,j,l)
            if s[i][k[j][l]-1]=='1':
                on+=1
        if on%2!=p[j]:
            light=False
        #print(i,light,j,on)
        on=0
    if light:
        cnt+=1
    light=True
print(cnt)

Submission status: Accepted

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**n):
    tmp=array([t>>s&1 for s in range(n)])
    if p==[sum(tmp[array(i)-1])%2for i in l]:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    X = [sum(1 << int(j) - 1 for j in i.split()[1:]) for i in lines[1:-1]]
    Z = lines[-1].split()
    print(sum([1 for i in range(1 << N) if sum([1 for x, y in zip(X, Z) if bin(i & x).count("1") % 2 == int(y)]) == M]))
    return


main()

Submission status: Accepted

Solution code:
from sys import stdin


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    X = [sum(1 << int(j) - 1 for j in i.split()[1:]) for i in lines[1:-1]]
    Z = lines[-1].split()
    ans = 0
    for i in range(1 << N):
        tmp = 0
        for x, y in zip(X, Z):
            if bin(i & x).count("1") % 2 == int(y):
                tmp += 1
        if tmp == M:
            ans += 1
    print(ans)

    return


main()

Submission status: Accepted

Solution code:
from __future__ import print_function
# import numpy as np
# import numpypy as np
import sys
input = sys.stdin.readline

def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

import math
import string
import fractions
from fractions import Fraction
from fractions import gcd

def lcm(n,m):
    return int(n*m/gcd(n,m))

import re
import array
import copy
import functools
import operator

import collections
import itertools
import bisect
import heapq


from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace

from queue import PriorityQueue as pq

def reduce(p, q):
    common = fractions.gcd(p, q)
    return (p//common , q//common )
# from itertools import accumulate
# from collections import deque

import random


def main():
    # n,m の先行受け取り
    n,m = map(int, input().split())
    # コンテナの準備
    k=[0 for i in range(m)]     # それぞれの電球(light)に繋がれたスイッチ(swuitch)の個数を表す
    # s=[0 for i in range(n)]     # それぞれの電球(light)に繋がれている「スイッチ(switch)」を表す
    
    S=[ [] for i in range(m)]
    # for i in range(m):
    #     S[i]=[ 0 for i in range( k[i] ) ]

    # 入力
    for i in range(m):
        l = list(map(int, input().split()))
        k[i] = l[0]
        ll=l[1:]
        for j in range(len(ll)):
            ll[j]=ll[j]-1
        S[i] = ll
    p = list(map(int, input().split()))

    # 出力
    eprint()
    # print(n,m)
    eprint("num of Switch : " + str(n) + "    num of Light : " + str(m))
    for i in range(m):
        # print(k[i],S[i])
        eprint("k[%d]: %d      S[%d]: " % (i,k[i],i ) + str(S[i]) )
    eprint("p: "+ str(p))

    # 処理
    cnt_state_whereLightIsTurnedOn=0
    
    for state in range(2**n):   # stateは状態(ステート)を表す整数
        failure_flag=0
        for index in range(m):  # indexは電灯の番号を表すインデックス
            cnt=0
            for i in range(k[index]): # i is the "uniform_number" of Switches
                if (state>>S[index][i] & 1)==1 :
                    cnt+=1
                    
            if cnt%2==p[index]:
                # failure_flag=0
                # cnt_state_whereLightIsTurnedOn+=1
                continue
            else:
                failure_flag=1
                break
                # eprint(cnt_state_whereLightIsTurnedOn)
        if failure_flag==0:
            cnt_state_whereLightIsTurnedOn+=1
        else:
            continue
        
    print(cnt_state_whereLightIsTurnedOn)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[list(map(int,input().split()))for i in range(m)]
for i in range(m):
    del s[i][0]
p=list(map(int, input().split()))
q=[0]*11


ans=0
while(True):
    for i in range(n):
        if(q[i]==2):
            q[i+1]+=1
            q[i]=0
    if(q[n]==1):
        break
    
    flag=1
    for i in range(m):
        tmp=0
        for j in s[i]:
            tmp+=q[j-1]
        if(tmp%2!=p[i]):
            flag=0
            break
    if(flag==1):
        ans+=1
    q[0]+=1

print(ans)

Submission status: Accepted

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

ans=0
for i in range(2**n):
    for j in range(m):
        k=ks[j][0]
        s=ks[j][1:]
        pid=p[j]
        check=0

        for x in s:
            if i >>(x-1) &1:
                check+=1
        if pid == check%2:
            continue
        else:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(200000)


def a(l2,x):
    l3=l2[:]
    if x==n+1:
        for j in l2:
            if j%2==1:
                return 0
        return 1
    for i in sw_l[x]:
        l3[i-1]+=1
    return a(l2,x+1)+a(l3,x+1)







n,m=map(int,input().split())
sw_l=[[] for _ in range(n+1)]
for i in range(1,m+1):
    l=list(map(int,input().split()))
    for j in l[1:]:
        sw_l[j].append(i)
p=list(map(int,input().split()))
ans=a(p,1)
print(ans)

Submission status: Accepted

Solution code:
# スイッチN個, 電球M個

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

ans = 0

for mask in range(1<<N):
    flag = True
    for i in range(M):
        cnt = 0
        for j in S[i]:
            if (mask >> (j-1)) & 1:
                cnt += 1
        flag &= (cnt % 2) == P[i]
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = []
s = [[] for _ in range(m)]
for i in range(m):
    line = list(map(int, input().split()))
    k.append(line[0])
    for j in range(len(line)-1):
        s[i].append(line[j+1])
p = list(map(int, input().split()))

def make(n):
    lists = []
    for i in range(2**n):
        str = format(i,"10b")
        bitlist = list(reversed(str.replace(" ", "0")))
        lists.append(bitlist)
    return lists
count = 0

for switch in make(n):
    flag = 0
    for i in range(m):
        sum = 0
        for j in range(k[i]):
            sum += int(switch[s[i][j]-1])
        if sum % 2 != p[i]:
            flag = 1
    if flag == 0:
        count += 1
print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(m)]
*p,=map(int,input().split())
a=0
for i in range(2**n):
    a+=all(sum((i>>(k-1))&1 for k in s[j][1:])%2==p[j] for j in range(m))
print(a)