Problem:


Score : 300 points

Problem Statement

We have N switches with "on" and "off" state, and M bulbs. The switches are numbered 1 to N, and the bulbs are numbered 1 to M.

Bulb i is connected to k_i switches: Switch s_{i1}, s_{i2}, ..., and s_{ik_i}. It is lighted when the number of switches that are "on" among these switches is congruent to p_i modulo 2.

How many combinations of "on" and "off" states of the switches light all the bulbs?

Constraints

1 \leq N, M \leq 10

1 \leq k_i \leq N

1 \leq s_{ij} \leq N

s_{ia} \neq s_{ib} (a \neq b)

p_i is 0 or 1.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
k_1 s_{11} s_{12} ... s_{1k_1}
:
k_M s_{M1} s_{M2} ... s_{Mk_M}
p_1 p_2 ... p_M

Output

Print the number of combinations of "on" and "off" states of the switches that light all the bulbs.

Sample Input 1

2 2
2 1 2
1 2
0 1

Sample Output 1

1

Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.

Bulb 2 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

There are four possible combinations of states of (Switch 1, Switch 2): (on, on), (on, off), (off, on) and (off, off). Among them, only (on, on) lights all the bulbs, so we should print 1.

Sample Input 2

2 3
2 1 2
1 1
1 2
0 0 1

Sample Output 2

0

Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.

Bulb 2 is lighted when there is an even number of switches that are "on" among the following: Switch 1.

Bulb 3 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

Switch 1 has to be "off" to light Bulb 2 and Switch 2 has to be "on" to light Bulb 3, but then Bulb 1 will not be lighted. Thus, there are no combinations of states of the switches that light all the bulbs, so we should print 0.

Sample Input 3

5 2
3 1 2 5
2 2 3
1 0

Sample Output 3

8



Sample input:
2 2
2 1 2
1 2
0 1


Sample output:
1

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from functools import reduce

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

t = [reduce(lambda x, y: x | (1 << (y - 1)), e, 0) for e in s]
result = 0
for i in range(2 ** N):
    for j in range(M):
        if (bin(i & t[j]).count('1') & 1) != p[j]:
            break
    else:
        result += 1
print(result)

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 = [0]*N
    
    for j in range(N):
        if (i>>j & 1):
            switch[j] = 1
    
    n_on_light = 0
    
    for x in range(M):
        n_on_switch_for_one_light = 0
        for k in range(ks[x][0]):
            n_on_switch_for_one_light += switch[ks[x][k+1]-1]
        if n_on_switch_for_one_light%2 == p[x]:
            n_on_light += 1
    
    if n_on_light == M:
        ans += 1
    
print(ans)

Submission status: Accepted

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

ans = 0

for i in range(2**N):
    light = [0]*M #ライトがすべて光っているか判定
    for j in range(M):
        on = 0 #ライトに接続しているonのスイッチの数
        for k in K[j]: #各ライトに接続しているスイッチk
            if (i>>(k-1))&1: #スイッチのon/offを確認
                on += 1
        if on%2 == P[j]: #onスイッチ数%2が点灯の条件と一致しているか確認
            light[j] = True
    if all(light): #全てのライトが点灯しているか確認
        ans += 1
print(ans)

Submission status: Accepted

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

s=[[0 for i in range(N)] for j in range(M)]

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

    k=tmp[0]
    for j in range(k):
        s[i][tmp[j+1]-1]=1

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

out=0

for i in range(2**N):
    b=list(map(int,list(bin(i))[2:]))
    b=[0 for j in range((N-len(b)))]+b
    ss=1
    for j in range(M):
        t=0
        for k in range(N):
            if b[k]==1 and s[j][k]==1:
                t+=1
        if t%2!=p[j]:
            ss=0
    if ss==1:
        out+=1

print(out)

Submission status: Accepted

Solution code:

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

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

a = []
for i in range(2 ** N):
    i_bin = bin(i)
    a.append(i_bin[2:].zfill(N))

c = 0
for ai in a:
    # print('ai:', ai)
    r = True
    for i, si in enumerate(S):
        x = 0
        for sii in si:
            # print('x', si, sii)
            x += int(ai[sii-1])
        if x % 2 != P[i]:
            r = False
    if r:
        c += 1

print(c)

Submission status: Accepted

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

r=[list(map(int,input().split()))[1:]for i in range(m)]
*p,=map(int,input().split())
ans=0
for i in range(2**n):
    lamp=array([i>>j&1for j in range(n)])
    ans+= p==[sum(lamp[array(j)-1])%2 for j in r]
print(ans)

Submission status: Accepted

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


def is_on(s, x, p):
    parity = 0
    for i in s:
        parity += (x >> (i-1)) & 1
    return parity % 2 == p


ans = 0
for i in range(int(math.pow(2, n))):
    on = 1
    for j in range(m):
        if not is_on(s[j], i, p[j]):
            on = 0
            break
    ans += on
print(ans)

Submission status: Accepted

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

n,m = map(int, input().split())
ks = [ list(map(int,input().split())) for _ in range(m) ]
p = list(map(int,input().split()))
# print(n)
# print(m)
# print(ks)
# print(p)

# print(len(ks))
x = [ len(c) for c in ks ]
# print(x)

count = 0
for i in range(2**n):
    b = bin(i)
    b = list(b)
    b = b[2:]
    b = list(map(int,b))
    swich_list = [0]*(n - len(b))
    c = swich_list + b
    c.reverse()
    # print(c)

    lamp_list = [0]*m
    for j in range(m):
        s = 0
        for k in ks[j][1:]:
            # print(k)
            s += c[k-1]

        if s%2==p[j]:
            lamp_list[j] = 1

    if sum(lamp_list)==m:
        count += 1

print(count)

Submission status: Accepted

Solution code:
def resolve():
    # n switches, m bulbs
    n, m = map(int, input().split())
    s = list(list(map(int, input().split()))[1:] for _ in range(m))
    p = list(map(int, input().split()))
    print(sum([1 for i in range(1 << n) if all([sum([1 for sji in sj if i & (1 << (sji - 1))]) % 2 == pj for sj, pj in zip(s, p)])]))


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def resolve():
    # n switches, m bulbs
    n, m = map(int, input().split())
    s = list(list(map(int, input().split()))[1:] for _ in range(m))
    p = list(map(int, input().split()))
    ok = 0
    for i in range(1 << n):
        lights = [False] * m
        for j in range(m):
            on = 0
            for sji in s[j]:
                # if (i >> (sji - 1)) & 1:
                if i & (1 << (sji - 1)):
                    on += 1
            if on % 2 == p[j]:
                lights[j] = True
        if all(lights):
            ok += 1
    print(ok)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

count = 0
for i in range(2 ** n):
    res = 0
    for kc, pc in zip(k, p):
        s = sum([(i >> (j-1)) & 1 for j in kc]) % 2
        res += s == pc
    count += res == len(p)
print(count)

Submission status: Accepted

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

table = []
for i in range(n):
    row = []
    for j in range(2 ** i):
        row += [1] * (2 ** (n-i) // 2) + [0] * (2 ** (n-i) // 2)
    table.append(row)

count = 0
for j in range(len(table[0])):
    res = 0
    for i, item in enumerate(k):
        if sum([table[n-1][j] for n in item]) % 2 == p[i]:
            res += 1
    if res == len(p):
        count += 1

print(count)

Submission status: Accepted

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

ans=0

for i in range(2**N):
  lamp=[0]*M
  for j in range(len(bin(i))-2):
    if (i>>j)&1==1:
      for k in range(M):
        if j+1 in ks[k]:
          lamp[k]+=1
  ja=0
  for j in range(M):
    if lamp[j]%2!=p[j]:
      ja+=1
  if ja==0:
    ans+=1
    
    
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def countMatchedSwitch(sw_status, switch, index):
    ret = 0
    for s in switch[index]:
        if int(sw_status[int(s) - 1]) == 1:
            ret += 1
    return ret % 2


if __name__ == '__main__':
    N, M = [int(i) for i in input().split()]
    s = []
    for i in range(int(M)):
        data = input().split()
        s.append(data[1:])
    p = [int(i) for i in input().split()]

    ret = 0
    for i in range(2**N):
        is_all_passed = True
        sw_status = bin(i)[2:].zfill(N)
        for j in range(M):
            if p[j] != countMatchedSwitch(sw_status, s, j):
                is_all_passed = False
        if is_all_passed:
            ret += 1
    print("{ret}".format(ret=ret))

Submission status: Accepted

Solution code:
N , M = map(int , input().split())
switch = []
bit_switch = []
for _ in range(M):
    switch = list(map(int ,input().split()))
    del switch[0]
    k = 0
    for i in switch:
        k += 1 << (i - 1)
    bit_switch.append(k)
p = list(map(int,input().split()))
cnt = 0
dp = [[] for _ in range(M + 1)]
dp[0] = [i for i in range(2 ** N)]
#print(bit_switch)
#print(dp)
for i in range(M):
    for j in dp[i]:
        if str(bin(j & bit_switch[i])).count('1')% 2 == p[i]:
            dp[i + 1].append(j)
#print(dp)
print(len(dp[M]))

Submission status: Accepted

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


#print(format(n,'b'))
#print(format(n,'b').zfill(n))
#print(format(n,'b').zfill(n)[1])
ans=0
for i in range(2**n):
	nn=format(i,"b")
	nnn=nn.zfill(n)	
	temp2=0
	for j in range(m):
		temp=0
		for k in range(lists[j][0]):
			ss=lists[j][k+1]
			temp=temp+int(nnn[ss-1])
		if temp%2==listp[j]:
			temp2=temp2+1
	if temp2==m:
		ans=ans+1
			
print(ans)

Submission status: Accepted

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

data = []
for _ in range(m):
    lista = [int(i) for i in input().split()]
    data.append(lista)
    
listp = [int(i) for i in input().split()]

testnum = 2**n
ans = 0
for i in range(testnum):
    checklist = [0]*n
    tmpi = i
    for j in range(n):
        if tmpi>=2**(n-1-j):
            checklist[j]=1
            tmpi -= 2**(n-1-j)
    #print("clist",checklist)
    succ = True
    for j in range(m):
        sumnum = 0
        for jj in range(1,len(data[j])):
            sumnum += checklist[data[j][jj]-1]
        if sumnum%2 != listp[j]:
            succ = False
            break
    if succ==True:
        ans +=1
        
print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

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

swt=[]
for i in range(M):
    lis=list(map(int,input().split()))
    swt.append(lis)
p=list(map(int,input().split()))
li=list(range(1,N+1))
combi=[]
for i in range(N+1):
    combi.extend(combinations(li,i))

ans=0
for s in combi:
    f=True
    for i in range(M):
        temp=0
        for j in range(1,swt[i][0]+1):
            if  swt[i][j] in s:
                temp+=1
        if not temp%2==p[i]:
            f=False
            break
    if f:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = []
for _ in range(M):
    k, *s = map(int, input().split())
    S.append(s)
p = list(map(int, input().split()))
ans = 0
for i in range(2 ** N):
    check = [0 for _ in range(N)]
    tmp = i
    flg = True
    for j in range(N):
        check[j] = tmp % 2
        tmp //= 2
    for l, s in enumerate(S):
        cnt = 0
        for k in s:
            cnt += check[k - 1]
        if cnt % 2 != p[l]:
            flg = False
    if flg:
        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()))
count = 0


def dfs(i, switch):
    if i == n:
        # check
        light_on_flag = True
        for a in range(m):
            switch_on_count = 0
            for b in range(ks[a][0]):
                if switch[ks[a][b + 1] - 1]:
                    switch_on_count += 1
            if not switch_on_count % 2 == p[a]:
                light_on_flag = False
                break
        if light_on_flag:
            global count
            count += 1
        return

    switch[i] = True
    dfs(i + 1, switch)
    switch[i] = False
    dfs(i + 1, switch)


switch = [False] * n
dfs(0, switch)
print(count)

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    s = [[int(i) for i in input()[2:].split()] for j in range(M)]
    p = [int(i) for i in input().split()]
    ans = 0
    for bit in range(1<<N):
        switches = [0] * N
        for i in range(N):
            if bit & (1<<i):
                switches[i] = 1
        for ss,pp in zip(s,p):
            tmp = 0
            for i in ss:
                if switches[i-1]:
                    tmp += 1
            if tmp%2 != pp:
                break
        else:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
n,m = map(int,input().split())
lamp = [[]for _ in range(m) ]
for i in range(m):
    s= list(map(lambda x:int(x)-1,input().split()))
    lamp[i] = s[1:]
mod = list(map(int,input().split()))

swiches = [[0 for _ in range(n)]]
for i in range(n):
    swiches2 =[]
    for swich in swiches:
        swiches2.append(swich)
        swich2 = copy.copy(swich)
        swich2[i] = 1
        swiches2.append(swich2)
    swiches = swiches2
ans = 0
for switch in swiches:
    for i,lampi in enumerate(lamp):
        sw_on = 0
        for j in lampi:
            sw_on += switch[j]
        if sw_on%2!=mod[i]:
            break
        else:
            if i==m-1:
                ans +=1
print(ans)

Submission status: Accepted

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

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

dp = [[] for _ in range(m+1)]
dp[0] = [i for i in range(2**n)]
for i in range(m):
  for j in dp[i]:
    if str(bin(j & S[i])).count('1')%2==p[i]:
      dp[i+1].append(j)
      
print(len(dp[m]))

Submission status: Accepted

Solution code:
def count1(x):
    global N
    return sum([(x&(1<<t))>>t for t in range(N)])

def check(k):
    global M,s,p
    for j in range(M):
        if (count1(k&s[j])-p[j])%2!=0:
            return False
    return True

N,M=map(int,input().split())
s=[]
for j in range(M):
    l=list(map(int,input().split()))
    A=sum([1<<(x-1) for x in l[1:]])
    s.append(A)
p=list(map(int,input().split()))

ans=0
for k in range(1<<N):
    if check(k):
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = [[int(i) for i in input().split()] for j in range(M)]
p = [int(i) for i in input().split()]
ans = 0
#print(S)
for i in range(2 ** N):
  T = [0] * N
  for j in range(N):
    if ((i >> j) & 1):
      T[j] += 1

  s = 0
  for j in range(M):
    pp = 0
    for k in range(S[j][0]):
      pp += T[S[j][k+1]-1]
    if pp % 2 == p[j]:
      s += 1
      #print(pp, p[j])
  if s == M:
    #print(T)
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,M = map(int, input().split())
    RAMPS = [0]*M
    for i in range(M):
        tmp = list(map(int, input().split()))
        RAMPS[i] = [x-1 for x in tmp[1:]]
    PS = list(map(int, input().split()))
    ans = 0
    for bit in range(2**N):
        for i in range(M):
            cnt = 0
            for j in RAMPS[i]:
                if 1<<j & bit != 0: cnt += 1
            if cnt%2 != PS[i]:
                break
        else:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

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()))
count = 0
for i in range(2 ** n):
    check = True
    bin_str = format(i, 'b').rjust(n + 1, "0")
    for j in range(m):
        light = 0
        for k in range(1, len(l[j])):
            if bin_str[l[j][k]] == "1":
                light += 1
        if not (light % 2 == p[j]):
            check = False
    if check:
        count += 1
print(count)

Submission status: Accepted

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

ans=0

for st in product([0,1],repeat=N):
    f=True
    for i in range(M):
        k=0
        for j in A[i]:
            k+=st[j-1]
        f= k%2==P[i]
        if not f:
            break
    if f:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    N, M = map(int, input().split())
    ksl = list()
    for _ in range(M):
        ksl.append(list(map(int, input().split())))
    p = list(map(int, input().split()))

    ans = 0
    for i in range(2 ** N):
        flag = str(format(i, 'b').zfill(N))
        flag = flag[::-1]
        is_Lightup = True
        for j in range(M):
            count = 0
            for k in range(ksl[j][0]):
                count += int(flag[ksl[j][k+1] - 1])
            if count % 2 != p[j]:
                is_Lightup = False
                break
        if is_Lightup:
            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()))
ans = 0
tmp = 0
for i in range(2**N):
    Judge = True
    for j in range(0,M):
        tmp = 0
        for k in range(1,KS[j][0]+1):
            if i >> (KS[j][k]-1) & 1 == 1:
                tmp += 1
        if tmp%2 != P[j]:
            Judge = False
    if Judge:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

bulb = {}
for i in range(1, m+1):
    k_s = list(map(int, input().split()))
    bulb[i] = k_s[1:]

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

count = 0
for item in product([0, 1], repeat=n):
    on = [ind+1 for ind, status in enumerate(item) if status]
    for k, v in bulb.items():
        if p[k-1] != len(set(v).intersection(set(on))) % 2:
            break
    else:
        count += 1

print(count)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0

for state in product([0,1],repeat=N):
  f = True
  for i in range(M):
    tmp = 0
    for s in sw[i]:
      tmp += state[s-1]
    f = tmp % 2 == p[i]
    if not f:
      break
  if f:
    ans += 1
print(ans)

Submission status: Accepted

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

Slist=[]
for i in range(pow(2,N)):
    # print(format(i,'0'+str(N)+'b'))
    Slist.append(format(i,'0'+str(N)+'b'))

#print(Slist)
ans = 0
for onoff in Slist:
    cnt=0
    for i in range(len(S)):
        tmp=0
        for chk in S[i]:
            #print(chk)
            if onoff[chk-1]=='1':
                tmp+=1
        if tmp%2 == P[i]:
            cnt+=1
    if cnt == M:
        ans+=1
print(ans)

Submission status: Accepted

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

def hoge(s,N,ans):
    if sum(s)==N:
        print(ans)
        exit(0)
    for i in range(N-1,-1,-1):
        if s[i]==0:
            s[i]=1
            break
        else:
            s[i]=0
    return s

for i in range(2**N):
    for i in range(M):
        tmp=0
        for k in li[i][1::]:
            if s[k-1]==1:
                tmp+=1
        if tmp%2!=p[i]:
            break
    else:
        ans+=1
    s=hoge(s,N,ans)

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()))
#print(S)
#print(P)

ans=0
for i in range(2**N):
  #print(bin(i))
  p=[]
  for s in S:
    tmp=0
    for ss in s:
      if i>>(N-ss)&1:
        tmp+=1
    p.append(tmp%2)
  if p==P:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
S = [0] * M
k = [0] * M
for i in range(M):
    KS = list(map(int,input().split()))
    k[i] = KS[0]
    S[i] = KS[1:] #1から最後までの書き方
P = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    global_count = 0
    for j in range(M):
        local_count = 0
        for x in S[j]:
            if (i >> (x-1)) % 2 == 0:
                continue
            else:
                local_count += 1
        if local_count % 2 == P[j]:
            global_count += 1
    if global_count == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools as it

N, M = list(map(int, input().split()))
s = []
for i in range(M):
    s_i = [int(a) for a in input().split()]
    s.append(s_i[1:])
p = [int(a) for a in input().split()]
ans = 0
for i in it.product(range(2), repeat=N):
    # each configuration of switches
    is_flash = []
    for j in range(M):
        # each flash condition
        cond = s[j]  # [1, 2]...
        num = 0
        for light in cond:
            num += i[light - 1]
        if num % 2 == p[j]:
            is_flash.append(True)
        else:
            is_flash.append(False)
    if all(is_flash):
        ans += 1
print(ans)

Submission status: Accepted

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

p = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    global_count = 0
    for j in range(M):
        local_count = 0
        for x in s[j]:
            if (i >> (x - 1)) % 2 == 0:
                continue
            else:
                local_count += 1
        if local_count % 2 == p[j]:
            global_count += 1
    if global_count == M:
        ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1<<N):#すいっちのくみあわせ
  for j in range(M):#でんきゅうをみてく
    rel=0
    for k in swis[j]:
      if i & (1<<(k-1)) != 0:
        rel+=1
        
    if rel%2 != need[j]:
        break
  else:
     ans+=1
      
print(ans)

Submission status: Accepted

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

Slist=[]
for i in range(pow(2,N)):
    #print(format(i,'0'+str(N)+'b'))
    Slist.append(format(i,'0'+str(N)+'b'))

#print(Slist)
ans = 0
for onoff in Slist:
    cnt=0
    for i in range(len(S)):
        tmp=0
        for chk in S[i]:
            #print(chk)
            if onoff[chk-1]=='1':
                tmp+=1
        if tmp%2 == P[i]:
            cnt+=1
    if cnt == M:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
N, M = map(int, input().split())

switches = []
for i in range(M):
    temp = list(map(int, input().split()))
    temp = [val-1 for val in temp]
    switches.append(set(temp[1:]))

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

def dfs(s):
    if len(s) == N:
        on = set([])
        for i, num in enumerate(s):
            if num == "1":
                on.add(i)

        for switch, p in zip(switches, ps):
            common = switch & on
            if len(common) % 2 != p:
                return 0
                break
        else:
            return 1
    else:
        return dfs(s + "0") + dfs(s + "1")

ans = dfs("")
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
target = [[num-1 for num in list(map(int,input().split()))[1:]] for _ in range(M)]
judge = list(map(int,input().split()))
cnt = 0

for i in range(2**N):
  switches = [0]*M
  for k in range(M):
    for j in range(N):
      if ((i>>j)&1) and j in target[k]:
        switches[k] += 1
  switches =  [switch%2 for switch in switches]
  if switches == judge:
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# 2019/09/22

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

res=0
for i in range(2**n):
    flag=True
    for j in range(m):
        cnt=0
        for e in s[j]:
            if i>>e&1:
                cnt+=1

        if cnt%2!=p[j]:
            flag=False
            break
    if flag:res+=1
print(res)

Submission status: Accepted

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


def main():
    N, M = map(int, input().split())
    K = []
    S = [[False]*N for _ in range(M)]
    for i in range(M):
        L = list(map(int, input().split()))
        K.append(L[:1])
        for l in L[1:]:
            S[i][l-1] = True
    P = list(map(int, input().split()))
    # for s in S:
    #         print(s)

    ans = 0
    for i in range(2**N):
        C = [0]*M
        for j in range(N):
            if (i>>j) & 1:
                for k in range(M):
                    if S[k][j]:
                        C[k] += 1
        flg = True
        for j in range(M):
            if C[j]%2!=P[j]:
                flg = False
        if flg:
            ans += 1
        # print(C)
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

l=[[int(x) for x in input().split()] for _ in range(m)]
p=[int(x) for x in input().split()]

t=0
for i in range(2**n):
  f = True
  for j in range(m):
     c=0
     for k in range(1,l[j][0]+1):
       if (i>>(l[j][k]-1)) & 1:
         c+=1
     if (c&1)!=p[j]:
        f = False
        break
  if f==True:
    t+=1

print(t)

Submission status: Accepted

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

a = [0] * N

# 各スイッチがどの電球に繋がっているか
for i in range(M):
    l = list(map(int, input().split()))
    k = l[0]
    S = l[1:]
    for j in range(k):
        s = S[j]
        s -= 1
        # s番目のスイッチにi番目の電球が繋がっている
        a[s] |= 1 << i

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

ans = 0
# スイッチの押し方全通り
for s in range(1 << N):
    t = 0
    for i in range(N):
        # iビット目が立っているか
        if s >> i & 1:
            # スイッチを押して、つながった電球の状態を反転させる
            t ^= a[i]
    # 各スイッチを押した後の電球の状態が理想と一致するか
    if t == p:
        ans += 1

print(ans)

Submission status: Accepted

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

a = [0] * N

# 各スイッチがどの電球に繋がっているか
for i in range(M):
    l = list(map(int, input().split()))
    k = l[0]
    S = l[1:]
    for j in range(k):
        s = S[j]
        s -= 1
        # s番目のスイッチにi番目の電球が繋がっている
        a[s] |= 1 << i

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

ans = 0
# スイッチの押し方全通り
for s in range(1 << N):
    t = 0
    for i in range(N):
        # iビット目が立っているか
        if s >> i & 1:
            t ^= a[i]
    if t == p:
        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()))

ans = 0
for i in range(2**N):
    status = [0] * N
    for j in range(N):
        if i >> j & 1:
            status[N - 1 - j] = 1

    possible = True
    for j in range(M):
        cnt_sw = sum(1 if status[k-1] == 1 else 0 for k in KS[j][1:])
        if cnt_sw%2 != P[j]:
            possible = False
    if possible:
        ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
# ABC128 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):
    i = format(i, "b").zfill(n)
    for j in range(len(s)):
        tmp = 0
        for k in s[j][1:]:
            tmp += int(i[k - 1])
		
        if p[j] != tmp % 2:
            break
        if j == len(s) - 1:
            ans += 1

print(ans)

Submission status: Accepted

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

ans = 0

for i in range(2**n):
    i = format(i, "b").zfill(n)
    for j in range(len(s)):
        tmp = 0
        for k in s[j][1:]:
            tmp += int(i[k - 1])
		
        if p[j] != tmp % 2:
            break
        if j == len(s) - 1:
            ans += 1

print(ans)

Submission status: Accepted

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

ans = 0

for i in range(2**n):
    i = format(i, "b").zfill(n)
    for j in range(len(s)):
        tmp = 0
        for k in s[j][1:]:
            tmp += int(i[k - 1])

        if p[j] != tmp % 2:
            break
        if j == len(s) - 1:
            ans += 1

print(ans)

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

s_cands = [[]]
for i in range(1, n+1):
  temp = []
  for cand in s_cands:
    temp.append(cand + [i])
    temp.append(cand)
  s_cands = temp

correct_pat = 0
for light_pat in s_cands:
  for i, s in enumerate(S):
    swicth_on = len(list(set(light_pat) & set(s)))
    if swicth_on % 2 != P[i]:
      break
  else:
    correct_pat += 1
print(correct_pat)