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())
dic_s = {}
for i  in range(n):
    dic_s[i] = []
for i in range(m):
    a = list(map(int, input().split()[1:]))
    for num in a:
        dic_s[num-1].append(i)
p = list(map(int, input().split()))
total = 0

def judge_bright(judge):
    for i,num in enumerate(judge):
        if num%2 != p[i]:
            return False
    return True

for i in range(2 ** n): # n個のスイッチの組み合わせ
    judge = [0 for i in range(m)]
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 1だったら(オンだったら)
            for d in dic_s[j]: #jのスイッチにつながる電球がカウントされる
                judge[d] += 1
    
    if judge_bright(judge):      # ぜんぶついた！
        total+=1
print(total)

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

import itertools
L = [0, 1] #生成する数字
num = N #生成するビット数
bit_list = list(itertools.product([0, 1], repeat=num))
ans = 0

for i in range(len(bit_list)):
    light = 0
    for j in range(len(ks)):
        count = 0
        for k in range(1,len(ks[j])):
            if bit_list[i][ks[j][k]-1] == 1:
                count += 1
        if count%2 == p[j]:
            light += 1
    if light == M:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
#abc128c
n,m=map(int,raw_input().split())
s=[map(int,raw_input().split()) for i in range(m)]
p=map(int,raw_input().split())
res=0
for i in range(2**n):
 res+=1
 for j in range(len(s)):
  on=0
  for k in range(s[j][0]):
   on+=((i>>(s[j][k+1]-1))%2)
  if on%2!=p[j]:
   res-=1
   break
print res

Submission status: Accepted

Solution code:
#x=int(input())
n,m=map(int,input().split())
#xl=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(m)]
pl=list(map(int,input().split()))
ans=0
for i in range(2**n):
    b=bin(i)
    switch=[0 for k in range(10)]
    for j in range(n):
        if ((i >> j) & 1):#二進数iの下から数えてj桁目が1か否か
            switch[j]=1
    flag=True
    for a in range(m):#それぞれのスイッチについてチェック
        templ=l[a]
        k=templ[0]
        count=0
        for t in range(k):
            s=templ[t+1]
            if switch[s-1]==1:
                count+=1
        if count%2!=pl[a]:
            flag=False
            break
    if flag:
        ans+=1
print(ans)

Submission status: Accepted

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

pattern=[]
ans=0
for i in range(2**(n)):
  count=0
  tmp=[0]*n
  for j in range(n):
    if i>>j & 1:
      tmp[j]=1
  pattern.append(tmp)
  #print(pattern[i])
  for j in range(m):
    num=0
    for t in range(k[j]):
      num+=pattern[i][s[j][t]-1]
    if (num%2==p[j]%2):
      count+=1
  if (count==m):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = []
for _ in range(M):
    arr = list(map(int, input().split()))
    bit = 0
    for i in arr[1:]:
        bit = bit | (1 << (i - 1))
    S.append(bit)
P = list(map(int, input().split()))

ans = 0
for bit in range(1 << N):
    for i in range(M):
        p = S[i] & bit
        on = 0
        for j in range(N):
            if p & (1 << j):
                on += 1
        if (on % 2) != P[i]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = []
for _ in range(M):
    arr = list(map(int, input().split()))
    bit = 0
    for i in arr[1:]:
        # print(i)
        bit = bit | (1 << (i - 1))
    # print('bit', bit, bin(bit))
    S.append(bit)
    # S.append(arr[1:])
P = list(map(int, input().split()))
# print('S')
# print(S)
# print('P', P)
ans = 0
for bit in range(1 << N):
    cnt = 0
    for i in range(M):
        # print('S[i], bit', bin(S[i]), bin(bit))
        p = S[i] & bit
        # print('p', bin(p))
        on = 0
        for j in range(N):
            # print('judge', 1 << j, p & (1 << j))
            if p & (1 << j):
                on += 1
            # if p & (1 << j):
            #     on += 1
        # print('P[i], i, on', P[i], i, on)
        # print('on', on)
        if (on % 2) == P[i]:
            cnt += 1
    if cnt == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = []
for _ in range(M):
    arr = list(map(int, input().split()))
    bit = 0
    for i in arr[1:]:
        # print(i)
        bit = bit | (1 << (i - 1))
    # print('bit', bit, bin(bit))
    S.append(bit)
    # S.append(arr[1:])
P = list(map(int, input().split()))
# print('S')
# print(S)
# print('P', P)
ans = 0
for bit in range(1 << N):
    cnt = 0
    for i in range(M):
        # print('S[i], bit', bin(S[i]), bin(bit))
        p = S[i] & bit
        # print('p', bin(p))
        on = 0
        for j in range(N):
            # print('judge', 1 << j, p & (1 << j))
            if p & (1 << j):
                on += 1
            # if p & (1 << j):
            #     on += 1
        # print('P[i], i, on', P[i], i, on)
        # print('on', on)
        if (on % 2) != P[i]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    ls = [0] * n
    
    for j in range(n):
        if (i >> j) & 1:
            ls[j] = 1
            
    am = [0] * m      
    
    for j in range(m):
        for k in s[j][1:]:
            if ls[k-1] == 1:
                am[j] += 1
    
    t = 0
    for j in range(m):
        if am[j] % 2 == p[j]:
            t += 1
        
    if t == m:
        ans += 1
        
print(ans)

Submission status: Accepted

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

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

    #このパターンで電球が点灯するか調べる
    for k in range(m):
        set_s=set(ks[k][1:])
        on_num=len(set_s&set(on_swich))
        if on_num%2!=p[k]:break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def inpl():
    return tuple(map(int, input().split()))


def getPattern(i):
    return {j for j in range(N) if (i >> j) % 2}


def isOn(pattern):
    return all(P[i] == len(pattern & S[i]) % 2 for i in range(M))


N, M = inpl()
S = []
for _ in range(M):
    tmp = inpl()
    tmp = [t - 1 for t in tmp[1:]]
    S.append(set(tmp))
P = inpl()

ans = 0
for i in range(2**N):
    pattern = getPattern(i)
    ans += int(isOn(pattern))
print(ans)

Submission status: Accepted

Solution code:

N, M = map(int, input().split())
K = []
S = []
for i in range(M):
    s = list(map(int, input().split()))
    K.append(s[0])
    S.append(s[1:])
P = list(map(int, input().split()))

counter = 0

for i in range(1<<N):
    b = format(i, '0%db'%N)
    flag = True
    for j in range(M):
        c = 0
        for k in S[j]:
            c += int(b[k-1])
        if c % 2 != P[j]:
            flag = False
    if flag:
        counter += 1

print(counter)

Submission status: Accepted

Solution code:
def roop(onoff, n):
    swit[n] = onoff
    if n == N-1:
        flag = True
        for i in range(M):
            if flag == False: break
            cur = 0
            for s in range(1,data[i][0]+1):
                cur += swit[data[i][s]-1]
            if cur%2 != p[i]:
                flag = False
                break
        if flag:
            return 1
        else:
            return 0
    else:
        return roop(0,n+1) + roop(1,n+1)
        

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

swit = [0]*N
print(roop(0,0) + roop(1,0))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
d_s_list = []
for i in range(m):
  d_s = list(map(int,input().split()))
  d_s_p = d_s[1:]
  d_s_list.append(d_s_p)
check_list = list(map(int,input().split()))
s_case = []
for i in range(2**n):
  s = [0 for i in range(n)]
  for j in range(n):
     if ((i >> j) & 1):
        s[j] = 1
  s_case.append(s)
  
ok_list = []
for case in s_case:
  frug = True
  for d_s in range(m):
    checker = 0
    for i in d_s_list[d_s]:
      checker  +=  case[i - 1] 
    if checker % 2 != check_list[d_s]:
      frug = False
  if frug == True:
    ok_list.append(case)
    
print(len(ok_list))

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

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

S = defaultdict(set)
for i in range(M):
    k, *s = map(int, input().split())
    for j in s:
        S[j - 1].add(i)

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

ans = 0
for i in range(2 ** N):
    on = [(i & (1 << j)) > 0 for j in range(N)]
    count = defaultdict(int)
    for j, ok in enumerate(on):
        if ok:
            for k in S[j]:
                count[k] += 1
    if all(count[j] % 2 == p[j] for j in range(M)):
        ans += 1
print(ans)

Submission status: Accepted

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

ans=0
for bit in range(1<<n):
    for i in range(m): #それぞれの電球について
        if P[i]!= sum([bit>>(j-1) & 1 for j in A[i]])%2:
            break
        if i==m-1:
            ans+=1

print(ans)

Submission status: Accepted

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

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

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

ans = 0

for i in range(2**N):
    flag = True
    for j in range(M):
        tmp = 0
        for h in range(1,s[j][0]+1):
            if (i>>(s[j][h]-1))&1:##点灯する
                tmp += 1
        if tmp%2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# from math import factorial,sqrt
# from itertools import permutations as permus
# from fractions import gcd
# from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

import numpy as np
# import scipy as scp

# 入力の受け取り
n,m = map(int,input().split())
# 配列入力の受け取り
lights = [list(map(int,input().split())) for _ in range(m)]
lightflg = list(map(int,input().split()))

ans = 0
for switch_bits in range(0,1<<n):
    allflg = True
    for i in range(m):
        flg = lightflg[i]
        on_count = 0
        for switch in lights[i][1:]:
            switch -= 1
            if switch_bits>>switch & 1:
                on_count += 1
        if on_count%2 != flg:
            allflg = False
            break
    if allflg:
        ans += 1

print(ans)
# print("{:.10f}".format(ans))
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する

Submission status: Accepted

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

cnt = 0

for i in range(2 ** N):
    flag = True
    for j in range(M):
        if not([(i >> k-1) & 1  for k in s[j]].count(1) % 2 == p[j]):
            flag = False
    if flag:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
k = []
s = []
for i in range(m):
    kk,*ss = map(int,input().split())
    k.append(kk)
    s.append(ss)
p = [int(x) for x in input().split()]
d = []
ans = 0

for i in range(2**n): #スイッチの押し方の全列挙
    flag = True
    for j in range(m): #各電球について
        count = 0
        for l in range(len(s[j])): #各電球のスイッチにについて
            tmp = s[j][l]
            #l番目のスイッチがオンかどうか
            if (i >> tmp-1) & 1 == 1:
                count += 1
        #各電球について、オンになっているスイッチの総数を2で割って点灯しているか調べる
        if count%2 != p[j]:
            flag = False
    #flagがTrueであればi番目のスイッチの押し方で全ての電球が点灯する
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m =map(int,input().split())
s_li = []
k_li = []
for i in range(m):
  inp = list(map(int,input().split()))
  k_li.append(inp[0])
  s_li.append(inp[1:])
p_li = list(map(int,input().split()))
cnt = 0 
for bit in range(1<<n): #n桁のbitを用意しオンオフを管理する
  ok = True
  for i in range(m):#m個の電球それぞれについてスイッチがいくつオンになってるか調べる
    con = 0 #最初はオンになっているスイッチは0
    for j in s_li[i]:
      #i個目の電球に繋がっているki個のスイッチのオンオフを調べたい
      if ((bit >> j-1) & 1) == 1:
        #i個目の電球に繋がっているj個目のスイッチのオンオフを用意しておいたbitと照らし合わせて確認
        con += 1
    if con%2 != p_li[i]:
      ok = False
  if ok == True:
    cnt += 1
print(cnt)

Submission status: Accepted

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

answer = 0
for i in range(1 << N):
    for (_, *ss), p in zip(kss, ps):
        okay = True
        if sum([(i >> s-1) & 1 for s in ss]) % 2 != p:
            okay = False
            break
    if okay:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
from itertools import product

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

answer = 0
for switches in product(range(2), repeat=N):
    for (_, *ss), p in zip(kss, ps):
        okay = True
        if sum([switches[s-1] for s in ss]) % 2 != p:
            okay = False
            break
    if okay:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:


n,m=map(int,input().split())

s=[]

for i in range(m):
    sss=list(map(int,input().split()))
    k=sss[0]
    b=0
    for ss in sss[1:]:
        b+=0b1<<(ss-1)
    s.append(b)


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

def cntbin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count

ans=0

for i in range(2**n):
    ok=True
    for k in range(m):
        cnt=cntbin(i&s[k])
        if cnt%2==p[k]:
            pass
        else:ok=False

    if ok:ans+=1

print(ans)

Submission status: Accepted

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

ans=0

for i in range(2**n):
    switch=[None]*n
    for j in range(n):
        if ((i>>j)&1)==1:
            switch[j]=True
    cnt=0
    for x,light in enumerate(k):
        tmp=0
        for i in range(len(light)):
            if i==0:
                continue
            if switch[light[i]-1]==True:
                tmp+=1
        if tmp%2==p[x]:
            cnt+=1
    if cnt==m:
        ans+=1
print(ans)

Submission status: Accepted

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

res = 0
for bit in range(2**N):
  sw = [0] * N
  for i in range(N):
    sw[i] = (bit >> i) & 1
  are_shining = True
  for i in range(M):
    cnt_on = 0
    for j in range(k[i]):
      if sw[s[i][j]-1] == 1:
        cnt_on += 1
    if cnt_on % 2 != p[i]:
      are_shining = False
  if are_shining:
    res += 1

print(res)

Submission status: Accepted

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

    ans = 0
    for ps in range(2**n):
        fl = [False] * m
        for k, v in enumerate(S):
            cnt = 0
            for s in v:
                if ps & 1 << (s-1):
                    cnt += 1

            if cnt % 2 == P[k]:
                fl[k] = True

        if all(fl):
            ans += 1

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

cnt = 0

for i in range(2 ** N):
    flag = True
    for j in range(M):
        if not([(i >> k-1) & 1  for k in s[j]].count(1) % 2 == p[j]):
            flag = False
    if flag:
        cnt += 1

print(cnt)

Submission status: Accepted

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

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

count = 0
for i in range(2**n):
    flag = True
    for j in range(m):
        if not([1 & (i >> k-1) for k in s[j]].count(1) % 2 == p[j]):
            flag = False
    if flag:
        count += 1
print(count)

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

ans=0

def dfs(i,f):
    global ans
    if i==n-1:
        a=0
        for j in range(len(l)):
            sw=p[j]+1
            x=l[j][1:]
            for k in x:
                if f[k-1]=="1":
                    sw+=1
            #print(sw)
            if sw%2:
               a+=1
        #print(a)
        if a==len(p):
            ans+=1
        return 0
    else:
        dfs(i+1,f+"0")
        dfs(i+1,f+"1")

dfs(0,"0")
dfs(0,"1")
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[0]*M
for i in range(M):
 A[i]=list(map(int,input().split()))
P=list(map(int,input().split()))
F=0
for i in range(2**N):
 E=0
 Sui=[0]*N
 for j in range(N):
  if ((i >> j) & 1):
   Sui[j]+=1
 for k in range(M):
  D=0
  for l in range(1,A[k][0]+1):
   if Sui[A[k][l]-1]==1:
    D+=1
  if D%2==P[k]:
   E+=1
 if E==M:
  F+=1
print(F)

Submission status: Accepted

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

s = []
for i in range(m):
  array = list(map(int, input().split()))
  tmp = 0
  for j in range(1, len(array)):
    tmp += 2 ** (array[j]-1)
    
  s.append(tmp)

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

count = 0
for i in range(0, 2**n):
  array = []
  for j in range(len(s)):
    tmp = i & s[j]
    tmp = bin(tmp).replace('0b', '').replace('0', '')
    r = len(tmp) % 2
    array.append(r)
    
  if p == array:
    count += 1
    
print(count)

Submission status: Accepted

Solution code:
from itertools import product

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


count = 0
for i in product([0,1], repeat=n):
    i = list(i)
    on = True
    for j in range(m):
        score = 0
        for k in s[j]:
            if i[k] == 1:
                score += 1
        if score % 2 == p[j]:
            continue

        else:
            on = False
            break

    if on:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
L = [[] for _ in range(M)]
for i in range(M):
  L[i] = list(map(int,input().split()))
  L[i].remove(L[i][0])
P = list(map(int,input().split()))
Cand = []
for i in range(2**N):
  res = []
  for j in range(N):
    if ((i>>j) & 1):
      res.append(1)
    else:
      res.append(0)
  Cand.append(res) 
res = 0
for i in range(2**N):
    key = 0
    loop = 0
    for j in range(M):
        loop = 1
        if P[j] == 0:
            Even_counter = 0
            for el in L[j]:
                if Cand[i][el-1] == 1:
                    Even_counter += 1
            if Even_counter % 2 != 0:
                key = 1
                break
        if P[j] == 1:
            Od_counter = 0
            for el in L[j]:
                if Cand[i][el-1] == 1:
                    Od_counter += 1
            if Od_counter % 2 != 1:
                key = 1
                break           
        if key == 0 and j == M-1 and loop == 1:
            res += 1    
print(res)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
n,m=f()
ll=[[0]*n for _ in range(m)]
for l in ll:
  k,*s=f()
  for i in s: l[i-1]=1
p=list(f())
import itertools as it
print(sum(all(sum(a*b for a,b in zip(l,t))%2==p[i] for i,l in enumerate(ll)) for t in it.product([0,1],repeat=n)))

Submission status: Accepted

Solution code:
def int_to_list(bit, n):
    l = []
    for i in range(n):
     if bit & (1 << i):
         l.append(i)
    return l

def solve():
    N, M = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(M)]
    p = list(map(int, input().split()))

    c = 0
    for i in range(1 << N):
        partial = int_to_list(i, N)
        b = True
        
        for j in range(M):
            d = 0
            for k in range(A[j][0]):
                if A[j][k+1]-1 in partial:
                    d += 1
            if d % 2 != p[j]:
                b = False

        if b:
            c += 1
        
    return c

print(solve())

Submission status: Accepted

Solution code:
import itertools

n,m= map(int, input().split())
l = [list(map(lambda x:int(x)-1, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))

res = 0
for i in itertools.product(range(2), repeat=n):
  i = list(i)
  flg = 0
  for j in range(m):
    now = 0
    for k in l[j]:
      if i[k] == 1:
        now += 1
    if now % 2 == p[j]:
      continue
    else:
      flg += 1
      break
  if flg == 0:
    res += 1
    
print(res)

Submission status: Accepted

Solution code:
from sys import stdin

N, M = map(int, stdin.readline().split())
light = [None] * M
for i in range(M):
    light[i] = list(map(int, stdin.readline().split()))[1:]
P = list(map(int, stdin.readline().split()))

ans = 0
for i in range(2 ** N):
    on_switch = [0] * N
    for j in range(N):
        if int(format(i, 'b').zfill(N)[j]) == 1:
            on_switch[j] = 1

    on_bulb = 0
    for j in range(M):
        num_of_on_switch = 0
        for index in light[j]:
            num_of_on_switch += on_switch[index - 1]
        if num_of_on_switch % 2 == P[j]:
            on_bulb += 1
    if on_bulb == M:
        ans += 1

print(ans)

Submission status: Accepted

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

sw = list(product([True, False], repeat=N))
cnt, ans = 0, 0
for pat in sw:
  flag = True
  for i in range(M):
    cnt = 0
    for j in range(ks[i][0]):
      if pat[ks[i][j+1]-1]:
        cnt += 1
    if cnt % 2 != p[i]:
      flag = False
      break
  if flag:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
light = [0 for _ in range(m)]
for i in range(m):
  key = [int(x) for x in input().split()]
  light[i] = key[1:]

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

ans = 0
for i in range(2**n):
  switch = [0]*n
  for j in range(n):
    if (i >> j) & 1:
      switch[j] = 1
  for j in range(m):
    x = 0
    for k in light[j]:
      if switch[k-1]:
        x += 1
    if x % 2 == p[j]:
      pass
    else:
      break
    if j == m-1:
      ans += 1
      
print(ans)

Submission status: Accepted

Solution code:
# 11　AtCoder Beginner Contest 128 C - Switches
n, m = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    d = [0]*n
    flag = True
    for j in range(n):
        if ((i>>j)&1):
            d[j] = 1
    for k in range(m):
        count = 0
        for l in range(1,s[k][0]+1):
            if d[s[k][l]-1]:
                count += 1
        if count%2!=p[k]:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n_switch, n_light = [int(i) for i in input().split()]
l_s = [[int(i)-1 for i in input().split()][1:] for _ in range(n_light)]
pp = [int(i) for i in input().split()]

ans = 0
for bit in range(1 << n_switch):
    on_switch = {i for i in range(n_switch) if (bit >> i) & 1}
    for i, p in enumerate(pp):
        ok = set(l_s[i]).intersection(on_switch)
        if len(ok) % 2 != p:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

def main():
    N, M = list(map(int, input().split()))
    ks = [list(map(int, input().split())) for _ in range(M)]
    p = list(map(int, input().split()))
    ans = 0

    for condition in ks:
        condition[1:] = list(map(lambda x: x-1, condition[1:]))
    
    for i in range(1 << N):
        switch = [None] * N
        for j in range(N):
            switch[j] = 1 if ((i >> j) & 1) else 0
        
        flag = True
        for m in range(M):
            s = ks[m][1:]
            if sum(switch[idx] for idx in s) % 2 != p[m]:
                flag = False
                break
        if flag:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def main():
    N, M = list(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(1 << N):
        switch = [None] * N
        for j in range(N):
            switch[j] = 1 if ((i >> j) & 1) else 0
        
        flag = True
        for m in range(M):
            tmp = 0
            k = ks[m][0]
            s = list(map(lambda x: x-1, ks[m][1:]))
            for idx in s:
                tmp += switch[idx]
            if tmp % 2 != p[m]:
                flag = False
                break
        if flag:
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import bisect
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
nl = lambda: list(map(int, stdin.readline().split()))

n, m = na()
l = []
for i in range(m):
    s = na()
    l.append(s[1::])
p = na()
ans = 0
for i in range(2**n):
    tmp = [0] * n
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            tmp[j] = 1
    for s, pi in zip(l, p):
        total = 0
        for si in s:
            if tmp[si-1]:
                total += 1
        if total % 2 != pi:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = [int(_) for _ in input().split()]
l = []
for i in range(m):
    l.append([int(_) for _ in input().split()])
p_l = [int(_) for _ in input().split()]
# print(l)
# print(p_l)
ans = 0
for i in range(2**n):
    i_bin = format(i, '0' + str(n) + 'b')
    flag = True

    # print('i_bin', i_bin)

    for i in range(m):

        # print('i', i)

        k = l[i][0]

        # print('k', k)

        c = 0
        for j in range(k):
            c += int(i_bin[l[i][j + 1] - 1])

            # print('j', j)
            # print('i_bin[l[i][j] - 1]', i_bin[l[i][j + 1] - 1])

        # print('c', c)

        if c % 2 != p_l[i]:
            flag = False
            break

        # print('flag', flag)

    if flag:
        ans += 1

    # print('ans', ans)
print(ans)

Submission status: Accepted

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


def dfs(x, s):
    global ans
    if x == n:
        for j in range(m):
            switchs = ls[j]
            cond = p[j]
            on_cnt = 0
            for switch in switchs:
                if int(s[switch]):
                    on_cnt += 1
            if on_cnt % 2 != cond:
                break
        else:
            ans += 1
    else:
        for c in "01":
            dfs(x+1, s+c)


dfs(0, "")
print(ans)

Submission status: Accepted

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

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

ans = 0
for i in range(2**n):
    i = bin(i)[2:].zfill(n)
    for k, si in enumerate(s):
        on_n = 0
        for sik in si:
            on_n += int(i[sik - 1])
        if on_n % 2 != p[k]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n, m = map(int, input().split())
ls = []
for _ in range(m):
    k, *s, = map(lambda x: int(x)-1, input().split())
    ls.append(s)
p = list(map(int, input().split()))
it = ["01"]*n

ans = 0
for b in product(*it):
    base_2 = "".join(b)
    for j in range(m):
        switchs = ls[j]
        cond = p[j]
        on_cnt = 0
        for switch in switchs:
            if int(base_2[switch]):
                on_cnt += 1
        if on_cnt % 2 != cond:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

ans =0
for i in range(2 ** n):
    ok = True
    for j,k in zip(ss,p):
        l = 0
        for m in j:
            if (2 ** m) & i != 0:
                l += 1
        if l % 2 != k:
            ok = False


    if ok:
        ans += 1
print(ans)