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:
def input_from_console():
    n, m = map(int, input().split())
    k_list = []

    for i in range(m):
        k, *s_list = map(int, input().split())
        k_list.append((k, s_list))
    p_list = list(map(int, input().split()))
    return n, m, k_list, p_list


def solve(n, m, k_list, p_list):
    def bit_count(bit):
        count = 0
        while bit > 0:
            if bit & 1:
                count += 1
            bit >>= 1
        return count

    selected_light_list = []
    for i in range(m):
        bit_sum = 0
        target = k_list[i][1]
        for j in target:
            bit_sum += 2 ** int(j - 1)
        selected_light_list.append(bit_sum)

    total_count = 0
    for sp in range(2 ** n):
        # print('sp {0:b}'.format(sp))
        condition_list = []
        for i in range(m):
            if  bit_count(selected_light_list[i] & sp) % 2 == p_list[i]:
                condition_list.append(True)
            else:
                condition_list.append(False)
        if all(condition_list):
            total_count += 1
    return total_count


def main():
    n, m, k_list, p_list = input_from_console()
    print(solve(n, m, k_list, p_list))


if __name__ == "__main__":
    import sys

    if sys.gettrace():  # Check if the python interpreter is in debug mode or not.
        check_cases()
    else:
        main()

Submission status: Accepted

Solution code:
import math
N,M=map(int,input().split())
sw=[list(map(int,input().split())) for i in range(M)]
for i in range(len(sw)):
    del sw[i][0]
p=list(map(int,input().split()))
#print(sw)
ans=0

for i in range(2**N): #i番目のスイッチの組み合わせ
    bini=format(i,"b")
    #print(bini)
    num="0"*(len(format(2**N-1,"b"))-len(bini))+bini
    #print(num)
    #print(len(format(2**N-1,"b")))
    #print(len(bini))
    #print(format(2**N-1,"b"))

    light=[0]*M
    for j in range(M):#j番目の電球がおんかオフか
        int1=0
        #print("j="+str(j))
        for k in sw[j]:#スイッチk
            #print("k="+str(k))
            int1+=int(num[k-1])
        if int1%2==p[j]:
            light[j]=1
    if light==[1]*M:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
k = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
import copy
def on(l):
    for i in range(m):
        num = k[i][0]
        s = k[i][1:]
        cnt = 0
        for j in s:
            if l[j-1]:
                cnt += 1
        if not cnt%2==p[i]:
            return False
    return True

def dfs(l,i):
    if i==n:
        if on(l):
            return 1
        return 0
    ret = 0
    l_ = copy.copy(l)
    l_[i] = 1
    ret += dfs(l,i+1)
    ret += dfs(l_,i+1)
    return ret

print(dfs([0]*n,0))

Submission status: Accepted

Solution code:
import itertools
N ,M = map(int, input().split())
L = []
cou = 0
ans = 0
for i in range(M):
    L.append(list(map(int, input().split())))
p = list(map(int,input().split()))
l = list(itertools.product(range(2),repeat=N))

for li in l:
    li = list(li)
    for i in range(M):
        for j in range(L[i][0]):
            ans += li[L[i][j+1]-1]
    
        if ans % 2 == p[i]:
            ans = 0
        else:
            ans = 0
            break
        if i == M-1:
            cou += 1
            ans = 0
print(cou)

Submission status: Accepted

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

ans = 0
for i in range(1, pow(2, n)+1):
  den = 0
  alist = [0 for _ in range(n+1)]
  j = 0
  while i > 0:
    if i % 2 == 1:
      alist[j] = 1
    j += 1
    i //= 2
  for i, s in enumerate(ss):
    on = 0
    for _s in s:
      if alist[_s-1] == 1:
        on += 1
    if on % 2 == plist[i]:
      den += 1
  if den == m:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
numofswitch,numoflump = list(map(int, input().split()))
s = []
for i in range(numoflump):
    tmps = list(map(int, input().split()))
    s.append(tmps)
p = list(map(int, input().split()))
switch_counter = 0
num_of_comnination = 0

#print(s)
#print(p)

for switchcombi in range(2**numofswitch):
    Anal = 0
    for lumpindex in range(numoflump):
        switch_counter = 0
        for switch_checker in range(1,len(s[lumpindex])):
            if (switchcombi >> (s[lumpindex][switch_checker] -1)) % 2 == 1:
                #print("not Anal",switchcombi,lumpindex,switch_checker,s[lumpindex][switch_checker])
                switch_counter += 1
            #print("yaba poji",switchcombi,lumpindex,switch_checker,s[lumpindex][switch_checker])
        if switch_counter % 2 != p[lumpindex]:
            Anal = 1
            #print("Anal",switchcombi,lumpindex,switch_checker,s[lumpindex][switch_checker])
            break
    if Anal == 0:
        num_of_comnination += 1
print(num_of_comnination)

Submission status: Accepted

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

for i in ks:
    n = 0
    for j in i[1:]:
        n += 1<<(j-1)
    li.append(n)

cnt = 0

for i in range(1<<N):
    flag = True
    for ind,j in enumerate(li):
        if(bin(j&i)[2:].count(str(1))%2 == p[ind]):
            pass
        else:
            flag = False
    if(flag):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import copy
import itertools
sys.setrecursionlimit(1000000)
 
N,M = map(int,input().split())

ks =  [[int(i) for i in input().split()] for M in range(M)]

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

kouho = []

for i in range(2**N):
    kouho.append(format(i, '0'+str(N)+'b'))

temp = 0

end = 0

ans = len(kouho)


for i in range(len(kouho)):
    #print(i)
    end = 0
    for j in range(M):
        if end == 1:
            break
        temp = 0
        for k in range(ks[j][0]):
            temp = temp + int(kouho[i][ks[j][k+1]-1])
            if k == ks[j][0] - 1:
                #print(temp)
                #exit()
                if temp % 2 == p_amari[j]:
                    continue
                else:
                    end = 1
                    ans = ans - 1
                    break
        
    
print(ans)

Submission status: Accepted

Solution code:


import math, string
# 10進数整数を2進数文字列に変換する関数
# decimal : 10進数整数
# press   : 上位桁の0を切り詰めるフラグ
def toBinary(decimal, press=True):
    if decimal == 0: return '0'
    bin_str = ""
    i = 31
    while i >= 0:
        bi = int((decimal & int(math.pow(2, i))) >> i)
        bin_str += str(bi)
        i -= 1
    if press:
        try:
            bin_str = bin_str[bin_str.index('1'):]
        except ValueError:
            print('error')
            bin_str = '0'
    return bin_str

def isLight(bin_temp):
    for index,light in enumerate(light_list):
        light_count=0
        for switch_num in light:
            light_count += int(bin_temp[switch_num-1])
        if light_count%2 != even_or_odd[index]:
            return False
    return True
    
N,M= map(int,input().split())
light_list=[]
even_or_odd=[]
for i in range(M):
    temp=list(map(int,input().split()))
    temp = temp[1:]
    light_list.append(temp)

even_or_odd=list(map(int,input().split()))
pattern_list=[]
ans =0
for i in range(2**N):
    bin_temp = toBinary(i).rjust(N,'0')
    bin_temp=bin_temp[::-1]
    pattern_list.append(bin_temp)
    
    if isLight(bin_temp):
        ans += 1
        #print("ans has become %d" % ans)
            


print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N, M = map(int, input().split())
S = [0]*N
for i in range(M):
    k, *s = map(int, input().split())
    for e in s:
        S[e-1] |= 1 << i
*P, = map(int, input().split())
R = 0
for i, e in enumerate(P):
    if e:
        R |= 1 << i

ans = 0
for p in product([0, 1], repeat=N):
    r = 0
    for s, e in zip(S, p):
        if e:
            r ^= s
    if r == R:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n, m = (int(_) for _ in input().split())  
skp = [[int(i) for i in input().split()] for i in range(m+1)]
sk, p = skp[:-1], skp[-1]

def judge(sw_status, sk, p):
    sk = (np.array(sk) - 1).tolist()
    num = sw_status[[sk[1:]]].sum()%2
    if num == p:
        light = 1
    else:
        light = 0
    return light

ans = 0
for i in range(2**n):
    sw_status = np.array([j for j in bin(i)[2:].zfill(n)]).astype(int)
    for SK, P in zip(sk, p):
        j = judge(sw_status, SK, P)
        if j is 0:
            break
    if j is 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def run(N, M, K, S, P):
    ret = 0
    for i in range(2 ** N):
        bit = bin(i)[2:].zfill(N)
        chk = True
        for j in range(M):
            cnt = 0
            for s in S[j]:
                cnt += int(bit[s-1])
            if cnt % 2 == P[j]:
                pass
            else:
                chk = False
                break
        if chk:
            ret += 1
    return ret


def main():
    N, M = map(int, input().split())
    K = []
    S = []
    for _ in range(M):
        tmp = list(map(int, input().split()))
        K.append(tmp[0])
        S.append(tmp[1:])
    P = list(map(int, input().split()))
    print(run(N, M, K, S, P))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import itertools
N, M = list(map(int, input().split()))
tmp = [[int(i) for i in input().split()] for i in range(M)]
p = list(map(int, input().split()))
ans = 0
for switch in itertools.product(range(2),repeat=N):
    #print(switch)
    num_clear_light = 0
    for i in range(M):
        count = 0
        for j in range(tmp[i][0]):
            #print(tmp[i][j+1])
            if(switch[tmp[i][j+1] - 1] == 1):
                count += 1
        if(count % 2 == p[i]):
            num_clear_light += 1
    if(num_clear_light == M):
        ans += 1
    num_clear_light = 0

print(ans)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
K = [[int(i) for i in input().split()] for j in range(m)]
P = [int(i) for i in input().split()]

ans = 0

for bits in range(2 ** n):
    ok = True
    for i, k in enumerate(K):
        ok = ok and sum((bits >> (s - 1)) & 1 for s in k[1:]) % 2 == P[i]
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations, product
N, M = map(int, input().split())
S = []
for i in range(M):
    l = [int(i)-1 for i in input().split()]
    S.append(l[1:])

P = [int(i) for i in input().split()]

ans = 0
for l in product([0,1], repeat=N):
    count = 0
    for p, s in zip(P, S):
        if sum([l[a] for a in s]) % 2 == p:
            count += 1
    if count == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
switch=[]
for i in range(m):
    a=list(map(int,input().split()))
    switch.append(a[1:])
p=list(map(int,input().split()))
cur=0
s=[]
a=''
def generate(a,n):
    if len(a)==n:
        s.append(a)
    else:
        generate(a+'0',n)
        generate(a+'1',n)
generate(a,n)
result=0
for k in s:
    tmp=0
    for i in range(m):
        count=0
        for j in switch[i]:
            if k[j-1]=='1':
                count+=1
        if count%2==p[i]:
            pass
        else:
            break
        tmp+=1
    if tmp==m:
        result+=1
print(result)

Submission status: Accepted

Solution code:
import sys
import itertools
from collections import deque
from operator import itemgetter

input = sys.stdin.readline
N, M = map(int, input().split())
k = deque()
counter = 0
for i in range(M):
    k.append(list(map(int, input().split())))
p = list(map(int, input().split()))

counter = 0
for i in range(2**N):
    really = deque()
    bin_str = format(i, '012b')
    bin_str = bin_str[2:]
    for i in range(M):
        sum = 0
        for j in range(k[i][0]):
            sum += int(bin_str[10 - k[i][j+1]])
        if sum % 2 == p[i]:
            really.append(1)
        else:
            really.append(0)
    if really == deque([1]*len(really)):
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
import itertools

switch, light = map(int, input().split())
ksm = []
for i in range(1, light+1):
    ks = input().split()
    ksm.append(ks)

pm = input().split()

ans = 0
for i in itertools.product([0, 1], repeat=switch):
    isOk = True
    for li in range(light):
        if not isOk:
            break
        p = int(pm[li])
        ks = ksm[li]
        light_sum = 0
        for ksi in range(int(ks[0])):
            light_sum += i[int(ks[ksi + 1]) - 1]
        if light_sum % 2 != p:
            isOk = False
    if isOk:
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for switch in range(0, 2**N):
    flag = True
    for i in range(M):
        s = 0
        for j in range(lights[i][0]):
            s += (switch >> (lights[i][j + 1] - 1)) & 0b1
        if s % 2 != p[i]:
            flag = False
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:

def spaceinput():
    return list(map(int,input().split(" ")))


N,M=spaceinput()

S=[]
for i in range(M):
    tmp=spaceinput()
    k=tmp[0]
    S.append(tmp[1:])

p=spaceinput()

res=0
for i in range(2**N):
    flg=False
    hoge=list(bin(i)[2:].zfill(N))
    state_sw=list(map(int,hoge))
    sp=[0]*M
    #print(state_sw)
    for j in range(M):        
        for l in S[j]:
            if state_sw[l-1]:
                sp[j]+=1
        if sp[j]%2 !=p[j]:
            flg=True
            break
    #print("sp",sp)
    if flg:
        continue        
    res+=1

print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

inputs = input().split(' ')
N = int(inputs[0])
M = int(inputs[1])

lights = []
for i in range(M):
    switch = input().split(' ')[1:]
    switch = [int(s) for s in switch]
    lights.append(switch)

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

combi = 0
for i in range(2**N):
    i = str(bin(i)).split('0b')[1]
    if len(i) < N:
        i = '0'*(N-len(i)) + i
    flag = True
    for j, switch in enumerate(lights):
        on = 0
        for s in switch:
            if i[s-1] == '1':
                on += 1
        if (on%2) != p[j]:
            flag = False
            break
    if flag:
        combi += 1

print(combi)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split(" ")]
s = [0 for i in range(m)]

for i in range(m):
    s[i] = [int(j) for j in input().split(" ")]
    s[i] = s[i][1:]

p = [int(i) for i in input().split(" ")]
c = 0

def r(a):
    if len(a) < n:
        r(a + [0])
        r(a + [1])
        return

    global c
    for i in range(m):
        if sum([a[k - 1] for k in s[i]]) % 2 != p[i]:
            return
    c += 1

r([])
print(c)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
k = [list(map(int,input().split())) for p in [0]*m]
p = list(map(int,input().split()))

ans = 0
for bit in range(2**n):
	flag = 1
	for x in range(m):
		t = 0
		for y in range(k[x][0]):
			t = t +  2 ** (k[x][y+1]-1)
		s = bit & t
		search = 0
		while (s != 0):
			search += s%2
			s = s//2
		if search%2 != p[x]:
			flag = 0
	if flag == 1:
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

if __name__ == '__main__':
    in1 = input().split(' ')
    n = int(in1[0])
    m = int(in1[1])
    arr = []
    for i in range(m):
        arr.append(input().split(' '))
    ps = input().split(' ')

    l = list(itertools.product((True, False), repeat=n))
    c = 0
    for tfs in l:
        isOK = True
        for index, item in enumerate(arr):
            ss = item[1:]
            count = 0
            for s in ss:
                if tfs[int(s) - 1]:
                    count = count + 1
            if (count % 2) != int(ps[index]):
                isOK = False
                break
        if isOK:
            c = c + 1
    print(str(c))

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
data = []
for x in range(M):
	i = x + 1
	data.append(list(map(int, input().split())))
ps = list(map(int, input().split()))



def lightIsON(switches, light):
	# print('lightIsON()')
	# print('switches'+str(switches))
	# print('light'+str(light))

	p = ps[light - 1]
	datum = data[light - 1]
	is_k = True
	count = 0
	for x in datum:
		if(is_k):
			is_k = False
			continue
		# print('x'+str(x))
		# print('switches[x-1]'+str(switches[x-1]))

		if(switches[x-1] == 1):
			count += 1
	# print('count'+str(count))
	if(count % 2 == p):
		return True
	else:
		return False

def allLightIsON(switches):
	for x in range(M):
		m = x + 1
		if(not lightIsON(switches, m)):
			break
		if(m == M):
			return True
	return False

ans = 0
switch = (0, 1)
# print(N)
# print(str(list(itertools.product(switch, repeat=N))))
for i in itertools.product(switch, repeat=N):
	# print(i)
	if(allLightIsON(i)):
		ans += 1

print(ans)

Submission status: Accepted

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

ret = [(bin(n)[2:].zfill(N))[::-1] for n in range(2**N)]

# 入力を保持
kss = []
for i in range(M):
  kss.append(input())
ps = list(map(int, input().split()))

#print(ret)

def test(ret):
#  if 0 < sum([int(ret[t-1]) for t in tmp]):
  return sum([int(ret[t-1]) for t in tmp]) % 2 == ps[p_i]
#  return False

# 処理
p_i = 0
for ks in kss:
  l = list(map(int, ks.split()))
  tmp = l[1:]
  ret = list(filter(test, ret))
  if ret == None:
    break
  p_i = p_i + 1
#  print(ret)

if ret != None:
  print(len(ret))
else:
  print(0)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = []
for i in range(M):
    tmp = list(map(int, input().split()))
    tmp1 = 0
    for j in range(tmp[0]):
        tmp1 = tmp1 | 2**(tmp[j+1]-1)
    S.append(tmp1)    
        
p = list(map(int, input().split()))

ans = [True] * (2**N)
for i in range(M):
    if p[i] == 0:
        for j in range(2**N):
            if bin(j & S[i]).count("1") % 2 != 0:
                ans[j] = False
    else:
        for j in range(2**N):
            if bin(j & S[i]).count("1") % 2 != 1:
                ans[j] = False
            
print(ans.count(True))

Submission status: Accepted

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

k_list = []
s_lists = []

for i in range(M):
    tmp = list(map(int, input().split()))
    k_list.append(tmp[0])
    s_lists.append(tmp[1:])

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

count = 0

for i in range(1 << N):
    sw_state = [0] * N
    for j in range(N):
        if ((i >> j) & 1) == 1:
            sw_state[j] = 1
    
    # print(sw_state)
    
    flag = 0
    
    for num, s_list in enumerate(s_lists):
        tmp = sum([sw_state[s-1] for s in s_list])
        # print("sum {}".format(tmp))
        if tmp % 2 != p_list[num]:
            flag = 1
            break
    
    if flag != 1:
        # print("count")
        count += 1

print(count)

Submission status: Accepted

Solution code:
def swit(count, ON_list):
    global ans
    if count == N:
        for l in range(M):
            d = 0
            for m in range(1,len(a[l])):
#                print(ON_list)
                if ON_list[a[l][m]-1] == 1:
                    d = d + 1
            if d % 2 != p[l]:
                return 0
        ans = ans + 1
    else:
        for l in range(2):
            ON_list[count] = l
            swit(count+1, ON_list)

N, M = map(int, input().split())
a = []
for i in range(M):
    b = list(map(int, input().split()))
    a.append(b)
p = list(map(int, input().split()))
ans = 0
swit(0, [0]*N)
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
ks = []
k_max = 0
for i in range(M):
	ks_in = list(map(int, input().split()))
	k_max = max(k_max, max(ks_in[1:]))
	ks.append(ks_in)
p = list(map(int, input().split()))

A = [0, 1]
lt = list(itertools.product(A, repeat=N))
count = 0
for elem in lt:
	for i in range(M):
		sum = 0
		for j in range(len(ks[i])-1):
			sum += elem[ks[i][j+1]-1]
		if sum % 2 != p[i]:
			break
	else:
		count += 1
print(count)

Submission status: Accepted

Solution code:
import numpy as np
N,M  = map(int,input().split())
coeff = np.zeros((M,N))
for i in range(M):
    inputs = list(map(int,input().split()))
    for switch in inputs[1:]:
        coeff[i][switch-1] = 1
onlist = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    vec = [int(num) for num in bin(i)[2:]]
    fill = N - len(vec)
    vec = np.append(np.zeros(fill),np.array(vec))
#     print(vec)
    if sum(onlist == np.dot(coeff,vec)%2) == M:
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
n, m = [int(_) for _ in input().split()]
b = [[int(_) for _ in input().split()] for __ in range(m)]
p = [int(_) for _ in input().split()]
ans = 0
for i in range(2**n):
    s = format(i, '0'+str(n)+'b')
    for j in range(m):
        on = 0
        for k in range(b[j][0]) : on += int(s[b[j][k+1]-1])
        on %= 2
        if p[j] != on : break
    else : ans += 1
print(ans)

Submission status: Accepted

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

oh = list(itertools.product(range(0, 2), repeat=n))
re = 0
for i in oh:
    for j in range(m):
        c = 0
        for k in swi[j][1:]:
            c += i[k - 1]
        if c % 2 != p[j]:
            break
    else:
        re += 1
print(re)

Submission status: Accepted

Solution code:
import itertools

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


origin_list = [0, 1]
all_way = []
for i in itertools.product(origin_list, repeat=N):
    all_way.append(i)

ans = 0
for way in all_way:
    light = 0
    for i, s in enumerate(S):
        small_sum = 0
        for ss in s:
            for sss in ss:
                if way[sss - 1] == 1:
                    small_sum += 1
            if small_sum % 2 == P[i]:
                light += 1
        if light == M:
            ans += 1

print(ans)

Submission status: Accepted

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

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

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

ok = 0
for i in range(2**N):
    s = format(i,'010b')
    s = s[-N:]
    s = [int(s[i]) for i in range(len(s))]

    
    for j in range(M):
        l = s_list[j]
        cnt = 0
        for ll in l:
            if s[ll-1] == 1:
                cnt += 1
        if cnt % 2 != p[j]:
            break
        if j == M-1:
            ok += 1

print(ok)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
switch_list=[input().split() for i in range(M)]
switch_list=[[int(i[m+1]) for m in range(len(i)-1)] for i in switch_list]
P_list=input().split()
P_list=[int(i) for i in P_list]
count=0
z=N
for i in range(1 << z):
    switch=[0 for i in range(N)]
    for j in range(z):
        if ((i >> j) & 1) == 1:
            switch[j]=1
    count+=sum([sum([switch[m-1] for m in switch_list[x]])%2==P_list[x] for x in range(M)])==M
print(count)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ls = []
for _ in range(m):
  tmp = list(map(int,input().split()))[1:]
  lls = []
  for i in range(1,n+1):
    lls += [int(i in tmp)]
  ls += [lls]
p = list(map(int,input().split()))
count = 0
yyy = [0]*n
while True:
  if yyy[-1] == 2:
    break
  dd = 0
  for mi in range(m):
    c = 0
    for ni in range(n):
      c += ls[mi][ni] * yyy[ni]
    d = c%2
    dd += 1-int(d==p[mi])
  if dd == 0:
    count += 1
  yyy[0] += 1
  for j in range(0,n-1):
    if yyy[j] == 2:
      yyy[j] = 0
      yyy[j+1] += 1
print(count)

Submission status: Accepted

Solution code:
#	!/usr/bin/env python3
#	encoding: UTF-8
#	Modified: <26/May/2019 07:02:39 PM>


#	✪ H4WK3yE乡
#	Mohd. Farhan Tahir
#	Indian Institute Of Information Technology (IIIT), Gwalior


import sys


def get_array(): return list(map(int, sys.stdin.readline().split()))


def get_ints(): return map(int, sys.stdin.readline().split())


def input(): return sys.stdin.readline().strip()


def binary(n):
    global length
    op = []
    bit = 1 << length - 1
    while (bit):
        if n & bit == 0:
            op.append(0)
        else:
            op.append(1)
        bit >>= 1
    return op


def main():
    global length
    length, m = get_ints()
    d = {}
    for i in range(m):
        tmp = get_array()
        d[i] = tmp[1:]
    p = get_array()
    ans = 0
    x = 1 << length
    combinations = []
    for i in range(x):
        combinations.append(binary(i))

    for i in combinations:
        flag = True
        for j in range(m):
            cnt = 0
            for k in d[j]:
                if i[k - 1] == 1:
                    cnt += 1
            if cnt % 2 != p[j]:
                flag = False
                break
        if flag == True:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import itertools

N, M = map(int, input().split())
a = np.zeros((M,N), dtype='int8')
for n in range(M):
    for c in input().split()[1:]:
        a[n, int(c) - 1] = 1
p = np.array(list(map(int, input().split())))
count = 0
for case in itertools.product(range(2), repeat=N):
    np_case = np.array(case)
    b = np.sum(a * np_case, axis=1) % 2
    if all(p == b):
        count += 1
print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = 1
for i in range(n):
	h *= 2
t = [[] for i in range(m)]
for i in range(m):
	a = [int(x) for x in input().split()]
	k = a[0]
	for j in range(1, k + 1):
		t[i].append(a[j])
p = [int(x) for x in input().split()]
ans = 0
for i in range(h):
	g = []
	for j in range(n):
		x = (i&(1<<j))
		if x == 0:
			g.append(0)
		else:
			g.append(1)
	f = True
	for j in range(m):
		cnt = 0
		for x in t[j]:
			if g[x - 1] == 1:
				cnt += 1
		if cnt % 2 != p[j]:
			f = False
	if f:
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n, m = wi()
ks = [None] * m
for i in range(m):
    ks[i] = wi()

p = wi()

nums = [0, 1]
for balls in itertools.product(nums, repeat=n):#3**2
    tmp = 0
    for i in range(m):
        tmp = 0
        for j in range(1, len(ks[i])):
            tmp += balls[ks[i][j] - 1]
        if tmp % 2 == p[i]:
            pass
        else:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ks = []
ans = 0
for i in range(m):
    k = list(map(int,input().split()))
    ks.append([k[0],set(k[1:])])
p = list(map(int,input().split()))

for i in range(2**n):
    now = set()
    for j in range(n):
        if (i>>j)&1:
            now.add(j+1)
    t  = True
    for j in range(m):
        if len(ks[j][1]&now)%2!=p[j]:
            t = False
            break
    if t:
        ans += 1

print(ans)

Submission status: Accepted

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

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

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

result = 0
for m in range(2**N):

    flag = True
    for idx, bulb in enumerate(bulbs):
        count = 0
        for switch in bulb:
            count += (m >> (switch-1)) & 1
        if count % 2 != P[idx]:
            flag = False
            break
    if flag:
        result += 1
print(result)

Submission status: Accepted

Solution code:
n, m = [int(_) for _ in input().split()]
b = [[int(_) for _ in input().split()] for __ in range(m)]
p = [int(_) for _ in input().split()]
ans = 0
for i in range(2**n):
    s = format(i, '0'+str(n)+'b')
    for j in range(m):
        on = 0
        for k in range(b[j][0]) : on += int(s[b[j][k+1]-1])
        on %= 2
        if p[j] != on : break
    else : ans += 1
print(ans)