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())
ks=[list(map(int,input().split())) for i in range(M)]
p=list(map(int,input().split()))

allbit = []
for i in range(2**N):
  bit = [0] * N
  for j in range(N):
    if (i >> j) & 1:
      bit[j] = 1
  allbit.append(bit)


j=0
for onof in allbit:
    l=0
    for m in range(M):
        s=ks[m][1:]
        i=0
        for st in s:
            i+=onof[st-1]
        if(i%2==p[m]):
            l+=1
    if(l==M):
        j+=1
        
print(j)

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()))
num = 0
for i in range(2**n):
    onof = format(i,'b').zfill(n)
    for j in range(m):
        sum_onof = 0
        for k in range(s[j][0]):
            sum_onof += int(onof[s[j][k+1]-1])
        if sum_onof%2 != p[j]:
            break
        elif j == m-1:
            num += 1
print(num)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    f = True
    for s, p in zip(S, P):
        c = 0
        for k in s:
            if i & 1 << k == 1 << k:
                c += 1
        if(c % 2 != p):
            f = False
            break
    if f:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def solve(n, m, k, s, p):
    switch_sockes_mapping = {i: [] for i in range(n)}
    for i in range(m):
        for switch in s[i]:
            switch -= 1
            switch_sockes_mapping[switch].append(i)

    res = 0
    for mask in range(2**n):
        nums = [0] * m # スイッチの押された回数
        for i in range(n):
            if (2**i) & mask:
                for j in switch_sockes_mapping[i]:
                    nums[j] += 1
        cnt = 0
        for j in range(m):
            if nums[j] % 2 == p[j]:
                cnt += 1
        if cnt == m:
            res += 1
    return res

n, m = map(int, input().split())
k = [0] * m
s = []
for i in range(m):
    v = list(map(int, input().split()))
    k[i] = v[0]
    s.append(v[1:])
p = list(map(int, input().split()))
print(solve(n, m, k, s, p))

Submission status: Accepted

Solution code:
import numpy as np
n,m = map(int, input().split())
sl= [[0]]*m
for i in range(m):
    k,*s = map(int,input().split())
    sl[i] =list(map(lambda x: 10-x+1 , s))
pl = list(map(int,input().split()))

cnt = 0

for j in range(2**n):
    switch = np.array(list(map(int,list(format(j, '011b')))))
    re = [sum(switch[sl[i]])%2 for i in range(m)]
    if pl == re:
        cnt +=1

print(cnt)

Submission status: Accepted

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

all_bit = []
for i in range(2**N):
  bit_li = [0] * N
  for j in range(N):
    if (i >> j) & 1:
      bit_li[j] = 1
  all_bit.append(bit_li)

count = 0
for i in all_bit:
  light_li = [0] * M
  for j in range(len(switch_li)):
    for k in range(N):
      if i[k] == 1:
        if k+1 in switch_li[j][1:]:
          light_li[j] += 1
  m_count = 0        
  for a,b in zip(light_li, p_li):
    if a % 2 == b % 2:
      m_count += 1
    if m_count == M:
      count += 1
      
print(count)

Submission status: Accepted

Solution code:
def counter(n):
	temp = n
	c = 0
	while temp != 0:
		c += temp & 1
		temp = temp >> 1
	return c % 2

def main():
	n,m = map(int,input().split())
	light = []
	for i in range(m):
		line = list(map(int, input().split()))
		temp = 0
		for j in line[1:]:
			temp += 2 ** (j-1)
		light += [temp]
	lst = list(map(int,input().split()))
	ans = 0
	for i in range(2**(n)):
		flg = True
		for j in range(m):
			if lst[j] != counter(light[j] & i):
				flg = False
				break
		if flg:
			ans += 1
	print(ans)

main()

Submission status: Accepted

Solution code:
N, M = [int(s) for s in input().split()]
S = []
for _ in range(M):
    l = [int(s) for s in input().split()]
    S.append(l[1:])
P = [int(s) for s in input().split()]

result = 0
for i in range(2 ** N):
    if all(sum(["{:0{N}b}".format(i, N=N)[t - 1] == '1' for t in s]) % 2 == P[j] for j, s in enumerate(S)):
        result += 1

print(result)

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
sw = [[] for _ in range(M)]
for i in range(M):
  sw[i] = list(map(int, input().split()[1:]))
p = list(map(int, input().split()))

ans = 0
for tpl in itertools.product([0,1],repeat=N):
  bl = True
  for i in range(M):
    s = sum([tpl[s-1] for s in sw[i]])
    if (s-p[i])%2 != 0:
      bl = False
      break
  if bl:
    ans += 1
print(ans)

Submission status: Accepted

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

k = [0] * M
s = [0] * M


for m in range(M):
    line = list(map(int, input().split()))
    k[m] = line[0]
    
    s[m] = [line[l] - 1 for l in range(1, k[m] + 1)]

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

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

Submission status: Accepted

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

k = []
s = []
p = []

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

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

on_pattern_cnt = 0

for s_pattern_int in range(2**n):
	s_pattern_binstr = str(bin(s_pattern_int)) # 2進数文字列化
	s_pattern_binstr = s_pattern_binstr[2:] # 0bの削除
	s_pattern_binstr = s_pattern_binstr.zfill(n)				# 上位を0で埋める
	s_pattern_binstr = s_pattern_binstr[::-1] # 反転

	s_pattern = []
	for c in s_pattern_binstr:
		s_pattern.append(int(c))

	flag = True
	for i in range(m): # 電球に関するループ
		on_cnt = 0
		for j in range(k[i]): # スイッチに関するループ
			if s_pattern[s[i][j]] == 1:
				on_cnt += 1

		if p[i] != on_cnt % 2:
			flag = False
			break

	if flag:
		on_pattern_cnt += 1


print(on_pattern_cnt)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
ks=[[int(i) for i in input().split()]for i in range(m)]
p=[int(i) for i in input().split()]
swi=list(itertools.product([0,1], repeat=n))
cnt=0

for SWI in range(len(swi)):
    DK=[0 for i in range(m)]
    for onoff in range(len(swi[SWI])):
        if swi[SWI][onoff]==1:
            for i in range(m):
                for kkk in ks[i][1:]:
                    if kkk-1==onoff:
                        DK[i]+=1
                DK[i]%=2
    if DK==p:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np


N, M = map(int, input().split())
s_mat = np.zeros((M, N), dtype=int)
si_list = []
for i in range(M):
    si = list(map(int, input().split()))[1:]
    for s in si:
        s_mat[i, s-1] = 1
p_list = np.array(list(map(int, input().split())))


prob = 0
for i in range(2**N):
    i_list = []
    for k in range(N-1, -1, -1):
        if i >= 2**k:
            amari = 1
            i -= 2**k
        else:
            amari = 0
        i_list.append(amari)
        
    i_array = s_mat.dot(np.array(i_list)) % 2
    if np.all(i_array == p_list):
        prob += 1

print(prob)

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

pattern_count = 0
for n in range(2 ** N):
	for i, ks in enumerate(KS):
		switch_count = 0
		for s in ks[1:]:
			if n >> (s - 1) & 1:
				switch_count += 1
		else:
			if switch_count % 2 != P[i]:
				break
	else:
		pattern_count += 1
print(pattern_count)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

N, M = map(int, input().split())
S = np.zeros((M, N))  # (M, N), switch

for i in range(M):
    k, *s = map(int, input().split())
    s = [x - 1 for x in s]
    S[i, s] = 1
p = np.array(list(map(int, input().split())), dtype=np.int)

cnt = 0
for i in product([0, 1], repeat=N):
    a = np.array(i, dtype=np.int)  # N,
    b = (np.dot(S, a) % 2).astype(np.int)
    if np.all(b == p):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def count_bit(x):
    res = 0
    while x > 0:
        res += x % 2
        x //= 2
    return res


n, m = map(int, input().split())
k = [0] * m
for i in range(m):
    x = list(map(int, input().split()))
    k[i] = sum(map(lambda l: 2**(l-1), x[1:]))
p = list(map(int, input().split()))

res = 0
for b in range(2**n):
    for i in range(m):
        x = b & k[i]
        if count_bit(x) % 2 != p[i]:
            break
    else:
        res += 1
print(res)

Submission status: Accepted

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

# kの値は特に必要ないので最初から取得しない
# S = [[1, 2], [2]]
# p = [0, 1]
S = [list(map(int,input().split()))[1:] for i in range(M)]
p = list(map(int, input().split()))

ans = 0

for i in range(1<<N): #スイッチのオンオフ状態(0, 1, 2, 3)
    count_2 = -1
    bit = list(str(bin(i))) # 0b0, 0b1, 0b10...
    fail = 0
    
    # 桁埋め処理
    ketaume = (1<<N) // 2 + 2 - len(bit) 
    if ketaume > 0:
        for i in range(ketaume):
            bit.insert(2, "0")
    # print("search target={}".format(bit))
    for s in S: #[1, 2], [2]の階層
        count_2 += 1 # 何番目のSかを数えたい
        count = 0
        for t in s: # 1, 2の階層
            # print("bit = {}".format(bit[-t]))
            if int(bit[-t]) == 1:
                count += 1 # ついているスイッチの数を数える
                
        # print("{}-> number of switch is {}".format(s, count))
                
        # ついているスイッチが偶数か奇数かを判定
        # print("if mod is {}, OK".format(p[count_2]))
        # print("")
        if not count % 2 == p[count_2]:
            fail = 1 # 望ましくなければ，失敗フラグを立ててブレイク
            break
    if fail == 0:
        # print("ans += 1")
        ans += 1
        
print(ans)

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(ks[1:])
p = list(map(int, input().split()))

ans = 0
for bits in range(2**n):
    flag = True
    for i in range(m):
        on_sum = 0
        for switch in s[i]:
            on_sum += ((bits >> (switch - 1)) & 1)
        flag = flag and ((on_sum % 2) == p[i])
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=[int(i) for i in input().split()]
joints=[]
patterns=[]
for i in range(M):
	a=[int(j) for j in input().split()]
	joints.append(a[1:])
ans=input().split()
def f(x,i):
	if i==N:
		patterns.append(x)
		return
	f(x+"0",i+1)
	f(x+"1",i+1)
f("",0)
res=0
for pattern in patterns:
	for i in range(len(joints)):#joinは一つの電球につながっているスイッチの一覧
		on=0
		for j in joints[i]:#jはつながっているスイッチの番号
			if pattern[j-1]=="1":
				on+=1
		if on%2==int(ans[i]):
			if i==len(joints)-1:
				res+=1
			else:
				continue
		else:
			break
	

print(res)

Submission status: Accepted

Solution code:
from sys import exit
from itertools import product

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

light = {}

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

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

count = 0
for i in product([1, 0], repeat=N):
    clear = True
    for j in range(M):
        s = 0
        for k in light[j]:
            if i[k - 1] == 1:
                s += 1

        if s % 2 != p[j]:
            clear = False
            break
    if clear:
        count += 1

print(count)

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()))
res = 0
for i in range(2**N):
    ON = 0
    for j in range(M):
        cnt = 0
        for s in S[j]:
            if (i >> s-1)&1 == 1:
                cnt += 1
        if cnt%2 == P[j]:
            ON += 1
    if ON == M:
        res += 1 
print(res)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ks = [[0] for i in range(m)]
jud = []
for i in range(m):
    tmp = list([int(i)-1 for i in input().split()])
    ks[i] = tmp[1:]
jud = list(map(int, input().split()))

ans = 0
c = True
for i in range(2 ** n):
    c = True
    ib = format(i, 'b')
    for iks, j in enumerate(ks):
        ch = 0
        for m in j:
            if len(ib) >= m+1:
                ch += int(ib[-m-1])
        if ch % 2 != jud[iks]:
            c = False
            break
    if c:
        ans += 1
print(ans)

Submission status: Accepted

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

lamp=[]
switches=[]
temp=[]

for i in range(m):
    temp=list(map(int,input().split()))
    lamp.append(temp.pop(0))
    switches.append(temp)
    temp=[]

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

bit_list=[]

for i in range(2**(n)):
    bit_list.append(bin(i)[2:].zfill(n))

ans = 0

for b in bit_list:
    flag = 0
    for s,p in zip(switches,modul):
        sum = 0
        for k in range(len(s)):
            sum=sum+int(b[s[k]-1])
        if sum%2 != p:
            flag = 1
            break
    if flag == 0:
        ans=ans+1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Mon Jun 10 22:22:57 2019

@author: YudNK
"""

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

def binaly(n):
    d = n
    binaly = [0 for i in range(N)]
    m = 0
    while d >= 1:
        binaly[m] = d % 2
        d = d // 2
        m += 1
    return binaly

pattern = 0
for i in range(2**N):
    sample = binaly(i)
    count = 0
    for j in range(M):
        sum = 0
        for k in range(list[j][0]):
            sum += sample[list[j][k + 1] - 1]
        if sum%2 == p[j]:
            count += 1
    if count == M:
        pattern += 1
print(pattern)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
s_list = [list(map(int, input().split())) for _ in range(m)]
p_list = list(map(int, input().split()))
patterns = []
for i in range(2**n):
    patterns.append(bin(i)[2:].zfill(n))
cnt = 0
for pattern in patterns:
    flag = 1
    for s, p in zip(s_list, p_list):
        if sum([int(pattern[i-1]) for i in s[1:]]) % 2 != p:
            flag = 0
            break
    if flag == 1:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=[]
sw=[0]*N

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

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


for k in range(2**N):
    flag=0
    b=bin(k)
    bi1=str(b[2:].zfill(N))
    bi=[int(_) for _ in bi1]
    for i in range(M):
        sm=0
        for j in range(len(S[i])):
            sm+=bi[S[i][j]-1]
        if sm%2!=p[i]:
            flag=1
            break
    if flag==0:
        count+=1


print(count)

Submission status: Accepted

Solution code:
def bitcount(bit):
    return bin(bit).count("1")

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

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

for i in s:
    mask = 0
    for j in i[1:]:
        mask |= 1<<(j-1)        
    kmask.append(mask)

result = 0
for i in range(1<<n):
    ok = True
    for mask,odd in zip(kmask,p):
        bc = bitcount(i&mask)
        if((bc&1)!=odd):
            ok = False
            break
    if ok:
        result += 1

print(result)

Submission status: Accepted

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

# kの値は特に必要ないので最初から取得しない
S=[list(map(int,input().split()))[1:] for i in range(M)]
p = list(map(int,input().split()))
ans = 0
for i in range(1<<N): #スイッチのオンオフ状態
    
    for m in range(M):  #電球の状態 
        count = 0
        for s in S[m]:
            if i & (1<<(s-1)) != 0:
                count += 1
                # 電球に対するスイッチのonの数を取得する
        if count%2 != p[m]:
            break
    else:
        # あるスイッチのパターンに対して各電球がOKだったらカウントする
        ans +=1
print(ans)

Submission status: Accepted

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

## INPUT ###
N, M = map(int, input().split())
tmp = []
k_i = []
p = []

for i in range(M):
    tmp = map(int, input().split())
    k_i.append(list(tmp))
p = list(map(int, input().split()))

det=[]
success = 0

for i in range(2**N):
    sw_status = format(i,'b').zfill(N)
    sw_status = list(map(int, sw_status))
    det=[]
    for k in range(M):
        det_j =0
        for j in range(k_i[k][0]):
            det_j += sw_status[k_i[k][j+1]-1]
        if p[k] == det_j % 2:
            det.append(1)
        else:
            det.append(0)
    if sum(det) == M:
        success += 1
print(success)

Submission status: Accepted

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

for i in range(2**n):
    bulb = [0] * m
    for j in range(n):
        if i>>j & 1:
            for k in range(m):
                if j+1 in lst[k][1:]:
                    bulb[k] += 1

    all_lightup = True
    for l in range(m):
        if bulb[l] % 2 != p[l]:
          all_lightup = False
          break
    if all_lightup:
        ans += 1

print (ans)

Submission status: Accepted

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

for i in range(2**n):
    bulb = [0] * m
    for j in range(n):
        if i>>j & 1:
            for k in range(m):
                if j+1 in lst[k][1:]:
                    bulb[k] += 1

    flag = True
    for l in range(m):
        if bulb[l] % 2 != p[l]:
            flag = False
    if flag:
        ans += 1

print (ans)

Submission status: Accepted

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

sw2lmp = [[] for _ in range(N)]
for i in range(M):
    k, *s = map(int, input().split())
    s = tuple(map(lambda x: x - 1, s))
    for ss in s:
        sw2lmp[ss].append(i)
p = tuple(map(int, input().split()))

cnt = 0
for i in range(1 << N):
    state = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            for lmp in sw2lmp[j]:
                state[lmp] += 1
    if all(x % 2 == p[i] for i, x in enumerate(state)):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import itertools

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 p in itertools.product([True, False], repeat=N):
    for i in range(M):
        ok = True if P[i] == 0 else False
        for s in S[i]:
            ok ^= p[s - 1]
        if not ok:
            break
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

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

b=[]
for k in range(2**n):
  b.append(format(k,'0'+str(n)+'b'))

ans=0
for i in range(2**n):
  cton=0
  for j in range(m):
    ct=0
    for k in range(1,l[j][0]+1):
      if b[i][l[j][k]-1]=='1':ct+=1
    if ct%2==p[j]:cton+=1
  if cton==m:ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = []
k = []
p = []
count = 0
for i in range(m):
    q = input().split()
    k.append(int(q[0]))
    q.remove(q[0])
    s.append(q)
    #print(q)
    for j in range(k[i]):
        s[i][j] = int(q[j])
        #print(s)
    
q = input().split()
for j in range(m):
        p.append(int(q[j]))
        #count.append([0])
#入力終了

       
for i in range(pow(2,n)):
    list = []
    for o in range(n):
        list.append(i%2)
        i = i // 2
    #print(list)
    q = 0
    for j in range(m):
        wa = 0
        for l in range(k[j]):
            wa += list[s[j][l]-1]
        #print(wa)
        if wa%2 == p[j]:
            q += 1
            #print(q)
        else:
            break
    if q == m:
        count += 1

#kotae = count[0]
#for i in range(1,m):
    #kotae *= count[i]

#print(kotae)
print(count)

Submission status: Accepted

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

count = 0
#bit全探索
for i in range(2**N): #スイッチの状態をbit-全探索
    c = [0] * M
    for j in range(N): #j桁目を確認
        if (i >> j) & 1: #j桁目 = j個目のスイッチがONの時
            for k in range(M): #M個の電球に対して確認
                if j+1 in lst[k][1:]:
                    c[k] += 1
    flag = True
    for l in range(M):
        if c[l]%2 != p[l]:
            flag = False
    if flag:
        count += 1


print (count)

Submission status: Accepted

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

count = 0

for i in range(2**n):
    switches =str(format(i, 'b').zfill(n))
    lights = ""
    for light in range(m):
        s_on = 0
        for connect in s[light]:
            if switches[connect-1] == "1":
                s_on += 1
        if s_on % 2 == p[light]:
            lights += "1"
    if lights == "1" * m:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys
import itertools

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

ans = 0

for state in itertools.product([0, 1], repeat=N):
    is_ans = True
    for bulb, p in zip(S, P):
        connected = 0
        for idx in bulb:
            if state[idx - 1] == 1:
                connected = connected + 1
        if connected % 2 != p:
            is_ans = False
            break
    if is_ans:
        ans = ans + 1

print(ans)

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()))
res = 0
for i in range(2**N):
    tmp = 0
    for j in range(M):
        ON = 0
        for s in S[j]:
            if (i >> s-1)&1 == 1:
                ON += 1
        if ON % 2 == P[j]:
            tmp += 1
    if tmp == M:
        res += 1
print(res)

Submission status: Accepted

Solution code:
import copy

L=[]

def check(M,p,tmp):
  n_ok=0
  for i in range(len(L)):
    sum=0
    for l in L[i]:
      sum+= 1 if tmp[l-1]==1 else 0
    if sum%2==p[i]:
      n_ok+=1
      
  if n_ok==M:
    return 1
  else:
    return 0

def rc(N,M,p,i,tmp):
  if i==N-1:
    return check(M,p,tmp)
  else:
    t1=copy.copy(tmp)
    t2=copy.copy(tmp)
    t1.append(0)
    t2.append(1)
    return rc(N,M,p,i+1,t1)+rc(N,M,p,i+1,t2)

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

print(rc(N,M,p,-1,[]))

Submission status: Accepted

Solution code:
from itertools import combinations

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

A = {i: [] for i in range(N)}

for i in range(M):
  line = [int(i) for i in input().strip().split(' ')]
  for s in line[1:]:
    A[s - 1].append(i)

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

cmb = []
for i in range(N + 1):
  cmb.extend(list(combinations(range(N), i)))

counter = 0
for c in cmb:
  # print(c)
  tmp = [0] * M
  for i in c:
    for j in A[i]:
      tmp[j] = (tmp[j] + 1) % 2
  if tmp == P:
    counter += 1

print(counter)

Submission status: Accepted

Solution code:
import sys
N, M = map(int, input().split())
k_list_list = []
for m in range(M):
    k_list_list.append(list(map(int, input().split()[1:])))
p_list = list(map(int, input().split()))
    
def add_num(on_off_list_list):
    new_list = []
    for on_off_list in on_off_list_list:
        for i in [[0], [1]]:
            new_list.append(on_off_list+i)
    return new_list

def create_on_off_list(N):
    on_off_list_list = [[]]
    for n in range(N):
        on_off_list_list = add_num(on_off_list_list)
    return on_off_list_list

def check(k_list, p, on_off_list):
    total = 0
    for k in k_list:
        k -= 1
        swich = on_off_list[k]
        if swich == 1:
            total += 1
    if total%2 == p:
        return True
    else:
        return False

def main():
    on_off_list_list = create_on_off_list(N)
    ans = 0
    for on_off_list in on_off_list_list:
        for k_list, p in zip(k_list_list, p_list):
            if check(k_list, p, on_off_list): continue
            else: break
        else:
            ans += 1
    print(ans)
    
main()

Submission status: Accepted

Solution code:
from itertools import product

#n進m桁のbit列の作成
def bit(n,m):
    bi = list((product([i for i in range(n)],repeat = m)))
    return bi

if __name__ == "__main__":
    N, M = map(int, input().split(" "))
    S = [list(map(int, input().split()))[1:] for i in range(M)]
    P = list(map(int, input().split()))

    ans = 0
    petterns = bit(2,N)
    for pettern in petterns:
        for m in range(M):
            cnt = 0
            for s in S[m]:
                # 探索中の君合わせpetternの内、電球mのスイッチsが含まれてたらカウント
                if pettern[s-1] == 1:
                    cnt += 1
            if cnt %2 != P[m]:
                break
        else:
            ans += 1
    print(ans)

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:
import collections
N,M=map(int,input().split())

ki=[]
k_sw=[] #Li -> s1 ~ ski
for i in range(M):
    terms = input().split()
    ki.append(int(terms[0]))
    k_sw.append([])
    for j in range(1,len(terms)):
        k_sw[i].append(int(terms[j]))
P=list(map(int,input().split()))

def is_all_on(swb):
    all_on = True
    for i in range(M):
        #for Light
        sws = k_sw[i]
        total = 0
        for s in sws:
            total += swb[s-1]
        if total % 2 != P[i]:
            all_on = False
            break
    return all_on

on_num = 0
for swp in range(0,2**N):
    binary_pattern = format(swp,'0'+str(N)+'b')
    blist = []
    for b in binary_pattern:
        blist.append(int(b))
    if is_all_on(blist):
        on_num += 1
print(on_num)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
L = []
for i in range(M):
  L.append(list(map(int,input().split())))
P = list(map(int,input().split()))
def Base_10_to_n(X,n):
  if (int(X/n)):
    return Base_10_to_n(int(X/n),n)+str(X%n)
  return str(X%n)
n = 2
ans = 0
for X in range(n**N):
  STR = Base_10_to_n(X,n).zfill(N)
  flag = True
  for i in range(len(L)):
    t = 0
    for j in range(1,L[i][0]+1):
      t += int(STR[L[i][j]-1])
    if t%2 != P[i]:
      flag = False
      break
  if flag:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from numpy import *

n, m = map(int, input().split())
s = [[int(x) for x in input().split()][1:] for y in range(m)]
p = [int(z) for z in input().split()]
ans = 0

for i in range(2**n):
    b = array([(i>>j)&1 for j in range(n)])
    if [sum(b[array(k) - 1]) % 2 for k in s] == p:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())  # N個のスイッチ, M個の電球

# M個の電球がそれぞれどこのスイッチと繋がっているかを格納
SSS = [list(map(int, input().split()))[1:] for i in range(M)]
P = list(map(int, input().split()))

ans = 0

for i in range(1 << N):  # 2のN乗の値になる, bit全探索
    for mask in range(M):
        ans_2 = 0
        for s in SSS[mask]:
            if (1 << s-1) & i != 0:
                ans_2 += 1

        if ans_2 % 2 != P[mask]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from numpy import *
n,m = map(int, input().split())

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

ans = 0

for i in range(2**n):
    b = array([(i>>j)&1 for j in range(n)])
    if [sum(b[array(k)-1]) % 2 for k in s] == p:
        ans += 1
print(ans)

Submission status: Accepted

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

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

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

count=0
flag=True
for i in range(1<<n):
    flag=True
    for j in range(m):
        count2=0
        for l in k[j]:
            if i & (1<<(l-1)):
                count2+=1
        if not count2%2==p[j]:
            flag=False
    if flag:
        count+=1

print(count)

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()))
ans = 0

for i in range(1<<N): #スイッチのオンオフ状態
    
    for m in range(M):  #電球の状態 
        count = 0
        for s in S[m]:
            if i & (1<<(s-1)) != 0:
                count += 1
        if count%2 != p[m]:
            break
    else:
        ans +=1
print(ans)