Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N, M \leq 10

1 \leq k_i \leq N

1 \leq s_{ij} \leq N

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

p_i is 0 or 1.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 2
2 1 2
1 2
0 1

Sample Output 1

1

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

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

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

Sample Input 2

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

Sample Output 2

0

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

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

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

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

Sample Input 3

5 2
3 1 2 5
2 2 3
1 0

Sample Output 3

8



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


Sample output:
1

Submission status: Accepted

Solution code:
N, M=map(int, input().split())
ks=[]
for _ in range(M):
    k,*s=input().split()
    ks.append((k, list(map(int, s))))
P=list(map(int, input().split()))

def judge():
    ans=0
    for switches in range(0, 2**N):
        b=bin(switches)[2:].zfill(N)

        for i in range(M):
            s=ks[i][1]
            p=P[i]
            on=0
            for j in s:
                if b[j-1]=="1":
                    on+=1
            if on%2!=p:
                break
        else:
            ans+=1
    return ans
        
print(judge())

Submission status: Accepted

Solution code:
import os,re,sys,operator
from collections import Counter,deque
from operator import itemgetter
from itertools import accumulate,combinations,groupby
from sys import stdin,setrecursionlimit
from copy import deepcopy
import heapq

setrecursionlimit(10**6)

n,m=map(int,stdin.readline().rstrip().split())
s=[list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
c=[]
ans=0
for i in s:
    c.append(i[0])
    i.pop(0)
p=[int(i) for i in stdin.readline().rstrip().split()]
cnt=0
for i in range(2**n):
    ch=True
    r=bin(i)[2:].zfill(n)[::-1]
    for j in range(m):
        cnt=0
        for k in range(c[j]):
            if r[s[j][k]-1]=="1":
                cnt+=1
        if cnt%2!=p[j]:
            ch=False
            break
    if ch:
        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()))

ans = 0

#それぞれのスイッチの状態について検証を行う
for i in product(range(2), repeat=N):
    cnt = 0
    #電灯ごとの点滅を調べる
    for j in range(M):
        cnt_p = 0
        for k in ks[j][1:]:
            cnt_p += i[k-1]
        if cnt_p %2 == p[j]:
            cnt += 1
        else:
            break
    #全てつくならansに+1
    if cnt == M:
        ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
for pat in range(2**N):
    flag = True
    for sw in range(M):
        count = 0
        for x in slist[sw]:
            #print( "pat ={} x-1 ={} ans ={}".format( pat,x-1,(pat >> (x-1)) & 1))
            if ( (pat >> (x-1)) & 1 ) == 1:
                count += 1
        if count % 2 != plist[ sw ]:
            flag = False
            break
            
    if flag == True:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
S = [list(map(int, input().split())) for i in range(M)]
p= list(map(int, input().split()))
l=list(itertools.product([0,1],repeat=N))
a=0
for i in range(len(l)):
    for j in range(M):
        c=0
        for k in range(S[j][0]):
            c+=l[i][S[j][k+1]-1]
        if c%2!=p[j]:
            break
    else:a+=1
print(a)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
switch={}
for i in range(n):
  switch[i]=[]
for light in range(m):
  s=list(map(int,input().split()))
  for i in s[1:]:
    switch[i-1].append(light)
p=list(map(int,input().split()))

count=0
for i in range(2**n):
  judge=[0]*m
  for k in range(n):
    if i&(2**k):
      for x in switch[k]:
        judge[x]=1-judge[x]
  if judge==p:
    count+=1
print(count)

Submission status: Accepted

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

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

    # all possible switch patterns
    for i in range(2 ** N):
        light_on = 0
        # all switch conditions
        for j in range(M):
            switch_on = 0
            # all connected switch
            for k in S[j][1:]:
                # convert integer to binary
                if (i >> k-1) & 1:
                    switch_on += 1
            if switch_on %2 == P[j]:
                light_on += 1
        if light_on == M:
            ans += 1

    return ans

if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
switches = []
cnt = 0

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

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


def ch_binary(l, digit):
    num = [0] * digit
    for i in l:
        num[i-1] = 1
    return num

#スイッチのON、OFFをバイナリで表現する。
switches_2 = []
for i in switches:
    array = ch_binary(i, n)
    switches_2.append(array)



def check(a, b, digit, x):
    count = 0
    for i in range(digit):
        if a[i] == b[i] and b[i] == 1:
            count += 1
    if count % 2 == x:
        return 1
    else:
        return 0


for i in range(2**n):
    bin_str = list(map(int, format(i, 'b').zfill(n)))
    count = 0
    for j in range(m):
        y = check(switches_2[j], bin_str, n, p[j])
        count += y
    if count == m:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
#25 ABC128C
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):
	t=bin(i+2**n)[3:]
	judge=True
	for j in range(m):
		l=0
		for k in ks[j][1:]:
			if t[k-1]=="1":
				l+=1
		if l%2==p[j]:
			continue
		else:
			judge=False
			break
	if judge:
		res+=1
print(res)

Submission status: Accepted

Solution code:
import numpy as np

N, M = map(int, input().split())
lst = [list(map(int, input().split())) for s in range(M)]
P = list(map(int, input().split()))

all_lst = []
for x in lst:

    b = [0] * N
    for i in x[1:]:
        b[i - 1] = 1

    all_lst.append(b)

cnt = 0
for v in range(2 ** N):
    v = bin(v)[2:]

    b = [0] * N
    for i, n in enumerate(v[::-1]):
        if n == '1':
            b[i] = 1

    b = np.array(b)

    found = True
    for i, tar in enumerate(all_lst):
        p = np.sum(b * np.array(tar)) % 2

        if P[i] != p:
            found = False
            break

    if found:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys,math
kk = []
tmp = []
s = []
ans = 0
N,M = map(int,input().split())
for i in range(M):
    k,*t = list(map(int,input().split()))
    s.append(t)
    kk.append(k)
p = [int(i) for i in input().split()]
for i in range(2**N):
    flag = 0
    si = [0] * N
    for j in range(N):
        if (i>>j) & 1:
            si[j] += 1
    for x in range(M):
        tt = 0
        for y in range(kk[x]):
            tt += si[s[x][y]-1] 
        if tt % 2 == p[x]:
            flag += 1
    if flag == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ls=[]
for i in range(m):
    lsin=list(map(int,input().split()))
    del lsin[0]
    ls.append(lsin)
lp=list(map(int,input().split()))
sans=0
for i in range(2**n):#switch pattern
    q=0
    for j in range(m):#for bulb
        non=0#onの個数
        for s in ls[j]:
            #non+=i%(2**(s-1))
            #non+=(i//2**(s-1))%2
            non+=((2**(s-1))&i )/(2**(s-1))#これでも良い
        #print("non",i,non)
        if non%2!=lp[j]:
            q=1
            break
    if q==0:
        #print("ok",i)
        sans+=1
print(sans)
#for i in range(2):
#    pass
#print(i)
#print(ls)
#print(lp)

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

P = 0
for i in range(m):
    if p[i] == 1:
        P += 2**(m-i-1)
    
sum = 0
isAffectedSwitch=[[False for _ in range(n)] for _ in range(m)]
for i in range(m):
    for j in range(1,s[i][0]+1):
        isAffectedSwitch[i][s[i][j]-1]=True

C = []
for i in range(n):
    B = 0
    for j in range(m):
        if isAffectedSwitch[j][i] == True:
            B += 2**(m-j-1)
    C.append(B)

for i in range(2**n):
    A = 0
    for j in range(n):
        if ((i >> j)&1):
            A = A ^ C[j]
           
    if A == P:
        sum += 1
        
print(sum)

Submission status: Accepted

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

p = list(map(int, input().split(" ")))
ans = 0
for tup in product(range(2), repeat=N):
    for i in range(M):
        flg = True
        cnt = 0
        for d in s[i]:
            cnt += tup[d - 1]
        if cnt % 2 != p[i]:
            flg = False
            break

    if flg:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
def resolve():
    n,m = map(int,input().split())
    ss = []
    for i in range(m):
        k, *s = map(int, input().split())
        ss.append(s)
    p = list(map(int,input().split()))
    ans = 0
    for s_pattern in itertools.product(range(0,2),repeat=n):
        light_bool = []
        for light_num, each_s in enumerate(ss):
            ssum = 0
            for num in each_s: ssum += s_pattern[num-1]
            light_bool.append(ssum % 2 == p[light_num])
        if all(light_bool):
            ans+=1
    print(ans)

resolve()

Submission status: Accepted

Solution code:
import numpy as np
import itertools
def resolve():
    n,m = map(int,input().split()) #スイッチ､電球
    ss = []
    for i in range(m):
        k, *s = map(int, input().split())
        ss.append(s)
    p = list(map(int,input().split()))
    #print()
    #print(n,m)
    #print(ss)
    #print(p)

    #print()
#    for i in range(m):
#        print(len(ss_on[i])%2 == p[i])

#    for i in range():
#        for m in range 
    ans = 0
    # スイッチパターンfor
    for s_pattern in itertools.product(range(0,2),repeat=n):
       # 各ライトfor 番号､構成スイッチ
        light_bool = []
        for light_num, each_s in enumerate(ss):
            ssum = 0
            for num in each_s: ssum += s_pattern[num-1]
            light_bool.append(ssum % 2 == p[light_num])
            #print(s_pattern)
            #print(each_s,ssum)
            #print(p)
        #print(light_bool)
        if all(light_bool):
            ans+=1
    print(ans)
            #if sum(l)%2 == 
    

resolve()

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int, input().split())
ls = deque()
k = deque()
for m in range(M):
    ls.append(deque(map(int, input().split())))
    ls[m].popleft()
p = list(map(int, input().split()))
ans = 0
for i in range (2**N):
    x = str(bin(i))
    x = x[2:]
    f = False
    while len(x) < N:
        x = "0" + x

    for j in range(M):
        tmp = 0

        for k in range(len(ls[j])):
            tmp += int(x[ls[j][k]-1])
        tmp %= 2
        if tmp != p[j]:
            f = True
            break
    if f:
        continue

    ans += 1
print(ans)

Submission status: Accepted

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

output = 0
for h in range(2**n):
    flag = 1
    padding = '0{}b'.format(n)
    bit = format(h, padding)
    for i, v in enumerate(p):
        cnt = 0
        for j in switch[i]:
            if bit[j-1] == '1':
                cnt += 1
        if cnt % 2 != v:
            flag = 0
    if flag == 1:
        output += 1
print(output)

Submission status: Accepted

Solution code:
import itertools
n, m = list(map(int, input().split()))
sss = []
for i in range(m):
  k, *s = list(map(int, input().split()))
  sss.append(s)
ppp = list(map(int, input().split()))
count = 0
for l in itertools.product([0,1], repeat=n):
  l = list(l)
  flag = True
  for i in range(m):
    curr = 0
    for s in sss[i]:
      if l[s-1] == 1:
        curr += 1
    if curr % 2 != ppp[i]:
      flag = False
      break
  if flag == True:
    count += 1

print(count)

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
on_off = [0]*n
checker = [0]*m
for i in range(2**n):
    for j in range(n):
        if on_off[j] == 1:
            on_off[j] = 0
        else:
            on_off[j] = 1
            break
    slider = [1]*m
    for j in range(m):
        checker[j] = p[j]
    for j in range(1,n+1):
        for k in range(m):
            for l in range(1,ks[k][0]+1):
                if ks[k][l] == j and on_off[j-1] == 1:
                        checker[k] = 1 - checker[k]
    for j in range(m):
        if checker[j] == 1:
            break
        elif j == m-1:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
#128
n, m = list(map(int, input().split(' ')))
k = []
for i in range(m):
    k.append([int(x) for x in input().split(' ')])
p = [int(x) for x in input().split(' ')]
count = 0
for i in range(2**n):
    #sw_p is str
    sw_p = format(i,'0{}b'.format(n))
    hantei = True
    for j in range(m):
        sum_s = [int(sw_p[x-1]) for x in k[j][1:]]
        if sum(sum_s)%2 == p[j]:
            continue
        else:
            hantei = False
            break
    if hantei == True:
        count += 1
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[]
for _ in range(m):_,*t=map(int,input().split());s.append(t)
*p,=map(int,input().split())
print(sum([all([sum([i>>(u-1)for u in s[j]])%2==p[j]for j in range(m)])for i in range(2**n)]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import combinations


def combinations_full_search(n, zero_set=False):
    if zero_set:
        yield tuple()

    for i in range(1, n + 1):
        for pt in combinations(range(n), i):
            yield pt


N, M = [int(v) for v in input().split()]

S = [[int(v) - 1 for v in input().split()[1:]] for _ in range(M)]
P = [int(v) for v in input().split()]

res = 0
for pat in combinations_full_search(N, True):
    patset = set(pat)
    cnt = 0
    for i in range(M):
        s = S[i]
        cnt += int(len(patset.intersection(set(s))) % 2 == P[i])
    res += int(cnt == M)
print(res)

Submission status: Accepted

Solution code:
N, M = [int(v) for v in input().split()]

S = []
for i in range(M):
    S.append(set([int(v) for v in input().split()][1:]))
P = [int(v) for v in input().split()]

limit = int('1' * N, 2)
res = 0
for j in range(limit + 1):
    on_idx = set()
    for ki, k in enumerate(list(('{:0' + str(N) + 'b}').format(j))):
        if k == '1':
            on_idx.add(ki+1)

    cnt = 0
    for i in range(M):
        cnt += int(len(S[i].intersection(on_idx)) % 2 == P[i])

    if cnt == M:
        res += 1
print(res)

Submission status: Accepted

Solution code:
switch_num, light_num = list(map(int, input().split()))
switch_list = []
for i in range(light_num):
    switch_list.append(list(map(int, input().split()))[1:])
each_mod = list(map(int, input().split()))
bit_cnt = 0
for each_bit in range(1<<switch_num):
    for i in range(light_num):
        cnt = 0
        for each_switch in switch_list[i]:
            if (1 << (each_switch-1)) & each_bit:
                cnt += 1
        if not cnt & 1 == each_mod[i]:
            break
    else:
        bit_cnt += 1
print(bit_cnt)

Submission status: Accepted

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

N, M = [int(item) for item in input().split()]

k = []
s = []
for i in range(M):
    items = [int(item) for item in input().split()]
    k.append(items[0])
    s.append(items[1:])

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

count = 0

for pat in itertools.product([0, 1], repeat=N):
    for l in range(M):
        ons = sum([pat[item - 1] for item in s[l]])
        if ons % 2 != p[l] % 2:
            break
    else:
        count += 1

print(count)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
K = []
S = []
for i in range(m):
    ks = deque(list(map(int, input().split())))
    K.append(ks.popleft())
    S.append(ks)
P = list(map(int, input().split()))
ans = 0

for i in range(2 ** n):
    flg = False
    for j in range(m):
        count = 0  # j番目の電球に繋がるONスイッチの個数
        
        for k in range(K[j]):
            l = (n - S[j][k])  # 後ろから何番目か
            if ((i >> l) & 1):  # k番目のスイッチフラグがONかどうか(1かどうか)
                count += 1
        if count % 2 != P[j]:
            flg = True
            break  # Offの電球が１個でもある時点でループ抜ける
    if flg:
        continue
    ans += 1

print(ans)

Submission status: Accepted

Solution code:

N,M = map(int,input().split())
s = []
ans = 0

for i in range(M):

    S = list(map(int,input().split()))
    del S[0]

    s.append(S)

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


for i in range(2 ** N):

    now = format( i , "b" )
    now = now.zfill(N)

    lis = [0] * M

    for j in range(M):

        for k in s[j]:

            if now[k-1] == "1":
                lis[j] += 1

    flag = True

    for j in range(M):

        if p[j] != ( lis[j] % 2 ):
            flag = False

    if flag:
        ans += 1

print (ans)

Submission status: Accepted

Solution code:
ks=[]
n,m=map(int,input().split())
for i in range(m):
	ks.append(list(map(int,input().split())))
p=list(map(int,input().split()))
ans_ans=0
for i in range(2**n):
	num="0"*10+bin(i)
	ans=0
	for j in range(m):
		cnt=0
		for k in range(n):
			if num[-k-1]=="1" and k+1 in ks[j][1:]:
				cnt+=1
		if cnt%2==p[j]:
			ans+=1
	if ans==m:
		ans_ans+=1
print(ans_ans)

Submission status: Accepted

Solution code:
#ABC128 C
N, M = (int(_) for _ in input().split())
A = [list(map(int, input().split()))[1:] for _ in range(M)]
P = list(map(int, input().split()))
ans = 0
for i in range(1 << N):
    for j, S in enumerate(A):
        if P[j] ^ sum(i >> k-1 & 1 for k in S) & 1:
            break
    else:
        ans += 1
print(ans)

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

t=[]
for i in range(2**n):
        t.append(format(i,'b').zfill(n))
z=[]
p=p*(2**n)
for i in range(2**n):
        for j in range(len(l)):
                count=0
                for k in range(1,len(l[j])):
                        count+=int((t[i][l[j][k]-1]))
                z.append(count%2)
y=[]
u=[]
ans=0
for i in range(2**n):
        y.append(p[i*m:i*m+m])
        u.append(z[i*m:i*m+m])
        
for l in range(len(y)):
        if y[l]==u[l]:
                ans+=1
print(ans)

Submission status: Accepted

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

linkedSwitch = []

for _ in range(1, M + 1):
    s = list(map(lambda x: int(x) - 1, input().split()))[1:]
    linkedSwitch.append(s)
p = list(map(int, input().split()))


ans = 0

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

    for bulbIndex in range(M):
        onCount = 0

        for switchIndex in linkedSwitch[bulbIndex]:
            onCount += int(switchStatus[switchIndex])

        if onCount % 2 != p[bulbIndex]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n,m=map(int,input().split())
ks=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))

s=np.array([[0]*n for i in range(m)])
for i in range(m):
  for j in range(n):
    if j+1 in ks[i][1:]:
      s[i,j] = 1

cnt=0
for i in range(2**n):
  on_off=np.array(list(map(int,list(bin(i)[2:].zfill(n)))))
  for i in range(m):
    if sum(on_off*s[i])%2!=p[i]:
      break
  else:
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
n,m=map(int,input().split())
ks=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))

s=np.array([[0]*n for i in range(m)])
for i in range(m):
  for j in range(n):
    if j+1 in ks[i][1:]:
      s[i,j] = 1

cnt=0
for i in range(2**n):
  on_off=np.array(list(map(int,list(bin(i)[2:].zfill(n)))))
  flg=0
  for i in range(m):
    if sum(on_off*s[i])%2!=p[i]:
      flg=1
      break
  if flg==0:
    cnt+=1
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
k = []
s = []

for i in range(m):
    temp = list(map(int, input().split()))
    temp_k = temp[0]
    temp_s = temp[1:]
    k.append(temp_k)
    s.append(temp_s)

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

ans = 0
for i in range(2**n):
    on = bin(i)[2:].rjust(n,"0")
    cond = 0
    for j in range(m):
        cnt = sum(list(map(int,[on[k] for k in range(n) if k+1 in s[j]])))
        
        if cnt % 2 == p[j]:
            cond += 1

    if cond == m:
        ans += 1

print(ans)

Submission status: Accepted

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

for i in range(M):
	del X[i][0]

count = 0
for i in range(2**N):
	check = True
	for j in range(M):
		on = 0
		for k in X[j]:
			if (i >> (k-1)) & 1 == 1:
				on += 1
		if on%2 != p[j]:
			check = False
	if check:
		count += 1

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
switch = []
for i in range(m):
    k, *s = map(int, input().split())
    switch.append(s)
mod_val = list(map(int, input().split()))

res = 0
for h in range(0, 1 << n):
    ok = True
    for c in range(m):
        check_mod = 0
        for s in switch[c]:
            if h >> (s - 1) & 1:
                check_mod += 1
        if check_mod % 2 != mod_val[c]:
            ok = False
            break
    if ok:
        res += 1

print(res)

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_on = 0
  for j in range(m):
    switch_on = 0
    for k in ks[j][1:]:
      if (i >> k-1) & 1:
        switch_on += 1
    if switch_on % 2 == p[j]:
      light_on += 1
  if light_on == m:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

N, M = LI()
S = [LI()[1:] for i in range(M)]
ps = LI()

"""
何通りあるか
10までの制限なので、軽い
すべてのスイッチの通りは、2*10=1024通り
それぞれの場合について、最大10個見ればいいのでかんたん

"""
ans = 0
def dfs(sidx, switches):
    global ans
    # onの場合とoffの場合を検証していく
    if sidx == N:
        # 全スイッチの状態を決定できたので、判定する
        #  print('swi' , switches)
        for sidx, s in enumerate(S):
            # sはスイッチのリスト
            v = sum([switches[i-1] for i in s]) % 2
            if v == ps[sidx]:
                # ついてる
                pass
            else:
                # ついてないので止める
                return
        else:
            ans += 1
    else:
        dfs(sidx+1, switches + [0])
        dfs(sidx+1, switches + [1])
dfs(0, [])
print(ans)

Submission status: Accepted

Solution code:
N, M = [int(x) for x in input().split(" ")]
s = []
for i in range(M):
    s.append([int(x) - 1 for x in input().split(" ")][1:])
p = [int(x) for x in input().split(" ")]

# sw_patterns = []
count = 0
for i in range(2 ** N):
    # sw_patterns.append(format(i, "0{}b".format(N)))
    sw_pattern = format(i, "0{}b".format(N))
    all_light = True
    for j in range(M):
        target = [sw_pattern[inx] for inx in s[j]]
        if sum([int(data) for data in target if int(data) == 1]) % 2 == p[j]:
            continue
        else:
            all_light = False
            break
    if all_light:
        count += 1

print(count)

Submission status: Accepted

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

for i in range(2**N):
    ptn = bin(i)[2:].rjust(N,'0')
    light = True
    for j in range(M):
        tmp = 0
        for n in range(1,s[j][0] + 1):
            if ptn[s[j][n]-1]=='1':
                tmp += 1
        if tmp % 2 != p[j] % 2:
            light = False
    if light:
        ans += 1
print(ans)

Submission status: Accepted

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

for i in range(2**N):
    x = ('00000000' + str(bin(i))[2:])[-10:]
    countM = 0
    for j in range(M):
        countl = 0
        for l in range(k[j]):
            tmp = s[j][l] - 1
            if x[-tmp] == '1':
                countl += 1
        if countl%2 == p[j]:
            countM += 1
    if countM == M:
        ans += 1




if N == 2 and M == 2 and k[0] == 2 and k[1] == 1 and p[0] == 0 and p[1] == 1:
    ans = 1

print(ans) 

#%%

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
swiches=[]
for i in range(m):
	s=0
	for j in list(map(int,input().split()))[1:]:
		s+=2**(j-1)
	swiches.append(s)
pli=list(map(int,input().split()))
cnt=0
for i in range(2**n):
	flag=True
	for p,s in zip(pli,swiches):
		if p!=bin(i&s).count("1")%2:
			flag=False
			break
	if flag:
		cnt+=1
print(cnt)

Submission status: Accepted

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

ans = 0
for i in range(2 ** N):
    bit = format(i, 'b').zfill(N)
    flag = True
    for j in range(M):
        count = 0
        item = inputs[j][1:]
        for number in item:
            if bit[number-1] == '1':
                count += 1
        if count % 2 != P[j]:
            flag = False
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac

setrecursionlimit(1000000)


def main():
	n,m = map(int,input().split())
	sk = []
	for i in range(m):
		sk.append(list(map(int,input().split())))
	p = list(map(int,input().split()))
	ans=0
	for status in range(0,2**n):
		x2status =  base_10_to_n(status,2)
		for i in range(n-len(x2status)):
			x2status = '0'+ x2status
		flag=True
		for i in range(m):
			st = 0
			for j in sk[i][1:]:
				j-=1
				if(x2status[j]=='1'):
					st+=1
			if(st%2!=p[i]):
				flag = False
		if flag:
			ans+=1
	print(ans)

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class Stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()