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

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

ans = 0
for i in range(1 << N):
    all_lit = True
    for j in range(M):
        n = 0
        for k in s[j]:
            n += bool(i & (1 << k))
        if n % 2 != p[j]:
            all_lit = False
            break
    ans += all_lit

print(ans)

Submission status: Accepted

Solution code:
def LI(): return list(map(int,input().split()))
N,M = LI()
ks = [LI() for _ in range(M)]
p = LI()
ans = 0
for i in range(2**N):
    bit = [i>>j & 1 for j in range(N)]
    for j,x in enumerate(ks):
        if p[j]!=sum([bit[y-1] for y in x[1:]])%2:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def LI(): return list(map(int,input().split()))
N,M = LI()
ks = [LI() for _ in range(M)]
p = LI()
ans = 0
for i in range(2**N):
    bit = [i>>j & 1 for j in range(N)]
    for j,x in enumerate(ks):
        k,*s = x
        if p[j]!=sum([bit[y-1] for y in s])%2:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def LI(): return list(map(int,input().split()))
N,M = LI()
ks = [LI() for _ in range(M)]
p = LI()
ans = 0
for i in range(2**N):
    bit = [i>>j & 1 for j in range(N)]
    for j,x in enumerate(ks):
        k,*s = x
        if p[j]!= sum([bit[y-1] for y in s])%2:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=[]
K=[]
for i in range(M):
  s=list(map(int,input().split()))
  k=s[0]
  s.remove(s[0])
  K.append(k)
  S.append(s)
P=list(map(int,input().split()))
cnt=0
for i in range(2**N):
  d=[]
  for j in range(M):
    a=0
    for k in S[j]:
      a+=2**(k-1)
    if bin(a&i)[2:].count('1')%2==P[j]:
      d.append(1)
    else:
      d.append(0)
  if not 0 in d:
    cnt+=1
print(cnt)

Submission status: Accepted

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

lights = []

for _ in range(M):
  args = [int(x) - 1 for x in input().split()]
  args.pop(0)  # k は不要  
  switches = 0
  for i in args:
    switches |= (1 << i)
  lights.append(switches)
  
P = [int(x) for x in input().split()]

count = 0

# 2^10
for mask in range(1 << N):
  if all(bin(mask & s).count('1') % 2 == P[i] for i, s in enumerate(lights)):
    count += 1
      
print(count)

Submission status: Accepted

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

ans = 0
for i in range(2 ** N):
    ok = True
    bit = list(map(int, list(bin(i)[2:].rjust(N, "0"))))
    for S, p in zip(D, P):
        c = len([j for j in range(S[0]) if bit[S[1:][j]-1] == 1])
        if ok and c % 2 != p:
            ok = False
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product as prod

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

for pattern in (prod((0, 1), repeat=n)):
    tmp = []
    for i in range(len(ks)):
        rep = 0
        for j in ks[i][1:]:
            if pattern[j - 1] == 1:
                rep += 1
        if (rep & 1) == p[i]:
            tmp.append(True)
        else:
            tmp.append(False)
    if all(tmp):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import itertools


def sr(): return sys.stdin.readline().rstrip()


def ir(): return int(sr())


def lr(): return list(map(int, sr().split()))


def check(sws):
    on_list = []
    for i in range(M):
        on = 0
        for s in d_dict[i + 1]:
            on += sws[s]
        if on % 2 == p_list[i]:
            on_list.append(True)
        else:
            on_list.append(False)

    return all(on_list)


ans = 0


def dfs(depth, sws):
    global ans

    if depth == 0:
        return check(sws) * 1

    for i in range(2):
        t_sws = sws
        t_sws[depth] = i
        on = dfs(depth - 1, t_sws)
        ans += on

    return 0


N, M = lr()
d_dict = {}
for i in range(M):
    s_list = lr()
    d_dict[i + 1] = s_list[1:]

p_list = lr()

sw_list = [0] * (N + 1)
dfs(N, sw_list)
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
lista = []
for i in range(m):
    # s:判定に使用するスイッチ
    k, *s, = map(int, input().split())
    lista.append(list(s))
# p:2で割った時の余りが等しいと点灯
# 全てのpについて成り立たせよう
p = list(map(int, input().split()))

#p[0]について成り立たせよう
sumans = 0
# 全ての状態
for bit in range(1 << n):
    # 任意の状態aの中
    # 全ての電球について判定
    flag = True
    for i in range(m):
        sum = 0
        # 電球1について
        for j in lista[i]:
            if bit & (1 << (j - 1)):
                sum += 1
        if sum % 2 != p[i]:
            flag = False
    if flag:
        sumans += 1
print(sumans)

Submission status: Accepted

Solution code:
# input
inp = input()
switch_num = int(inp.split()[0]) #N
light_num = int(inp.split()[1]) #M
switch_info = [input() for i in range(light_num)]
p_info = input()

# データ整理
k_list = []
for l in switch_info:
    k_list.append(int(l.split()[0]))
s_list = []
for l in switch_info:
    l_list = [int(i) for i in l.split()[1:]]
    s_list.append(l_list)
p_list = [int(l) for l in p_info.split()]

#bit作成
bit_list = []
for i in range(2 ** switch_num):
    c = format(i,'b').zfill(switch_num)
    bit_list.append(c)
bit_list = [list(i) for i in bit_list]

#電球のon/off確認
result = 0
for bit in bit_list:
    on_num = 0
    for i in range(light_num):
        on_light = sum([int(bit[s-1]) for s in s_list[i]])
        # print(on_light)
        if p_list[i] == (on_light%2):
            on_num += 1
    if on_num == light_num:
        result += 1

print(result)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
lis = [None]*M
for i in range(M):
    lis[i] = list(map(int,input().split()))
p = list(map(int,input().split()))
answer = 0

for bit in range(1<<N):
    count =[]
    for i in range(N): #make bit
        mask = 1<<i
        if mask&bit:
            count.append(1)
        else:
            count.append(0)
        #process
    for j in range(M):
        temp = 0
        for k in range(lis[j][0]):
            temp+=count[lis[j][k+1]-1]
        if temp%2 != p[j]:
            break
    else:
        answer+=1
print(answer)

Submission status: Accepted

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

ans = 0

# N個のスイッチの状態をbit全探索
for i in range(2 ** N):
    cntFlg = True
    # 各電球について点灯状態を確認
    for m in range(M):
        # ONになっているスイッチの数をカウント
        onSwCnt = 0
        for j in range(L[m][0]):
            # SWがONなら
            if (i >> L[m][j+1] - 1) & 1:
                onSwCnt += 1
        if not P[m] == onSwCnt % 2:
            cntFlg = False

    if cntFlg:
        ans += 1

print(ans)

Submission status: Accepted

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

# スイッチに関して全探索
ans = 0
for item in itertools.product([0, 1], repeat=n):
    flag = True
    for i, switch in enumerate(switches):
        on_count = 0
        for s in switch:
            on_count += item[s-1]
        if on_count % 2 != p[i]:
            flag = False
    if flag: ans += 1
print(ans)

Submission status: Accepted

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

pattern = []
for bit in range(1<<n):
    stock = []
    for i in range(n):
        mask = 2**(n-i-1)
        if mask & bit:
            stock.append(1)
        else:
            stock.append(0)
    pattern.append(stock)

count = 0
for on_off in pattern:
    truf = True
    for j in range(m):
        count_s = 0
        for k in switch_wiring[j]:
            if on_off[k-1] == 1:
                count_s += 1
        if count_s % 2 != p[j]:
            truf = False
            break
    if truf:
        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)]
p = list(map(int,input().split()))

ans = 0
for i in range(2 ** n):
    on = [False] * n
    for j in range(n):
        if ((i>>j) & 1):
            on[n - j - 1] = True
    g = 0
    for j in range(m):
        c = 0
        for s in range(1,len(ks[j])):
            if on[ks[j][s]-1]:
                c += 1
        if c % 2 == p[j]:
            g += 1
    if g == m:
        ans += 1
print(ans)

Submission status: Accepted

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

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

def bitfield(n):
    return [int(digit) for digit in bin(n)[2:]]

count = 0
for i in range(1,2**N+1):
    bitarray = bitfield(i)
    bitarray.reverse()
    all_on_flg = True
    for j in range(0,M):
        num_on = sum([bitarray[k-1] if k <= len(bitarray) else 0 for k in ks[j][1:]])
        if num_on % 2 != ps[j]:
            all_on_flg = False
            break
    if all_on_flg:
        count += 1
            
print(count)

Submission status: Accepted

Solution code:
# C - Switches

import itertools

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

switch = ('0', '1')
ans = 0
for l in itertools.product(switch, repeat=n):
    for i, kslist in enumerate(ks):
        tmp = 0
        for j in range(1, (kslist[0])+1):
            tmp += int(l[kslist[j]-1])
        if (tmp%2)!=p[i]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n,m = map(int,input().split())
l = [list(map(int,input().split()))[1:] for _ in range(m)]
p = list(map(int,input().split()))
s = 0
a = 0
for i in product([0,1],repeat=n):
  for j in l:
    for k in j:
  #    print(i,j,k)
      a += i[k-1]
 #   print(a,p[l.index(j)])
    if a%2!=p[l.index(j)]:
      a =0
      break
    a =0
  else:
    s += 1
print(s)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
li_swich = [[0]*n for _ in range(m)]
li_k = []
for i in range(m):
    k, *swich = map(int, input().split())
    for j in swich:
        li_swich[i][j-1] = 1
li_p = [int(x) for x in input().split()]
#すべてのすいっちについて考える
how_many = 0
for i in range(1<< n):
    b = True
    for k in range(len(li_swich)):
        count = 0
        li = li_swich[k]
        for j in range(len(li)):
            if (i>>j)&1:
                count += li[j]
        if count%2  != li_p[k]:
            b = False
    if b:
        how_many += 1

print(how_many)

Submission status: Accepted

Solution code:
# 23:20
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(2**n):
    for s, p in zip(S, P):
        c = 0
        for t in s:
            if (i >> t-1) & 1:
                c += 1
        if c % 2 != p:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

    ans = 0
    for i in range(1<<n):
        for j in range(m):
            cnt = 0
            for b in s[j][1:]:
                if (i>>b)&1: cnt += 1
            if cnt%2 != p[j]: break
        else: ans += 1

    return ans

if __name__ == "__main__":
    print(solve())

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
def check(x):
    ok = True
    for i in range(m):
        cnt = 0
        for j in range(len(s[i])):
            if not j:continue
            if (x>> (s[i][j]-1))%2:cnt +=1
        if cnt%2 != p[i]:
            ok = False
            break
    return ok
for i  in range(2**n):
    if check(i):ans +=1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    judge = 0
    for j in range(M):
        c = 0
        for k in S[j]:
            if ((i>>(k-1)) & 1):
                c += 1
        if c % 2 != P[j]:
            judge = 1
            break
    if judge == 0:
       ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	#a = int(input())
	n, m = IN()
	#s = input()
	sn=[0]*n
	for i in range(m):
		dd=2 ** i
		al=list(IN())
		for ni in al[1:]:
			sn[ni-1] += dd
	
	switch_aa=list(IN())
	switch_aaa=0
	for i, v in enumerate(switch_aa):
		if v == 1:
			switch_aaa+= 2**i
	
	cc=0
	for state_i in range(2 ** n):
		switch_state=0
		for switch_i, is_on in enumerate(bin(state_i+2**12)[14-n+1:]):
			if is_on == '1':
				switch_state = switch_state ^ sn[switch_i]
		else:
			switch_state = switch_state ^ switch_aaa
			if switch_state == 0:
				cc+=1
	print(cc)
			
		
				
			
			
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

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()))
ans = 0
for i in range(2**N):
  switch = {i:0 for i in range(1, N+1)}
  for j in range(N):
    if (i>>j)&1:
      switch[j+1] += 1    
  flag = True
  for i in range(M):
    k = ks[i][0]
    s = ks[i][1:]
    pp = p[i]
    cnt = 0
    for ss in s:
      if switch[ss] == 1:
        cnt += 1
    if cnt % 2 != pp:
      flag = False

  if flag:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
k=[]
s=[]
for i in range(m):
  arr=input().split()
  k.append(int(arr[0]))
  s.append([int(arr[j+1]) for j in range(k[i])])
p=list(map(int,input().split()))
chk=[]
for i in range(1<<n):
  wk=[]
  for j in range(n):
    if 1&(i>>j)==1:
      wk.append(j+1)
  chk.append(wk)
ans=0
for i in range(len(chk)):
  calc=[0]*m
  for j in range(len(chk[i])):
    for l in range(m):
      for x in range(k[l]):
        if s[l][x]==chk[i][j]:
          calc[l]+=1
  ans+=1
  for l in range(m):
    if calc[l]%2!=p[l]:
      ans-=1
      break
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    n, m = map(int, input().split())
    ks = [list(map(int, input().split())) for _ in range(m)]
    p = list(map(int, input().split()))
    ans = 0
    for i in range(2**n):
        switch = [0]*n
        flag = True
        for j in range(n):
            if (i >> j) & 1:
                switch[j] = 1
        for k in range(m):
            test = ks[k][1:]
            on = 0
            for l in range(len(test)):
                if switch[test[l]-1] == 1:
                    on += 1
            if on % 2 != p[k]:
                flag = False
        if flag:
            ans += 1
    print(ans)

resolve()

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

ans = 0
# 全探索
for i in range(2**N):
    light = 0
    for j in range(M):
        count = 0
        for k in range(1, ks[j][0]+1):
            if i & 2**(ks[j][k]-1) == 2**(ks[j][k]-1):
                count += 1
        if count % 2 == p[j]:
            light += 1
    if light == M:
        ans += 1

print(ans)

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):
    on = [0 for _ in range(n)]
    for j in range(n):
        if((i>>j)&1):
            on[j]=1
    all_on = True 
    for j in range(m):
        on_num = 0 
        for s in ks[j][1: ]:
            if(on[s-1]==1):
                on_num += 1 

        if(on_num%2 != p[j]):
            all_on = False
            break 

    if(all_on):
        res += 1
print(res)

Submission status: Accepted

Solution code:
# pythonで青くなるブログ
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M = map(int, input().split())
lamps = [list(map(lambda x:int(x)-1, input().split()))[1:]
         #1個目は繋がっているスイッチの個数
         #2個目以降が繋がっているスイッチの番号、0始まりに
         for _ in range(M)]
p = list(map(int, input().split()))
# on になっているスイッチの個数を2で割った余りがpiに等しい時に点灯
ans = 0

# bit全探索(スイッチの入れ方を全探索する)
for i in range(1 << N):#2^N分、Bit検索
    for r in range(M):  # 全てのランプがついてるかチェック
        on_sum = 0  # ランプrにおいて、onのスイッチの数。電球はM個。
        for j in range(N):  # スイッチのj番目について
            if i >> j & 1 and j in lamps[r]:
            #j番目のフラグが立って、電球rのj番目のスイッチが入っていれば
                on_sum += 1  
                # スイッチjがランプrに繋がってて、onならon_sum+=1
        if on_sum % 2 != p[r]:  # on_off check
            break  # 一つでもoffなら次のbitに
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# pythonで青くなるブログ
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M = map(int, input().split())
lamps = [list(map(lambda x:int(x)-1, input().split()))[1:]
         #1個目は繋がっているスイッチの個数
         #2個目以降が繋がっているスイッチの番号
         for _ in range(M)]
p = list(map(int, input().split()))
# on になっているスイッチの個数を2で割った余りがpiに等しい時に点灯
ans = 0

# bit全探索(スイッチの入れ方を全探索する)
for i in range(1 << N):
    for r in range(M):  # 全てのランプがついてるかチェック
        on_sum = 0  # ランプrにおいて、onのスイッチの数
        for j in range(N):  # スイッチのj番目について
            if i >> j & 1 and j in lamps[r]:
                on_sum += 1  
                # スイッチjがランプrに繋がってて、onならon_sum+=1
        if on_sum % 2 != p[r]:  # on_off check
            break  # 一つでもoffなら次のbitに
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

import itertools
N,M = map(int,readline().split())
S = [list(map(int,readline().rstrip().split()))[1:] for m in range(M)]
P = list(map(int,readline().rstrip().split()))

ans = 0
for t in itertools.product([0,1],repeat=N):
    bool = True
    for i in range(M):
        Q = sum([t[s-1] for s in S[i]])
        if (Q-P[i])%2 != 0:
            bool = False
            break
    if bool:
        ans += 1
print(ans)

Submission status: Accepted

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

k = [0] * M
s = [[0] * N for i in range(M)]
tmp = [0] * (N + 1)
for i in range(M):
    tmp = [int(i) for i in input().split()]
    k[i] = tmp[0]
    s[i] = tmp[1 : k[i] + 1]

p = [0] * M
p = list(map(int, input().split()))

#電球に接続されたスイッチのonの数
s_cnt = [0] * M
ans = 0

for i in range(2 ** N):
    bit_str = format(i, "0"+str(N)+"b")
    s_on = True
    for j in range(len(bit_str)):
        if bit_str[j] == "1":
            for k in range(len(s)):
                if j+1 in s[k]:
                    s_cnt[k] += 1
    for j in range(len(s_cnt)):
        if s_cnt[j] % 2 != p[j]:
            s_on = False
    if s_on:
        ans += 1
    s_cnt = [0] * M

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
all_li = []
for _ in range(m):
    li = list(map(int,input().split()))
    li.pop(0)
    all_li.append(li)
p_li = list(map(int,input().split()))

kumi = list(itertools.product([0,1], repeat=n))
# print(list(itertools.product([0,1], repeat=n)))
# [(0, 0), (0, 1), (1, 0), (1, 1)]

#print(all_li)
# [[1, 2], [2]]

count = 0
for k in kumi:
    flag = True
    for i,each_li in enumerate(all_li):
        tmp = 0
        for e in each_li:
            if list(k)[e-1] == 1:
                tmp += 1
        if tmp%2 != p_li[i]:
            flag = False
    if flag:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools
from math import *
from bisect import *
from heapq import *
from collections import *

def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N, M = In.ints()

bulbcons = [0]*M

for i in range(M):
    bulbcons[i] = In.ints()[1::]

p = In.ints()
ans = 0

# print(bulbcons)
# print(p)
for comb in itertools.product(range(2), repeat=N):
    # print(comb)
    problem = False

    for i in range(M):
        res = sum([comb[bulbcons[i][j]-1] for j in range(len(bulbcons[i]))])

        if res%2 != p[i]:
            problem=True
            break
            
    if not problem:
        # print(comb)
        ans+=1

print(ans)


######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Accepted

Solution code:

def main():
    n, m = map(int, input().split())
    lamps = []
    for _ in range(m):
        data = [int(i)-1 for i in input().split()][1:]
        lamps.append(data)
    p = [int(i) for i in input().split()]

    #bit全探索
    #全てのswichのonoffを試す
    res = 0
    for i in range(1<<n):
        onSwitch = set()
        flag = True
        for j in range(n):
            if i>>j & 1:
                onSwitch.add(j)
        #swichOn setに含まれるlamp jのswitchの数を数える
        for j in range(m):
            cnt = 0
            for k in range(len(lamps[j])):
                if lamps[j][k] in onSwitch:
                    cnt += 1
            if cnt%2 != p[j]:
                flag = False
        if flag:
            res += 1 
    print(res)
main()

Submission status: Accepted

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

ans = 0
for i in range(1<<N):
    for j in range(M):
        cnt = 0
        for s in S[j][1:]:
            if i >> s & 1: cnt += 1
        if cnt%2 != P[j]: break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
s = [[0] * n for _ in range(m)]
for i in range(m):
    k, *si = map(int, input().split())
    for j in si:
        s[i][j - 1] = 1
p = list(map(int, input().split()))
l = list(itertools.product([0, 1], repeat=n))
ans = 0
for i in l:
    for index, j in enumerate(s):
        if sum([x * y for x, y in zip(i, j)]) % 2 != p[index]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
switch, light = map(int, input().split())
K = []
for _ in range(light):
    k = list(map(int, input().split()))
    K.append(k)
P = list(map(int, input().split()))

ans = 0
# bit全探索で全パターンをチェックする
for i in range(2**switch):

    # 各電球につながっているスイッチが何個ONか
    switch_on_list = [0]*light

    # 各スイッチの状態チェック
    for j in range(switch):
        # スイッチが付いているか
        if ((i >> j) & 1):
            # スイッチがつながっているライトを+1
            for k in range(light):
                for l in range(1, K[k][0]+1):
                    if j == K[k][l]-1:
                        switch_on_list[k] += 1

    # 電球が点灯する数のスイッチがONか
    for j in range(light):
        if switch_on_list[j] % 2 != P[j]:
            break
    else:
        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()))

ans=0
for i in range(2**n):
  num=0
  #ある電球
  for j in range(m):
    cnt=0
    #ある電球に接続されている各スイッチ
    for k in range(1,l[j][0]+1):
      if (i>>l[j][k]-1) & 1:
        cnt+=1
    if cnt%2==p[j]:
      num+=1
  if num==m:
    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()))

ans=0
for i in range(2**n):
#  bit=format(i,'011b')
#  bit=list(reversed(format(i,'b')))
#  bit=bin(i)
#  print(bit)
  #ある電球
  num=0
  for j in range(m):
    #ある電球に接続されている各スイッチ
    cnt=0
    for k in range(1,l[j][0]+1):
#      print(l[j][k])
#      if bit[l[j][k]]==1:
#      if (i>>k)&1:
#      print(i,l[j][k])
      if (i>>l[j][k]-1)&1:
        cnt+=1
#    print(i,j,cnt)
    if cnt%2==p[j]:
      num+=1
  if num==m:
    ans+=1
print(ans)

Submission status: Accepted

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

uoo = []

for _ in range(m):
    x = list(map(int, input().split()))
    x.pop(0)
    uoo.append(x)

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


pattern = []

for i in range(2 ** (n)):
    tmp = [0] * (n)
    for j in range(n):
        if i >> j & 1:
            tmp[j] = 1
    pattern.append(tmp)


ans = 0

for pat in pattern:
    is_light_up = True
    cnt = 0
    for uo in uoo:
        is_even = True
        for u in uo:
            if pat[u-1] == 1:
                is_even = not is_even
        if is_even:
            if p[cnt] == 1:
                is_light_up = False
        else:
            if p[cnt] == 0:
                is_light_up = False
        cnt += 1
    if is_light_up:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
switchss = []
for _ in range(M):
    k, *sws = map(int, input().split())
    switchss.append([sw-1 for sw in sws])
ps = list(map(int, input().split()))

ans = 0
for S in range(1<<N):
    for i in range(M):
        num = 0
        for sw in switchss[i]:
            if (S>>sw) & 1:
                num += 1
        if num%2 != ps[i]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc157/tasks/abc157_d
N,M = map(int, input().split())

K = []
S = []
P = []

for i in range(M):
    k,*s = map(int, input().split())
    K.append(k)
    S.append(s)
*P, = map(int, input().split())
ans = 0

for i in range(2**N):
    Switch = ["on"]*N
    flg = 0

    for j in range(N):
        if (i>>j)&1:
            Switch[j] = "off"
    for s in range(len(S)):
        count = 0
        for switch in range(len(Switch)):
            if ((switch+1) in S[s]) and Switch[switch]=="on":
                count = count + 1
        if count%2!=P[s]:
            flg = 1
            continue
    if flg==0:
        ans = ans + 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
k=[]
s=[]
for _ in range(m):
  k_=list(map(int,input().split()))
  k.append(k_[0])
  s.append(k_[1:])
p=list(map(int,input().split()))
#print(s)
#print(p)
#print(k)
ans=0
for i in range(2**n):
  sw=str(bin(i)).replace('b','00000000000')#右からi番目が1->スイッチiがON
  f=True
  for j in range(m):# m個の電気に対して
    n_on=0
    for sj in s[j]:
      if sw[-sj]=='1':
        n_on+=1
    if n_on%2!=p[j]: # j個目の電気がNG
      f=False
      break
  if f==True:
    ans+=1
    #print(sw)
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N, M = map(int, input().split())
    K = [list(map(int, input().split())) for _ in range(M)]
    P = list(map(int, input().split()))
    # bit全探索
    ans = 0

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

        for j in range(N): #それぞれのスイッチがonかoffか
            if 1 & (i >> j):
                s[j] = True

        for light in range(M):
            count = 0
            for switch in range(1, K[light][0]+1):
                if s[K[light][switch]-1]: #1indexなので
                    count += 1
            if count &1 != P[light] &1:
                break
        else: #breakせず終了した場合、すべて点灯している。
            ans += 1
    print(ans)



if __name__ == '__main__':
    solve()