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())
X=[]
for i in range(M):
    X.append(list(map(int, input().split())))
P=list(map(int, input().split()))
ans=0

key='{:0'+str(N)+"b}"
for k in range(2**N):
    
    switch=list(key.format(k))
    for i in range(M):
        odd=1
        even=0
        if P[i]==1:
            odd=0
            for j in range(X[i][0]):
                odd+=int(switch[ X[i][j+1]-1] )
            if odd%2==0:
                break
            
        else:
            even=0
            for j in range(X[i][0]):
                even+=int(switch[ X[i][j+1]-1] )
            if even%2==1:
                break
    
    if odd%2==1 and even%2==0:
        ans+=1
        #print(X[i],switch,odd,even)
            
print(ans)

Submission status: Accepted

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

k = []
s = []
for _ in range(M):
    temp = list(map(int, input().split()))
    k.append(temp[0])
    s.append(temp[1:])

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

# bit全探索
c = 0
for i in range(2 ** N):
    b = []
    for j in range(N):
        b.append(i >> j & 1 > 0)
    flag = True
    for j in range(M):
        cc = 0
        for ss in s[j]:
            if b[ss-1]:
                cc += 1
        if cc % 2 != p[j]:
            flag = False
            break
    if flag:
        c += 1
print(c)

Submission status: Accepted

Solution code:
import numpy as np
import itertools as ittr

def test_switch(e_balls, sw, p):
    for i, e_ball in enumerate(e_balls):
        n_on = np.sum(sw[e_ball - 1])
        
        if p[i] != (n_on % 2):
            return False
    
    return True

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

e_balls = []

for m in range(M):
    e_balls.append(np.asarray([int(si) for si in input().split()[1:]]))

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

cnt = 0

for sw in ittr.product([0, 1], repeat = N):
    if test_switch(e_balls, np.array(sw), p):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
import itertools as ittr

def test_switch(e_balls, sw, p):
    for i, e_ball in enumerate(e_balls):
        n_on = np.sum(sw[e_ball - 1])
        
        if p[i] != (n_on % 2):
            return False
    
    return True

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

e_balls = []

for m in range(M):
    i = input().split()
    s = [int(si) for si in i[1:]]
    e_balls.append(np.asarray(s))

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

cnt = 0

for sw in ittr.product([0, 1], repeat = N):
    if test_switch(e_balls, np.array(sw), p):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
import itertools as ittr

def test_switch(e_balls, sw, p):
    for i, e_ball in enumerate(e_balls):
        si = sw[e_ball - 1]
        
        if p[i] != (np.sum(si == 1) % 2):
            return False
    
    return True

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

e_balls = []

for m in range(M):
    i = input().split()
    s = [int(si) for si in i[1:]]
    e_balls.append(np.asarray(s))

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

cnt = 0

for sw in ittr.product([0, 1], repeat = N):
    if test_switch(e_balls, np.array(sw), p):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
import itertools as ittr

def test_switch(e_balls, sw, p):
    for i, e_ball in enumerate(e_balls):
        eb = np.asarray(e_ball)
        si = sw[eb - 1]
        
        if p[i] != (np.sum(si == 1) % 2):
            return False
    
    return True

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

e_balls = []

for m in range(M):
    i = input().split()
    s = [int(si) for si in i[1:]]
    e_balls.append(s[:])

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

cnt = 0

for sw in ittr.product([0, 1], repeat = N):
    if test_switch(e_balls, np.array(sw), p):
        cnt += 1

print(cnt)

Submission status: Accepted

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

li=[]
for i in range(1, m+1):
    s=list(map(int, input().split()))
    s.pop(0)
    li.append(s)

if m==1:
    p = [int(input())]
else:
    p = list(map(int, input().split()))
#print(li)
#print(p)

def check(g,en):
    stack = ["1", "0"]
    candi = []
    while stack:
        cur = stack.pop()
        if len(cur) == en:
            candi.append(cur)
            continue
        for i in g[len(cur)+1]:
            tmp = cur+i
            stack.append(tmp)
    return candi

g={}
for i in range(0,n+1):
    g[i]=["1", "0"]

ans = 0
#print(check(g,n))
for i in check(g,n):
    flag=0
    for j in range(m):
        tmp=0
        for k in range(0,len(li[j])):
            tmp += int(i[li[j][k]-1])
        if tmp % 2 != p[j]:
            flag=1
            break
    if flag==0:
        #print(i)
        ans += 1

print(ans)

Submission status: Accepted

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


for i in range(1 << n):
    check = True
    for j in range(m):
        cnt = 0
        for l in range(1, len(k[j])):
            cnt += (i>>(k[j][l]-1))&1
        if cnt%2 != p[j]:
            check = False
    if check == True:
        ans += 1

print (ans)

Submission status: Accepted

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

ans = 0

for i in range(1 << N):
    cnt_on = [0]*M
    for j in range(N):
        if ((i >> j) & 1) == 1:
            for m in range(M):
                cnt_on[m] += ks[m][1:].count(j+1)

    c = 0
    for m in range(M):
        if cnt_on[m]%2 == p[m]:
            c += 1
    
    if c == M:
        ans += 1


print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, m = map(int, input().split())
s = [None] * m
for i in range(m):
    k, *s[i] = map(lambda x: int(x) - 1, input().split())
p = list(map(int, input().split()))
ans = 0
for b in range(1 << n):
    f = True
    for i in range(m):
        cnt = sum(b >> x & 1 for x in s[i])
        f &= (cnt % 2 == p[i])
    ans += f
print(ans)

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    bulbs = []
    for _ in range(M):
        b = tuple(map(int, input().split()))
        bulbs.append(b[1:])

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

    ans = 0
    for switch in range(2**N):
        check = [0] * M
        for i, bulb in enumerate(bulbs):
            cnt = 0
            for b in bulb:
                if switch >> (b - 1) & 1:
                    cnt += 1

            if cnt % 2 == P[i]:
                check[i] = True
            else:
                check[i] = False

        if all(check):
            ans += 1

    return ans


if __name__ == '__main__':
    print(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()))

ans=0
for i in range(1<<n):
    isok=True
    for j in range(m):
        cnt = 0
        for k in range(1,len(ks[j])):
            cnt += (i>>(ks[j][k]-1))&1
        if cnt%2 != p[j]:
            isok = False
            break
    if isok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
(n,m),*s,p=[list(map(int,t.split()))for t in open(0)]
a=0
for i in range(1<<n):
 c=[0]*m
 for j in range(n*m):c[j%m]^=i>>j//m&(j//m+1in s[j%m][1:])
 a+=c==p
print(a)

Submission status: Accepted

Solution code:
(n,m),*s,p=[list(map(int,t.split()))for t in open(0)]
a=0
for i in range(1<<n):
 c=[0]*m
 for j in range(n*m):c[j%m]^=i>>j//m&(j//m+1in s[j%m][1:])
 a+=all(j==i for i,j in zip(c,p))
print(a)

Submission status: Accepted

Solution code:
[input_n, input_m] = map(int, input().split())

input_ks = [list(map(int, input().split())) for i in range(input_m)]
input_p = list(map(int, input().split()))

switch_list = [[bool(i & 2 ** j) for j in range(input_n)]
               for i in range(2 ** input_n)]

count = len(switch_list)
for switch in switch_list:
    for m in range(input_m):
        if ((sum(switch[l - 1] for l in input_ks[m][1:])-input_p[m]) % 2):
            count -= 1
            break
print(count)

Submission status: Accepted

Solution code:
(n,m),*s,p=[list(map(int,t.split()))for t in open(0)]
a=0
for i in range(1<<n):
 c=[0]*m
 for j in range(n*m):c[j%m]+=i>>j//m&(j//m+1in s[j%m][1:])
 a+=all(j==i%2for i,j in zip(c,p))
print(a)

Submission status: Accepted

Solution code:
(n,m),*s,p=[list(map(int,t.split()))for t in open(0)]
a=0
r=range
for i in r(1<<n):
 c=[0]*m
 for j in r(n*m):j,k=j//m,j%m;c[k]+=i>>j&(j+1in s[k][1:])
 a+=all(j==i%2for i,j in zip(c,p))
print(a)

Submission status: Accepted

Solution code:
(n,m),*s,p=[list(map(int,t.split()))for t in open(0)]
a=0
r=range
for i in r(1<<n):
 c=[0]*m
 for j in r(n):
  for k in r(m):c[k]+=i>>j&(j+1in s[k][1:])
 a+=all(j==i%2for i,j in zip(c,p))
print(a)

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
n,m=I()
*s,p=eval('I(),'*-~m)
a=0
r=range
for i in r(1<<n):
 c=[0]*m
 for j in r(n):
  for k in r(m):c[k]+=i>>j&(j+1in s[k][1:])
 a+=all(j==i%2for i,j in zip(c,p))
print(a)

Submission status: Accepted

Solution code:
[input_n, input_m] = map(int, input().split())

input_ks = [list(map(int, input().split())) for i in range(input_m)]
input_p = list(map(int, input().split()))

switch_list = [[bool(i & 2 ** j) for j in range(input_n)]
               for i in range(2 ** input_n)]

count = 0
for switch in switch_list:
    switchPattern = []
    for m in range(input_m):
        switchPattern.append(sum(switch[l - 1] for l in input_ks[m][1:]) %2 == input_p[m])
    if (all(switchPattern)):
        count += 1
print(count)

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
n,m=I()
s=eval('I(),'*m)
p=I()
a=0
r=range
for i in r(1<<n):
 c=[0]*m
 for j in r(n):
  for k in r(m):c[k]+=i>>j&(j+1in s[k][1:])
 a+=all(j==i%2for i,j in zip(c,p))
print(a)

Submission status: Accepted

Solution code:
[N,M] = list(map(int,input().split()))
K = []
S = []
for i 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 ms in range(1 << N):
  cnt = 0
  for i in range(M):
    sum = 0
    for v in S[i]:
      if (ms >> (v-1)) & 1:
        sum += 1
    if sum % 2 == P[i]:
      cnt += 1
  if cnt == M:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
k = []
lis = []
P = []
for _ in range(M):
    x = list(map(int, input().split()))
    k.append(x[0])
    lis.append(x[1:])
for p in map(int, input().split()):
    P.append(p)
count = 0
for i in range(2**N):
    flag = True
    string = str(bin(i)[2:])[::-1]
    for index in range(M):
        total = 0
        for s in lis[index]:
            if s <= len(string):
                if string[s - 1] == '1':
                    total += 1
        if total % 2 != P[index]:
            flag = False
            break
    if flag:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
mat = np.zeros((M,N))
for i in range(M):
    slist = list(map(int, input().split()))
    for j in slist[1:]:
        mat[i,j-1] = 1
plist = list(map(int, input().split()))
mat = np.append(mat, np.array([plist]).T, axis=1)

def power_set(N):
    p_sets = [[]]
    item = [i for i in range(N)]
    for i in item:
        temp = []
        for j in p_sets:
            temp += [ j+[i] ]
        p_sets += temp
    return p_sets

ret = 0
for swi in power_set(N):
    tm_mat = mat[:,swi+[N]]
    if sum([(np.sum(i) % 2) == 0 for i in tm_mat]) == M:
        ret += 1
print(ret)

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:
N, M = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(M)]  #sの各要素のはじめはk
p = list(map(int, input().split()))
ans = 0

# 0をoffとして2進数でパターンを表現

for i in range(2 ** N):
	ptn = bin(i)[2:].rjust(N, "0")  # N桁の2進表現にする
	light = True  # 着目している電球が点灯していないときはこれがFalseになる
	for j in range(M):
		tmp = 0  # 着目している電球について、スイッチのonの個数をカウントする
		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:
import math
from functools import reduce
from collections import deque

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,m = get_nums_l()

lamps = []
for i in range(m):
    lamps.append(get_nums_l()[1:])

p = get_nums_l()

ans = 0
# nビット全パターン
for x in range(2**n):
    ok = True
    for ri,r in enumerate(lamps):
        count = 0
        for a in r:
            count += x&(2**(a-1)) > 0
        if count%2 != p[ri]:
            ok = False
            break
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

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

# 0をoffとして2進数でパターンを表現

for i in range(2 ** N):
	x = bin(i)[2:].rjust(N, "0")
	light = True  # 着目している電球が点灯していないときはこれがFalseになる
	for j in range(M):
		tmp = 0  # 着目している電球について、スイッチのonの個数をカウントする
		for k in range(1, s[j][0] + 1):
			if x[s[j][k] - 1] == "1":
				tmp += 1
		if tmp % 2 != p[j] % 2:
			light = False
	if light:
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
# ABC128C - Switches
import sys
from itertools import product

input = sys.stdin.readline


n, m = list(map(int, input().rstrip().split()))
lst = [list(map(int, input().rstrip().split())) for _ in range(m)]
con = list(map(int, input().rstrip().split()))
ans = 0
for i in product(range(2), repeat=n):
    cnt = 0
    for j in range(m):
        ons = 0
        for k in lst[j][1:]:
            if i[k - 1] == 1:
                ons += 1
        if ons % 2 == con[j]:
            cnt += 1
    if cnt == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc128
# -*- coding: utf-8 -*-

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

k = []
s = []
for i in range(m):
    x = list(map(int,input().split()))
    k.append(x[0])
    y = []
    for j in range(x[0]):
        y.append(x[j+1])
    s.append(y)

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

cnt = 0
for i in range(1024):
    x = format(i,"010b")[::-1]
    if n < 10 and x[n] == "1":
        break
    
    for j in range(m):
        tmpSum = 0
        for k in s[j]:
            tmpSum += int(x[k-1])
        if tmpSum%2 is not p[j]:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split(" "))
botlist = []
ans = 0
for n in range(M):
    bot = list(map(int, input().split(" ")))
    
    botlist.append(bot)
#botlist
plist = list(map(int, input().split(" ")))

pushlist = [[]for i in range(2**N)]

for p in range(N):
    for q in range(2**N):
        if q % (2**(p+1)) <2**p:
            pushlist[q].append(0)
        else:
            pushlist[q].append(1) 

for A in pushlist:
    #print(A)
    g = 0
    faa = 0
    for B in botlist:
        g += 1
        cou = 0
        for c in range(B[0]):
            cou += A[B[c+1]-1]

        if cou % 2 == plist[g-1]:
            faa += 1
    if faa == M:
        ans += 1
    

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, M = map(int, input().split())
lamplist = [0]*M
for i in range(M):
    A = list(map(int, input().split()))
    lamplist[i] = A
oddeven_ans = list(map(int, input().split()))

switch = np.zeros(N)
ans = 0
numofswitch = np.zeros(M)

for s in range(M):
    numofswitch[s] = lamplist[s][0]
    del lamplist[s][0]

for j in range(2 ** N):
    ansflag = 0

    for k in range(N):
        switch[k] = j % 2
        j //= 2
    for p in range(M):
        numofshining = 0
        for r in lamplist[p]:
            if switch[r-1] == 1:
                numofshining += 1

        if numofshining % 2 != oddeven_ans[p]:
            ansflag = 1
    if ansflag == 0:
        ans += 1

print("{}".format(ans))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
k = []
lis = []
P = []
for _ in range(M):
    x = list(map(int, input().split()))
    k.append(x[0])
    lis.append(x[1:])
for p in map(int, input().split()):
    P.append(p)
count = 0
for i in range(2**N):
    flag = True
    Switch = [False] * (N+1)
    string = str(bin(i)[2:])
    for index, s in enumerate(string[::-1]):
        if s == '1':
            Switch[index + 1] = True
    for index in range(M):
        total = 0
        for s in lis[index]:
            if Switch[s]:
                total += 1
        if total % 2 != P[index]:
            flag = False
            break
    if flag:
        count += 1
print(count)

Submission status: Accepted

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

p_list = list(map(int, input().split()))
count = 0
for i in range(2**n):
  s_str = format(i, 'b').zfill(n)
  for j in range(len(k_list)):
    on = 0
    for s in k_list[j]:
      on += int(s_str[s-1])
    if on % 2 != p_list[j]:
      break
  else:
    count += 1

print(count)

Submission status: Accepted

Solution code:
import itertools

n, m = [int(i) for i in input().split()]
s = []
for i in range(m):
    _, *s_ = [int(i) for i in input().split()]
    s.append(s_)
p = [int(i) for i in input().split()]

answer = 0
for i_list in itertools.product([0,1],repeat=n):

    電気点灯 = 0
    for j in range(m):
        オンになっているスイッチの個数 = 0
        for k in range(len(s[j])):
            if i_list[s[j][k]-1] == 1:
                オンになっているスイッチの個数 += 1
        if オンになっているスイッチの個数 % 2 == p[j]:
            電気点灯 += 1

    if 電気点灯 == m:
        answer += 1

print(answer)

Submission status: Accepted

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

ans = 0
for i in range(1 << N):
  tmp = 1
  for j, b in enumerate(KS):
    if sum([1 for bb in b[1:] if (i >> (bb - 1)) & 1 == 1])%2 != P[j]:
      tmp = 0
      break
  if tmp:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

N, M = map(int, input().split())
L = []

for i in range(M):
    k = list(map(int, input().split()))
    l = [i-1 for i in k[1:]]  # indexを渡していることに注意
    L.append(l)

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


def calc(idx, lampe):
    if idx == N:
        ans = 0
        for l in range(M):
            if sum([lampe[v] for v in L[l]]) % 2 != p[l]:
                return 0

        return 1

    ans = 0
    ans += calc(idx+1, lampe)
    lampe2 = copy.copy(lampe)
    lampe2[idx] = 1
    ans += calc(idx+1, lampe2)
    return ans


ans = calc(0, [0]*N)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import copy

N, M = map(int, input().split())
L = []

for i in range(M):
    k = list(map(int, input().split()))
    l = [i-1 for i in k[1:]]  # indexを渡していることに注意
    L.append(l)

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


def calc(idx, lampe):
    if idx == N:
        ans = 0
        for l in range(M):
            s = [lampe[v] for v in L[l]]
            if sum(s) % 2 != p[l]:
                return 0

        return 1

    ans = 0
    ans += calc(idx+1, lampe)
    lampe2 = copy.copy(lampe)
    lampe2[idx] = 1
    ans += calc(idx+1, lampe2)
    return ans


ans = calc(0, [0]*N)
print(ans)

Submission status: Accepted

Solution code:
import itertools

n, m = [int(i) for i in input().split()]
s = []
for i in range(m):
    _, *s_ = [int(i) for i in input().split()]
    s.append(s_)
p = [int(i) for i in input().split()]

answer = 0
for i0, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10 in itertools.product(range(2), range(2), range(2),range(2), range(2), range(2),range(2), range(2),range(2), range(2), range(2)):
    #i_list = [i0, i1, i2, i3, i4, i5, i6, i7, i8, i9, i10]
    i_list = [i10, i9, i8, i7, i6, i5, i4, i3, i2, i1, i0]
    #print(i_list)
    if i_list[n] == 1:
        break

    電気点灯 = 0
    for j in range(m):
        オンになっているスイッチの個数 = 0
        for k in range(len(s[j])):
            if i_list[s[j][k]-1] == 1:
                オンになっているスイッチの個数 += 1
        if オンになっているスイッチの個数 % 2 == p[j]:
            電気点灯 += 1

    if 電気点灯 == m:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
import itertools

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

s= []
#s.append([0])

for i in range(m):
	ss = list(map(int, input().split()))
	temp_ss = []
	for i in range(1, len(ss)):
		temp_ss.append(ss[i]-1)
	s.append(temp_ss)
p = list(map(int, input().split()))

ans = 0

#print(s)
#print(p)
#print(list(combi))

for c in itertools.product([0,1], repeat=n):
	#print(c)
	is_ans = True
	for i in range(len(s)):
		if(sum([c[a] for a in s[i]])) % 2 != p[i]:
			is_ans = False
			break

	if(is_ans):
		ans += 1
print(ans)

Submission status: Accepted

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

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

combi = 0
for i in range(1<<N):
    flag = True
    for j, switch in enumerate(lights):
        if sum([1 for s in switch if (i>>(s-1)) & 1 == 1])%2 != p[j]:
            flag = False
            break
    if flag:
        combi += 1

print(combi)

Submission status: Accepted

Solution code:
#C問題
N,M = map(int,input().split())
K = []
S = []
for i in range(M):
    ks =list(map(int,input().split()))
    ss = []
    kk = ks[0]
    K.append(kk)
    for j in range(kk):
        ss.append(ks[j+1])
    
    S.append(ss)
P = list(map(int,input().split()))
Bit = 2**N
ans = 0
for i in range(Bit):
    b = bin(i)
    b = b.lstrip("0b")
    lenb = len(b)
    j = 0
    for j in range(N-lenb):
        b = "0"+b
        
    sw = []
    j = 0

    for j in range(N):
        if b[j] == "1":
            sw.append(1)
        else:
            sw.append(0)
    
    j = 0
    flag = 0
    for j in range(M):
        cond = P[j]
        now = 0
        for k in range(K[j]):
            now+=sw[S[j][k]-1]
            
        if now%2 == cond:
            pass
        else:
            flag = 1
            break
            
    if flag == 0:
        ans+=1
    
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
dict = {}
for i in range(M):
    l = list(map(int, input().split()))
    for j in range(l[0]):
        if l[j+1] in dict:
            dict[l[j+1]].append(i)
        else:
            dict[l[j+1]] = [i]
ps = list(map(int, input().split()))
n = 1 << N
ans = 0
while n:
    cnt = 0
    ks =[0]*M
    for i in range(N):
        if n >> i & 1:
            if i+1 in dict:
                for k in dict[i+1]:
                    ks[k] += 1
    for j in range(M):
        if ks[j] % 2 == ps[j]:
            cnt += 1
    if cnt == M:
        ans += 1
    n -= 1
print(ans)

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
n,m=I()
s=eval('I(),'*m)
p=I()
a=0
r=range
for i in r(1<<n):
 c=[0]*m
 for j in r(n):
  for k in r(m):c[k]+=i>>j&1and j+1in s[k][1:]
 a+=all(j==i%2for i,j in zip(c,p))
print(a)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
k, lights = [], []
for i in range(M):
    tmp = [int(j) for j in input().split()]
    k.append(tmp[0])
    lights.append(tmp[1:])
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(k[i]):
            s += (switch >> (lights[i][j] - 1)) & 0b1
        if s % 2 != p[i]:
            flag = False
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

l = [0, 1]
on_off = list(itertools.product(l, repeat=N))
ans = 0
for idx,i in enumerate(on_off):
  ans_lst = []
  for j in range(M):
    sum = 0
    for k in all_lst[j]:
      sum += i[k-1]
    ans_lst.append(sum % 2)
  if(ans_lst == lst_p):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = (int(i) for i in input().split())
  
dict_rel = dict()
for i in range(M):
  dict_rel[i+1] = [int(j) for j in input().split()][1:]
list_cond = [int(i) for i in input().split()]

#print(dict_rel)
#print(list_cond)

list_pattern = [[] for j in range(2**N)]

for i in range(len(list_pattern)):
  b = bin(i)[2:].zfill(N)
  list_pattern[i] = [int(k) for k in b]

#print(list_pattern)

num_full = 0
for pattern in list_pattern:
  flg = True
  for light in dict_rel.keys():
    num_on = 0
    for i in dict_rel[light]:
      if pattern[i-1] == 1:
        num_on += 1
    if list_cond[light-1] != num_on%2:
      flg = False
      #break
  if flg == True:
    num_full += 1

print(num_full)

Submission status: Accepted

Solution code:
from itertools import product
N, M = list(map(int, input().split()))
k_list = []
s_list_list = []
for _ in range(M):
    k, *s_list = list(map(int, input().split()))
    k_list.append(k)
    s_list_list.append(s_list)
p_list = list(map(int, input().split()))

def light_check(switch_pattern):
    return all([
        sum([int(switch_pattern[s-1]) for s in s_list]) % 2 == p
        for s_list, p in zip(s_list_list, p_list)
    ])

cnt = 0
for switch_pattern in product('01', repeat=N):
    if light_check(switch_pattern):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
k = []
for i in range(M):
    tmp = [int(j) for j in input().split()]
    k.append(tmp)

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

onoff = [0, 1]
kouho = list(itertools.product(onoff, repeat=N))

ans = 0
for li in kouho:
    flag = True
    for i in range(M):
        end = k[i][0]+1
        sum = 0
        for j in range(1, end):
            sum += li[k[i][j]-1]
        if sum % 2 != p[i]:
            flag = False
            break
    if flag == True:
        ans += 1

print(ans)

Submission status: Accepted

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


ans = 0
for i in range(2**n):
    bina = list(reversed(format(i, '010b')))
    flag = True
    for j in range(m):
        count = 0
        sw = ks[j]
        for k in range(1,len(sw)):
            if bina[sw[k]-1] == "1":
                count += 1
        if count % 2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def statecheck(state,kS,p):
  status = True
  i = 0
  for ks in kS:
    check_num = 0
    for s in ks[1:]:
      check_num = (check_num + state[s-1])
    if p[i] != check_num%2:
      status = False
      break
    i+=1
  return status

N, M= (int(i) for i in input().split())

kS = [list(map(int, input().split())) for _ in range(M)]
p = [int(i) for i in input().split()]

ans = 0

for i in range(2**N):
  state = list(format(i, 'b').zfill(N))
  state = list(map(int,state))
  if statecheck(state,kS,p):
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math
N, M = map(int, input().split())
s=[] #kとs
num=pow(2,N+1)-1
flag=True
count=0
for i in range(M):
  s2=list(map(int,input().split()))
  s.append(s2) #s[0]がk, それ以降はs
p=list(map(int,input().split())) #p
for i in range(pow(2,N)): # スイッチの全てのパターン
  if N<10:
    S=format(num, '0'+str(N)+'b')
  else:
    S=format(num, str(N)+'b')
  S2=list(S)
  flag=True
  for j in range(M): #各電球を見ていく
    sum=0
    for k in range(s[j][0]):#電球iのonの和
      sum=sum+int(S[s[j][k+1]])
    if sum%2 != p[j]:
      flag=False
  if flag==True:
    count=count+1
  num=num-1
print(count)

Submission status: Accepted

Solution code:
import itertools

def main():
    n,m=list(map(int,input().split(' ')))
    swich_all=list(itertools.product([0,1],repeat=n))
    swich=[]
    cnt=0
    for i in range(m):
        swich.append(list(map(int,input().split(' '))))
    check_p=list(map(int,input().split(' ')))
    for i in swich_all:
        check = []
        for j in range(m):
            tmp = 0
            for k in swich[j][1:]:
                tmp += i[k-1]
            check.append(tmp%2)
        if check == check_p:
            cnt +=1

    print(cnt)

main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=eval('list(map(int,input().split()[1:])),'*m)
*p,=map(int,input().split())
a=0
r=range
for i in r(1<<n):
 c=[0]*m
 for j in r(n):
  for k in r(m):c[k]+=i>>j&1and j+1in s[k]
 a+=all(j==i%2for i,j in zip(c,p))
print(a)

Submission status: Accepted

Solution code:
from itertools import product
n,m = (int(i) for i in input().split())
x,ans = [],0
for i in range(m):
    y = [int(i)-1 for i in input().split()]
    x.append(y[1:])
z = [int(i) for i in input().split()]
def check(q):
    p = 0
    for i in range(m):
        num = 0
        for j in x[i]:
            if q[j]: num+=1
        if num%2==z[i]: p+=1
    return p==m
for i in product((0,1), repeat=n):
    if check(i): ans+=1
print(ans)