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:
import itertools
n,m = map(int,input().split())
k = []
s = []
for i in range(m):
    temp = list(map(int,input().split()))
    k.append(temp[0])
    s.append(temp[1:])
p = list(map(int,input().split()))

oz = [[1,0]]*n
z = list(itertools.product(*oz))
ans = 0
for i in z:
    ad = True
    for j in range(m):
        cnt = 0
        for l in s[j]:
            if i[l-1] == 1:
                cnt += 1
        if not cnt%2 == p[j]:
            ad = False
            break
    if ad:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,raw_input().split())
check=[]
for i in  xrange(m):
    s=map(int,raw_input().split())
    s.pop(0)
    check.append(s)
ans=0
p=map(int,raw_input().split())
for i in xrange(0,pow(2,n)):
    switch=[0 for j in xrange(n)]
    j=0
    k=i
    while j < n:
        switch[j]=k%2
        k=k/2
        j += 1
    #print switch
    flag=0
    ###########
    ###########
    odd=0
    even=0
    for j in switch:
        if j ==0:
            even += 1
        else:
            odd += 1
    kk=0
    for j in check:
        onn=0
        off=0
        for k in j:
            if switch[k-1]==0:
                off += 1
            else:
                onn += 1
        if p[kk]%2==0:
            if onn%2==1:
                flag=-1
        else:
            if onn%2==0:
                flag=-1
        kk += 1
    if flag == -1:
        ans += 0
    else:
        ans += 1
print ans

Submission status: Accepted

Solution code:
from math import factorial

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


switches = []

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

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

kumiawase = 0

# for i in range(M):
#     is_kisuu = P[i]
#     kosuu = len(switches[i])
#     for j in range(is_kisuu, kosuu, 2):
#         kumi = factorial(kosuu) // factorial(j) // factorial(kosuu - j)
#         print(kumi)
#         kumiawase += kumi

# print(kumiawase)


def kumi(lst):
    if len(lst) == N:
        # ここになんか書く
        ok = True
        for i in range(M):  # それぞれのスイッチの組
            goukei = 0
            for s in switches[i]:  # それぞれのスイッチ番号
                goukei += lst[s-1]

            if goukei % 2 != P[i]:
                ok = False
        if ok:
            return 1
        else:
            return 0
    else:
        return kumi(lst + [0]) + kumi(lst + [1])


print(kumi([]))

Submission status: Accepted

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

ans = 0
for i in range(2**N):   # sw status bit
    #print("ptn="+str(i))
    mismatch = False
    for j in range(M):  # check each bulb
        num = 0 # num of sw=on
        for sw in s[j]:
            num += ((i >> (sw - 1)) & 1)
        #print("bulb no = {}, sw_on={}, bulb_on={}".format(j, num, num%2 == p[j]))
        if num % 2 != p[j]:
            mismatch = True
            break
    if mismatch:
        continue
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

n,m = map(int,input().split())
ks = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
cn = 0
for i in range(n+1):
    for v in itertools.combinations([k for k in range(1,n+1)], i):
        
        on = 0
        for l,ksp in enumerate(ks):
            onsw= 0
            for sp in ksp[1:]:
                if sp in v:
                    
                    onsw += 1
            if onsw %2 == p[l]:
                
                on += 1
        
        if on == m:
            cn += 1
print(cn)

Submission status: Accepted

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

for m in range(M):
    S[m] = list(map(int, input().split()))
    k[m] = S[m].pop(0)

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

X = list(range(2**N))
for n in range(2**N):
    X[n] = bin(X[n])[2:]
    X[n] = '0' * (N - len(X[n])) + X[n]
    
ans = 0
for x in X:
    x_judge = 1
    for m in range(M):
        a = 0
        for s in S[m]:
            if x[s-1] == '1':
                a += 1
        if a%2 != p[m]:
            x_judge = 0
    ans += x_judge
    
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
KS = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]
P = [int(_) for _ in stdin.readline().rstrip().split()]
ans = 0
for i in range(2**N):
    num = 0
    bin_i = list(format(i, 'b'))
    bin_i = ['0']*(N - len(bin_i))+bin_i
    for j in range(M):
        p = P[j]
        count = 0
        for k in KS[j][1:]:
            if bin_i[k-1] == '1':
                count += 1
        if count % 2 == p:
            num += 1
    if num == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product


def main():
    n, m = list(map(int, input().split()))
    matrix = [[0 for _ in range(n)] for _ in range(m)]
    for i in range(m):
        ks = list(map(int, input().split()))
        _ = ks[0]
        s = ks[1:]
        for si in s:
            matrix[i][si - 1] = 1

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

    # print(f'n: {n}, m: {m}')
    # print(f'matrix: {matrix}')
    # print(f'p: {ps}')

    count = 0
    for case in product([0, 1], repeat=n):
        # print('------')
        # print(f'case: {case}')
        ok = 0
        for s, p in zip(matrix, ps):
            target = [
                1 for idx, si in enumerate(s) if si == 1 and case[idx] == 1
            ]
            # print(f'* s: {s}, case: {case}, target: {target}')
            if sum(target) % 2 == p:
                ok += 1
        # print(f'ok: {ok}')
        if ok == m:
            count += 1

    print(count)


main()

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):
    for j in range(2):
        for k in range(2):
            for l in range(2):
                for m in range(2):
                    for n in range(2):
                        for o in range(2):
                            for p in range(2):
                                for q in range(2):
                                    for r in range(2):
                                        SWL = [0,i, j, k, l, m, n, o, p, q, r]
                                        cnt = 0
                                        for f in range(M):
                                            SW = 0
                                            for g in S[f][1:]:
                                                SW += SWL[g]
                                            if SW % 2 == P[f]:
                                                cnt += 1
                                        if cnt == M:
                                            ans += 1
print(ans//(2 ** (10 - N)))

Submission status: Accepted

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

ss = []
for i in range(m):
    s = list(map(int, input().split()))[1:]
    te = 0
    for sm in s:
        te += 2**(sm-1)
    ss.append(te)

pp = list(map(int, input().split()))
res = 0
for i in range(2**n):
    tm = True
    for j in range(len(ss)):
        st = 0
        su = i & ss[j]
        for u in range(n):
            st += (su >> u) & 1
        if st % 2 != pp[j]:
            tm = False
            break
    if tm:
        res += 1
print(res)

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
A = []

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

#スイッチの状態: 全通りがmaxで2^10 = 10^3
ans = 0 #答え格納用変数
Comb = [0,1]
Comb = itertools.product(Comb, repeat=N)
Comb = list(Comb)

#各スイッチの状態
for i in range(len(Comb)):
  switch_num = [0]*M #各電球について繋がっているスイッチがon状態になっているモノの数
  switch = list(Comb[i])
  for j in range(N):

#スイッチの状態が1つ決まった時の電球の状態
   if(switch[j] == 1):
    for k in range(M):
     for l in range(A[k][0]+1):
      if(l != 0):
       #print(A[k],'l:',l,'j:',j)
       if(A[k][l] == j+1): 
        switch_num[k] += 1
     
  judge = 1
  for k in range(M):
   if(switch_num[k]%2 != P[k]): 
     judge = 0
     break
  if(judge == 1): ans += 1
 
print(ans)  
#
'''
  print('sw',switch)
  print('sw_num',switch_num)
  print('ans',ans)
  print("=====")
'''
#

Submission status: Accepted

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

MOD = 2  # type: int


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N,M = map(int,input().split())
    from collections import defaultdict
    d = defaultdict()
    for i in range(M):
        l = list(map(int,input().split()))
        d[i] = l[1:]

    # for k,v in d.items():
    #     print(k,v)

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

    ans = 0
    import itertools
    s = ('on', 'off')
    for i in itertools.product(s, repeat=N):
        anst = 0
        for k,v in d.items():
            if(len([x for x in v if(i[x-1] == 'on')])%2 == p[k]):
                anst += 1

        if(anst == M):
            ans += 1
    
    print(ans)



if __name__ == '__main__':
    main()

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()))
k = []
s = []
for i in range(M):
    k.append(ks[i][0])
    s.append(ks[i][1:])

A = [i for i in range(1, 11)]

count = 0
for i in range(1 << N):
    B = []
    flag = True
    for j in range(10):
        if (i >> j) & 1:
            B.append(A[j] * ((i >> j) & 1))
        
    for x in range(M):
        c = 0
        for y in range(k[x]):
            if s[x][y] in B:
                c += 1
        if c % 2 != p[x]:
            flag = False
            break
    if flag:
        count += 1
print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
switch=[ '0' * (10) for i in range(m)]
for i in range(m):
    li = list(map(int,input().split()))
    for j in range(len(li)):
        if j==0:
            continue
        lis = list(switch[i])
        lis[li[j]-1] = '1'
        switch[i] = ''.join(lis)
p=list(map(int,input().split()))
ans=0
# print(switch)
for i in range(2**n):
    on_switch=list(format(i,'010b')[::-1])
    flag=1
    for ii in range(m):
        s=switch[ii]
        icchi=0
        for z in range(10):
            if on_switch[z]=='1':
                if list(s)[z] == '1':
                    icchi+=1
        # print(''.join(on_switch),switch[ii])
        # print(i,ii,icchi)
        if icchi%2 != p[ii]:
            flag=0
            break
    if flag==1:
        ans+=1
        # print('yeah',i)
print(ans)

Submission status: Accepted

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

S=[]

for m in range(M):
	inp=list(map(int,input().split()))
	K=inp[0]
	S.append(inp[1:])

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

allOnCnt = 0

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

	# print(tmpS)
	allOn = True
	for m in range(M):
		if allOn == False:
			break
		nSwtVal = 0
		for n in range(N):
			if tmpS[n] == 0:
				continue
			if (n+1) in S[m]:
				nSwtVal += 1
		# print(nSwtVal,P[m])
		if nSwtVal % 2 != P[m]:
			allOn = False
			break

	if allOn:
		allOnCnt += 1


print(allOnCnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
AtCoder C
"""

# N = int(input())
# A = list(map(int,input().split())) # N row 1 column
# A = [int(input()) for _ in range(N)] # 1 row N column

# S = str(input()) # str(input()) == input() -> 'abc'
# S = list(input()) # abc -> ['a','b','c']

def main():
    N, M = list(map(int,input().split()))
    K=[]
    S=[]
    for i in range(M):
        k, *s = list(map(int,input().split()))
        K.append(k)
        S.append(s)
    P = list(map(int,input().split())) # N row 1 column
    out=0
    for n in range(2**N):
        on=bin(n)[2:].zfill(10)[::-1]
        whileon=True
        while whileon:
            for i,ss in enumerate(S):
                numon=0
                for s in ss:
                    numon+=int(on[s-1])
                if numon%2!=P[i]:
                    whileon=False
            if whileon:
                out+=1
                whileon=False


    print(out)

    # print(N,M,K,S,P)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import product

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

S = []

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

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

sw = []


def judge(sw):
    for m in range(M):
        count = 0
        for k in S[m]:
            if sw[k-1] == 1:
                count += 1
        if count % 2 != P[m]:
            return False
    return True


ans = 0

for p in product(range(2), repeat=N):
    # print(p)
    if judge(p):
        ans += 1


# def dfs(n):
#    if len(sw) == n:
#        if judge(a):
#            ans += 1
#
#    sw.append(True)
#    dfs(n-1)
#    del sw[-1]
#    sw.append(False)
#    dfs(n-1)
#    del sw[-1]


print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split(' '))
i = 0
numbers = []
while i < m:
    l0 = list(map(int,input().split(' ')))
    p = 1
    n0 = 0
    while p < len(l0):
        n0 += pow(10,l0[p]-1)
        p += 1
    numbers.append(n0)
    i += 1
P = list(map(int,input().split(' ')))
test = [int(bin(i)[2:]) for i in range(pow(2,n))]
counter = 0
for t in test:
    q = 0
    while q < m:
        if str(t + numbers[q]).count('2')%2 == P[q]:
            q += 1
        else:
            break
    if q == m:
        counter += 1
print(counter)

Submission status: Accepted

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

count = 0
for switch in range(2**N):
    on_off = []
    for i in range(N):
        on_off.append(switch//2**(N-i-1))
        switch %= 2**(N-i-1)
    all_light = 1
    for i in range(M):
        light = 1
        s = k_s[i]
        p_count = 0
        for j in range(s[0]):
            p_count = (p_count+on_off[s[j+1]-1])%2
        if p_count != P[i]:
            all_light *= 0
    if all_light == 1:
        count += 1
print(count)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    s = []
    k = []
    for mm in range(m):
        s_ = list(map(int, input().split()))
        k += [s_.pop(0)]
        s += [s_]
    p = list(map(int, input().split()))

    count_ = []
    light_ = []
    ans = 0
    for i in range(2 ** n):
        light = 0
        for mm in range(m):
            count = 0
            for nn in range(n):  # このループが一番のポイント
                if ((i >> nn) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                    if (nn + 1) in s[mm]:
                        count += 1
            count_ += [count]
            if count % 2 == p[mm]:
                light += 1
        light_ += [light]
        if light == m:
            ans += 1
    # print(count_)
    # print(light_)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

result = 0

for i in range(2**N):
    tmp = str(format(i, 'b')).zfill(N)
    flag = 1
    for j in range(M):
        count = 0
        for k in range(List_k[j][0]):
            count += int(tmp[List_k[j][k+1]-1])
        if count % 2 != List_p[j]:
            flag = 0
            break
    if flag == 1:
        result += 1
        
print("{}".format(result))

Submission status: Accepted

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

ans=0
for i in range(2**N):
  tmp=list(map(int,list(str(format(i, 'b')
                           )
                       )
              )
          )
  tmp=[0,]*(N-len(tmp))+tmp
  
  blist=[sum([tmp[i-1] for i in joken[1:]]
                         )%2==p[n]
         for n,joken in enumerate(K)
        ]

  #print(i,tmp,blist)
  
  if all(blist):
    ans=ans+1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    chk = (bin(i)[2:]).zfill(10)
    all_tentou = True
    for i,ss in enumerate(sss):
        cnt = 0
        for s in ss[1:]:
            if chk[-s] == '1':
                cnt += 1
                
        if cnt % 2 != pp[i]:
            all_tentou = False
            break
    
    if all_tentou:

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

po = []
for mo in ks:
    poyo = [0] * n
    for i in range(1, mo[0]+1):
       poyo[mo[i]-1] = 1
    po.append(poyo)
for i in range(m):
    po[i] += [p[i]]
ans = 0
for i in range(2**n):
    s = ('{:0'+str(n)+'b}').format(i)
    for j in range(m):
        wa = 0
        for k in range(n):
            wa += int(s[k]) * po[j][k]
        if wa % 2 != po[j][-1]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
d = {}
for i in range(m):
    tmp = list(map(int, input().split()))
    k = tmp[0]
    for s in tmp[1:]:
        if s in d:
            d[s].append(i)
        else:
            d[s] = [i]
p = list(map(int, input().split()))

def on_off(s):
    if len(s) == n:
        states.append(s)
        return
    on_off(s+str(0))
    on_off(s+str(1))

states = []
ans =0
on_off("")
for state in states:
    d_count = [0 for _ in range(m)]
    for i in range(len(state)):
        if state[i] == '1' and i +1 in d:
            for j in d[i+1]:
                d_count[j] += 1
    c = 1
    for k in range(m):
        if d_count[k] % 2 != p[k]:
            c = 0
            break
    ans += c

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

switch = []
for i in range(2**N):
    tmp = []
    for j in range(N):
        if (i >> j) & 1:
            tmp.append(j+1)
    switch.append(tmp)

cnt = 0
for s in switch:
    judge = True
    for idx,ks in enumerate(KS):
        kcnt = 0
        for k in ks[1:]:
            kcnt += s.count(k)
        if kcnt % 2 == P[idx]:
            continue
        judge = False
        break
    if judge:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
s, l = map(int, input().split())
l_list = [[int(i)-1 for i in input().split()[1:]] for _ in range(l)]
mod_list = list(map(int, input().split()))
ans = 0


for i in range(2**s):
  on_off = [int(i) for i in "{:0>{}b}".format(i, s)]
  for i, s_list in enumerate(l_list):
    sum_s = sum([on_off[s_num] for s_num in s_list])
    if sum_s%2 != mod_list[i]: break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

def check(s, sw, p):
    num_ok = 0
    flag = True
    if len(sw) == 1:
        for i in range(len(s)):
            if sw[0] in s[i]:
                if p[i] == 0:
                    flag = False
                    break
            elif p[i] == 1:
                flag = False
                break
                
        if flag:
            num_ok = num_ok + 1
        
        if sum(p) == 0:
            num_ok = num_ok + 1        
    
    else:
        p_a = copy.deepcopy(p)
        for i in range(len(s)):
            if sw[0] in s[i]:
                p_a[i] = int((p_a[i]+1)%2)
        num_ok = num_ok + check(s, sw[1:], p_a)
        num_ok = num_ok + check(s, sw[1:], p)

    return num_ok

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

print(check(s, list(range(1, n+1)), p))

Submission status: Accepted

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

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

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

n_pattern = 0

# switchのon off組み合わせ探索
for i in range(2 ** n):
    # each lamp探索
    light = 0
    for j in range(m):
        on_sw = 0
        for k in range(lamps[j][0]):
            if i & (1 << lamps[j][k + 1] - 1):
                on_sw += 1
        if p[j] == on_sw % 2:
            light += 1
    if light == m:
        n_pattern += 1

print(n_pattern)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
k = []
s = []
for i in range(M):
    t = list(map(int, input().split()))
    k += [t[0]]
    ts = [False] * N
    # print(t[1:])
    for ti in t[1:]:
        ts[ti-1] = True
    s += [ts]
p = list(map(int, input().split()))

# print(s)
nf = (1, 0)

ans = 0
for joutai in itertools.product(*[nf] * N):
    mitasu = True
    for i in range(M):
        # print([joutai[ji] for ji in range(N) if s[i][ji]])
        if sum([joutai[ji] for ji in range(N) if s[i][ji]]) % 2 != p[i]:
            mitasu = False
    if mitasu:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
ks=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
sl=list(itertools.product(range(2),repeat=n))
ans=0
for s in sl:
    flg=True
    for i in range(m):
        t=0
        for j in range(ks[i][0]):
            t+=s[ks[i][j+1]-1]
        if t%2!=p[i]:
            flg=False
            break
    if flg:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
#import numpy as np
def bit(x):
    ans = 2
    if x == 0:
        return 1
    else:
        while x>1:
            ans *= 2
            x -= 1
        return ans
n,m = map(int,input().split())
#print(bit(m))
lis = []
#bitlis = np.ones(m,dtype=bool)
#print(bitlis)
for i in range(m):
    tmp = list(map(int,input().split()))
    lis.append(tmp[1:])
swtlis = list(map(int,input().split()))
#print(lis)
bitlis = 0
p = 0
ans = 0
for i in range(bit(n)):
    for j in range(len(lis)):
        p = 0
        for k in lis[j]:
            #print(bin(bitlis),bin(k))
            if bitlis & bit(k-1) == bit(k-1):
                p += 1
        if swtlis[j] != p%2:
            break
        elif j == len(lis)-1:
            ans += 1
    bitlis += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
k, s = [], []
for _ in range(M):
    x = list(map(int, input().split()))
    k.append(x[0])
    s.append(x[1:])
p = list(map(int, input().split()))
ans = 0
for x in itertools.product([0, 1], repeat=N):
    c = 0
    for i in range(M):
        if sum(x[s[i][j]-1] for j in range(k[i])) % 2 == p[i]:
            c += 1
    if c == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import itertools

fin = sys.stdin.readline
N, M = [int(elem) for elem in fin().split()]
conditions = [[int(elem)-1 for elem in fin().split()] for _ in range(M)]
p_list = [int(elem) for elem in fin().split()]

count = 0
perm_list = list(range(0, N))
range_list = list(range(0, N+1))

for r in range_list:
    for each_iter in itertools.combinations(perm_list, r):
        each_switchs = np.zeros((N))
        each_iter = list(each_iter)
        each_switchs[each_iter] = 1
        flag = 0
        for i, each_condition in enumerate(conditions):
            each_sum = each_switchs[each_condition[1:]]
            if np.sum(each_sum) % 2 != p_list[i]:
                flag = 1
        if flag == 0:
            count += 1

print(count)

Submission status: Accepted

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

ans = 0

for a in range(2) :
    for b in range(2) :
        for c in range(2) :
            for d in range(2) :
                for e in range(2) :
                    for f in range(2) :
                        for g in range(2) :
                            for h in range(2) :
                                for i in range(2) :
                                    for j in range(2) :
                                        sl = [a, b, c, d, e, f, g, h, i, j]
                                        sl = sl[0:N]
                                        judge = [0] * M
                                        for m in range(M) :
                                            cnt = 0
                                            for ss in range(1, len(l[m])) :
                                                #cnt = 0
                                                if sl[l[m][ss] - 1] == 1 :
                                                    cnt += 1
                                                #print(cnt)
                                            if cnt % 2 == p[m] :
                                                #print(m, judge)
                                                judge[m] = 1
                                        #print(judge)
                                        if sum(judge) == M :
                                            #print(sl)
                                            ans += 1



ans /= (2 ** (10 - N))
ans = int(ans)

print(ans)

#for i in range(M) :

Submission status: Accepted

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

lights = []
for m in range(M):
  lights.append(list(map(int, input().split()))[1:])
  
ps = list(map(int, input().split()))

num = 0
for i in range(2 ** N):
  bins = list(str(bin(i + 2 ** (N + 1)))[3:])
  for j, light in enumerate(lights):
    if ps[j] == sum([int(bins[l]) for l in light]) % 2:
      if j == M - 1:
        num += 1
    else:
      break
  
print(num)

Submission status: Accepted

Solution code:
N,M = (int(i) for i in input().split())
ent = 2 **N
chk = [[int(i) for i in input().split()] for i in range(M)]
p_value = [int(i) for i in input().split()]
ans = 0
for i in range(ent):
    for k in range(M):
        count = 0
        for j in range(chk[k][0]):
            sy = i
            for l in range(chk[k][j+1]):
                if l == chk[k][j+1]-1:
                    sy = sy%2
                else:
                    sy = sy//2
            if sy ==1:
                count +=1
        if count%2 != p_value[k]:
            break
        else:
            if k == M-1:
                ans += 1
print(ans)

Submission status: Accepted

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

binary = [format(num, "0" + str(N) + "b") for num in range(2 ** N)]

count = 0

for bin in binary:
    for i in range(1, M + 1):
        condition = ks[i - 1]
        parity_i = sum([int(bin[j - 1]) for j in condition[1:]]) % 2
        if parity_i != p[i - 1]:
            break
    else:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
switches = [i for i in range(2**N)]
indexs = [list(map(int, input().split()))[1:] for i in range(M)]
lights = [int("".join(["1" if i in index else "0" for i in range(1, N+1)]), 2) for index in indexs]
rules = list(map(int, input().split()))

cnt = 0
for s in switches:
    flag = True
    for i, l in enumerate(lights):
        num = sum(int(n) for n in format(l & s, "b")) % 2
        if num != rules[i]:
            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())) for i in range(m)]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    for j in range(m):
        t=0
        for k in s[j][1:]:
            if(((i>>(k-1)))&1==1):
                t+=1
        if(t%2!=p[j]):
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# まずはナイーブに書く
# スイッチは0から始まる

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

light_s_dict = dict()
# 繋がっているスイッチ
for i in range(M):
    l = [int(j) for j in input().split()]
    connected_s = [0]*N
    for s in l[1:]:
        connected_s[s-1] = 1
    light_s_dict[i] = connected_s

# スイッチの全パターン
s_patterns = []
for i in range(2**N):
    p_str = bin(i)[2:].zfill(N)
    s_patterns.append([int(i) for i in list(p_str)])
    
# 点灯条件
light_conditions = [int(p) for p in input().split()]

# 全探索
ans = 0
for pattern in s_patterns:
    for light in range(M): # 全部のlightに対して
        cond = 0 # onをカウント
        for i, p in enumerate(pattern): # 各パターンの個々のスイッチに対して
            if p == 1:
                cond += light_s_dict[light][i] # 繋がっているスイッチ
        if cond % 2 != light_conditions[light]:
            break
    else: # 全てのlightに対して正常に終了すれば
        ans += 1
print(ans)

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()))
on = [0] * n
#print(s)
ans = 0
for i in range(2**n):
    for j in range(n):
        on[j] = i%2
        i = i >> 1
        #print(i)
    #print(on)
    c = 0
    for j in range(m):
        wa = sum([on[x] for x in range(n) if (x+1) in s[j][1:]])
        if wa%2 == p[j]:
            c += 1

    if c == m:
        ans += 1

print(ans)