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 = [int(_) for _ in input().split()]
s = []
for i in range(m):
    s.append([int(_) for _ in input().split()])
p = [int(_) for _ in input().split()]

seq = [0, 1]
cand = list((itertools.product(seq,repeat = n)))
ans = 0
for c in cand:
    are_all_ok = True
    for j in range(m):
        kj = s[j][0]
        on_switch = 0
        for l in range(kj):
            on_switch += c[s[j][l + 1] - 1]
        if on_switch % 2 != p[j]:
            are_all_ok = False
    if are_all_ok == True:
        ans += 1

print(ans)

Submission status: Accepted

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

sss = [[] for i in range(m)]

for i in range(m):
  ss = list(map(int, input().split()))
  ss = ss[1:]
  sss[i] = ss
#print(sss)

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

ans = 0
for i in range(2**n):
  s = [0]*n
  for j in range(n):
    if ((i>>j) & 1):
      s[j] = 1
  for a in range(m):
    sum_ = 0
    for b in sss[a]:
      sum_ += s[b-1]
    if sum_%2 !=  ps[a]:
      break
  else:
    ans += 1
    #print(s)

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s_lists = [list(map(int, input().split()))[1:] for _ in range(m)]
P = list(map(int, input().split()))
count = 0
for i in range(2**n):
  l = 1
  for p, S in zip(P, s_lists):
    l *= (sum([int(bin(i)[2:].zfill(n)[s-1]) for s in S]) % 2 == p)
  count += l
print(count)

Submission status: Accepted

Solution code:
# coding: utf-8

def main():
	N, M = map(int, input().split())
	S = []
	for m in range(M):
		s = list(map(int, input().split()))
		S.append(s)
	p = list(map(int, input().split()))

	res = 0
	for bit in range(1<<N):
		s_check = True
		for i in range(M):
			cnt = 0
			for s in S[i][1:]:
				if bit & (1<<s-1):
					cnt += 1
			if cnt % 2 != p[i]:
				s_check = False
		if s_check == True:
			res += 1
	print(res)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import itertools

n,m=map(int, input().split())
List=[list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))

seq = [0,1] #反復する配列
v_list = list((itertools.product(seq,repeat = n))) #2進数でon/offを用意しておく

ans = 0

for i in range(2**n):
  All_ok = 0
  for j in range(m):
    on_off = 0
    for k in range(List[j][0]):
      on_off += v_list[i][List[j][k+1]-1]
    if on_off % 2 == p[j]:
      All_ok += 1
  if All_ok == m:
    ans += 1
print(ans)

Submission status: Accepted

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

count = 0
for i in range(2**n):
    allon = True
    for j in range(m):
        on = 0
        for l in range(k[j]):
            on = on +  (i >> (s[j][l]-1))&1
        if on%2 != p[j]:
            allon = False
            break
    if allon:
        count+=1
print(count)

Submission status: Accepted

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

q = []
for i in range(m):
    q.append(list(map(int, input().split())))

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

for s in range(2**n):
    judge = True
    for i in range(m):
        cnt = 0
        for j in range(1, len(q[i])):
            w = q[i][j]
            if s>>(w-1) &1 == 1:
                cnt += 1
        if cnt % 2 != p[i]:
            judge = False
    if judge:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = 0
m = 0
s = []
p = []
ans = 0

def rec(v, y):
	global n, m, p, s, ans
	if y == 0:
		# ひかる電球数
		d = 0
		for i in range(m):
			# ONスイッチ数
			c = 0
			for j in range(s[i][0]):
				if v[s[i][1 + j]-1] == 1:
					c += 1
			if c % 2 == p[i]:
				d += 1
		if d == m:
			ans += 1
		return
	rec(list(v + [0]), y-1)
	rec(list(v + [1]), y-1)

def main():
	global n, m, s, p, ans
	n, m = map(int, input().strip().split())
	s = [[] for _ in range(m)]
	for i in range(m):
		s[i] = list(map(int, input().strip().split()))
	p = list(map(int, input().strip().split()))
	rec([], n)
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
l=[[0]*n for _ in range(m)]
for i in range(m):
    ltmp=list(map(int,input().split()))
    for j in ltmp[1:]:
        l[i][j-1]=1
p=list(map(int,input().split()))
lit=list(itertools.product([0,1],repeat=n))
ans=0
for i in lit:
    atmp=[]
    for j in l:
        tmp=sum([x*y for (x,y) in zip(i,j)])%2
        atmp.append(tmp)
    if atmp==p:ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
count = 0
for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if ((i >> j) & 1):
            switch[j] = 1
    All = True
    for k in range(m):
        on = 0        
        for l in lis[k][1:]:
            on += switch[l-1]
        if on % 2 == p[k]:
            continue
        else:
            All = False
            break
    if All == True:
        count += 1
        
print(count)

Submission status: Accepted

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

for i in range(2 ** N):
    light = True

    flag = []
    for k in range(N):
        if ((i>>k)&1):
            flag.append(1)
        else:
            flag.append(0)

    for j in range(M):
        tmp = 0 
        for n in range(1, s[j][0] + 1):
            if flag[s[j][n] - 1] == 1:
                tmp += 1    
        if tmp % 2 != p[j] % 2:
            light=False
    if light:
	    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
S = []
for m in range(M):
	nums = list(map(int,input().split()))
	S.append(nums[1:])
#print(S)
p = list(map(int,input().split()))
#print(p)

ans = 0
for bits in range(1<<N):
	for m in range(M):
		on = 0
		for s in S[m]:
			on += (bits>>(s-1))&1
		if (on&1) != p[m]:
			break  
	else:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
from itertools import product

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

    all_stats = product((0,1), repeat=N)
    ans = 0
    for stat in all_stats:
        is_ok = True
        for switch_i, switch in enumerate(S):
            on_num = 0
            for i in range(len(switch)):
                if stat[switch[i]-1] == 1:
                    on_num += 1
            if on_num%2 != P[switch_i]:
                is_ok = False
                break
        if is_ok:
            ans += 1
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
mat = [[ 0 for _ in range(N)] for _ in range(M)]
for i in range(M):
    A = list(map(int, input().split()))
    for j in range(A[0]):
        mat[i][A[j+1]-1] = 1
P = list(map(int,input().split()))

def calc(X):
    for i in range(M):
        tmp = 0
        for j in range(N):
            tmp += mat[i][j] * X[j]
        if tmp % 2 != P[i]:
            return 0
    return 1

ans = 0
for i in range(2 ** N):
    X = [(i >> s) % 2 for s in range(N)]
    ans += calc(X)
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m = map(int,input().split())
seq = [0,1]
v_list = list((itertools.product(seq,repeat = n)))
ks = []
ans = 0
for i in range(m):
    ks.append(list(map(int,input().split())))
p = list(map(int,input().split()))
s = set()
for i in range(m):
    for j in range(ks[i][0]):
        s.add(ks[i][j+1])

for x in range(2**n):
    counter = 0
    for i in range(m):
        tmp = 0
        for j in range(ks[i][0]):
            tmp += v_list[x][ks[i][j+1] - 1]
        if tmp % 2 == p[i]:
            counter +=1
    if counter == m:
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import product

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

K = []

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

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



S = []

for s in product([0,1], repeat=N):
    S.append([0] + list(s))

count = 0

for s in S:
    verify = True
    for p,k in zip(P,K):
        _sum = 0
        for i in k[1:]:
            _sum += s[i]
        parity = _sum % 2
        if parity != p:
            verify = False
            break
    if verify:
        count += 1

print(count)

Submission status: Accepted

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

K_list = [0 for i in range(M)]
A_list = [[] for i in range(M)]

for i in range(M):
    ai = list(map(int, input().split()))
    K_list[i] = ai[0]
    A_list[i] = ai[1:]

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

A_sorted = sorted(A_list)


# print(K_list)
# print(A_list)
# print(P_list)

patterns = [[] for i in range(2**N)]
for i in range(2 ** N):
    temp = i
    pattern = [0 for j in range(N)]
    for j in range(N):
        pattern[j] = temp % (2)
        temp = temp//2

    patterns[i] = pattern

# print(patterns)
count = 0
for i, pattern in enumerate(patterns):  # 各パターンに
    for j, targets in enumerate(A_list):  # 各電球に
        tempsum = 0
        for k in targets:
            tempsum += pattern[k-1]
        if P_list[j] != tempsum % 2:
            break
    else:
        # print(pattern)
        count += 1

print(count)

Submission status: Accepted

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

for s in range(2**n):
    judge=True
    for i in range(m):
        cnt=0
        for j in range(1,len(q[i])):
            w=q[i][j]
            if s >> (w-1) &1 == 1:
                cnt += 1
        if cnt % 2 != p[i]:
            judge=False
    if judge:
        res += 1
print(res)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
b = []
for _k in k:
    bit = 0
    for i in _k[1:]:
        bit += 2 ** (i-1)
    b.append(bit)

res = 0
for i in range(2**n):
    for j, k in enumerate(b):
        if bin(i & k).count('1') % 2 != p[j]:
            break
    else:
        res += 1
print(res)

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())

    link = np.zeros((M, N))

    for i in range(M):
        tmp = list(map(int, input().split()))
        for j in range(1, tmp[0]+1):
            link[i][tmp[j]-1] = 1

    p = np.array(list(map(int, input().split()))).T
    # print(link.shape)
    # print(p.shape)
    ans = 0
    for i in range(2**N):
        switch = np.zeros((N, 1))
        for j in range(N):
            if i&1:
                switch[j][0] = 1
            i >>= 1
        now = np.dot(link, switch) % 2
        ok = True
        for i in range(M):
            if now[i] != p[i]:
                ok = False
                break
        if ok:
            ans += 1
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

N, M = list(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()))

ans = 0
for x in itertools.product(("on", "off"), repeat=N):
    flag = True
    for s, p in zip(S, P):
        count = 0
        for i in s:
            if x[i-1] == "on":
                count += 1
        if count % 2 != p:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(2 ** n):
  sw = [1 if ((i >> j) & 1) else 0 for j in range(n)]
  
  flg = True
  for k, light in enumerate(light_sw):
    sum_sw = 0
    for ls in light:
      sum_sw += sw[ls-1]
    if sum_sw % 2 != p[k]:
      flg = False
      break
  
  if flg:
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = [list(map(int, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
for bit in range(1 << n):
    flag = 1
    for i in range(m):
        on_count = 0
        for switch in s[i]:
            if bit & (1 << (switch-1)):
                on_count += 1
        if (on_count % 2) != p[i]:
            flag = 0
            break
    ans += flag
print(ans)

Submission status: Accepted

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

ans = 0
for bit in range(0, 1 << n):
    flag = 1
    for i in range(m):
        on_count = 0
        for switch in s[i]:
            if bit & (1 << (switch-1)):
                on_count += 1
        if (on_count % 2) != p[i]:
            flag = 0
    if flag == 1:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
s=[[0 for i in range(N+1)] for j in range(M)]
p=[0]*M
a=[0]*N
count=0
for i in range(M):
  s[i]=list(map(int,input().split()))
p=list(map(int,input().split()))
for i in range(1 << len(a)):
    a=[0]*N
    for j in range(len(a)):
        if ((i >> j) & 1) == 1:
            a[j]=1
    c=0
    for l in range(M):
      S=0
      for k in range(1,s[l][0]+1):
        S=S+a[s[l][k]-1]
      if S%2==p[l]:
        c=c+1
    if c==M:
      count=count+1
print(count)

Submission status: Accepted

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1]

def main():
    n,m = map(int,input().split())
    k = []
    s = []
    ans = 0
    
    for _ in range(m):
        tmp = [int(i) for i in input().split()]
        k.append(tmp.pop(0))
        s.append(tmp)

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

    for i in range(2**n):
        tentou=[0]*m
        b = bin(i)[2:].zfill(n)
        for i2 in range(len(s)):
            for i3 in s[i2]:
                if b[i3-1] == "1":
                    tentou[i2]+=1
        tentou = [z % 2 for z in tentou]
        if tentou == p:
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


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

def on_off(kumi, s, p):
    for i in range(M):
        atai = 0
        for j in s[i]:
            atai += kumi[j - 1]
        atai = atai % 2
        if atai != p[i]:
            return 0
    return 1

num = 0
kumi = [0 for i in range(N)]
for i in range(2**N):
    kumi = [0 for i in range(N)]
    for j in range(N):
        kumi[j] = (i & (2**j))//(2**j)
    num += on_off(kumi, s, p)

print(num)

Submission status: Accepted

Solution code:
def Switches():
    from math import log2
    N, M = map(int, input().split())
    # m行n列
    switchList = []

    # スイッチの組み合わせ取得
    for i in range(M):
        k = list(map(int, input().split()))
        k = k[1:]
        # print(k)
        switchList.append([True * (i+1 in k) for i in range(N)])
    p = list(map(int, input().split()))
    # print(switchList)
    result = 0

    # 2bit化し、条件比較を行い結果がpと等しければ正解とする
    for i in range(2**N):
        tmp = format(i, "0"+str(N)+"b")
        tmp = [int(j) for j in tmp]
        # print(tmp)
        tmp = [sum([switchList[k][j] * tmp[j] for j in range(N)]) % 2 for k in range(M)]
        if p == tmp:
            result += 1

    print(result)

if __name__ == "__main__":
    Switches()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
from itertools import combinations
import copy

def solve2():
    """
    itertools.productを使えばもっとすっきり？
    """
    import itertools as it
    N, M = list(map(int, input().split()))
    K = []
    S = []
    for i in range(M):
        _in = list(map(int, input().split()))
        K.append(_in[0])
        S.append(_in[1:])
    P = list(map(int, input().split()))

    switch_stats = it.product((0,1), repeat=N)

    ans = 0
    for stats in switch_stats:
        is_ok = True
        for i in range(M):  # すべての電球において
            on_num = 0
            for s_i in S[i]:
                on_num += 1 if stats[s_i-1]==1 else 0
            if on_num%2 == P[i]:
                continue
            else:
                is_ok = False
        
        if is_ok:
            ans += 1
    
    print(ans)


def solve():
    N, M = list(map(int, input().split()))
    K = []
    S = []
    for i in range(M):
        _in = list(map(int, input().split()))
        K.append(_in[0])
        S.append(_in[1:])
    P = list(map(int, input().split()))

    """
    全探索
    計算量 O(2^N * M * max(len(S)))
    N=10, M=10でも、1024 * 10 * 10 くらい？
    """
    def dfs(switch_stats):
        if len(switch_stats)==N:
            is_ok = True
            for i in range(M):
                on_num = 0
                for switch_i in S[i]:
                    on_num += 1 if switch_stats[switch_i-1] == 1 else 0
                if on_num%2 == P[i]:
                    continue
                else:
                    is_ok = False
                    break
            
            if is_ok:
                return 1
            else:
                return 0
        switch_stats1 = copy.deepcopy(switch_stats)
        switch_stats1.append(0)
        ret1 = dfs(switch_stats1)
        switch_stats2 = copy.deepcopy(switch_stats)
        switch_stats2.append(1)
        ret2 = dfs(switch_stats2)
        return ret1 + ret2

    ans = dfs([])
    print(ans)


if __name__ == "__main__":
    solve2()

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
from itertools import combinations
import copy

def solve():
    N, M = list(map(int, input().split()))
    K = []
    S = []
    for i in range(M):
        _in = list(map(int, input().split()))
        K.append(_in[0])
        S.append(_in[1:])
    P = list(map(int, input().split()))


    def dfs(switch_stats):
        if len(switch_stats)==N:
            is_ok = True
            for i in range(M):
                on_num = 0
                for switch_i in S[i]:
                    on_num += 1 if switch_stats[switch_i-1] == 1 else 0
                if on_num%2 == P[i]:
                    continue
                else:
                    is_ok = False
                    break
            
            if is_ok:
                return 1
            else:
                return 0
        switch_stats1 = copy.deepcopy(switch_stats)
        switch_stats1.append(0)
        ret1 = dfs(switch_stats1)
        switch_stats2 = copy.deepcopy(switch_stats)
        switch_stats2.append(1)
        ret2 = dfs(switch_stats2)
        return ret1 + ret2

    ans = dfs([])
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

sw_li = [list(map(int, input().split())) for _ in range(m)]
p_li = list(map(int, input().split()))

count = 0
for i in range(2**n):
    tf = True
    on_li = format(i, "b").zfill(n)
    
    for index, j in enumerate(sw_li):
        sum = 0
        for k in j[1:]:
            sum += int(on_li[n - k-1])
        if sum % 2 != p_li[index]:
            tf = False
            break

    if tf :
        count+= 1

print(count)

Submission status: Accepted

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

def main():                      
    N,M = map(int,input().split())
    S = [[int(s)-1 for s in input().split()[1:]] for _ in range(M)]
    P = [int(p) for p in input().split()]  
    
    ans = 0
    
    for i in range(2**N):
        state = [(i>>j)%2 for j in range(N)]
        ans += sum([sum([state[s] for s in S[j]])%2==P[j] for j in range(M)])==M
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
x = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
v=[0]*n
w=[]
z=0
count=0
ans=0
for i in range(2**n):
    for j in range(n):
        if ((i >> j) & 1):
            v[j]=1
    w.append(v)
    v=[0]*n
for i in range(2**n):
    for j in range(m):
        for k in range(1,len(x[j])):
            z+=(w[i][x[j][k]-1])
        if z%2==p[j]:
            count+=1
        z=0
    if count==m:
        ans+=1
    count=0

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

on_off = [[0], [1]]

for _ in range(N-1):
    kari = []
    for j in on_off:
        kari.append(j+[0])
        kari.append(j+[1])
    on_off = kari

for a in on_off:
    cnt = 0
    for m in range(M):
        s = 0
        for c in l[m-1]:
            s += a[c-1]
        if s % 2 == p[m-1]%2:
            cnt += 1
    if cnt == M:
        ans += 1

print(ans)

Submission status: Accepted

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

e = [[] for _ in range(n)]
# e[switch] : 接続先電球リスト

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

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

ans = 0
for bits in range(1 << n):
    cnt_on_sw = [0] * m
    # cnt_on_sw[lamp] : オンになっているスイッチ数
    for sw in range(n):
        if (bits >> sw) & 1:
            for lamp in e[sw]:
                cnt_on_sw[lamp] += 1
    cnt_on_sw = tuple(map(lambda x: x % 2, cnt_on_sw))
    if cnt_on_sw == p:
        ans += 1
print(ans)

Submission status: Accepted

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

ans, n = 0, 2 ** N
for i in range(n):
    for s_, p_ in zip(s, p):
        if bin(i & s_).count("1") % 2 != p_:
            break
    else:
        ans += 1
        
print(ans)

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):
    all_on = True
    for j in range(M):
        n_on = 0
        for s in ks[j][1:]:
            if (i >> (s - 1)) & 1:
                n_on += 1
        if n_on % 2 != p[j]:
            all_on = False
    if all_on:
        ans += 1
print(ans)

Submission status: Accepted

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

for i in range(2**n): #スイッチの付き方全通り
    on=[]
    onlight=0
    for j in range(n): #何個目のスイッチがついてるかonに記憶
        if (i>>j)&1:
            on.append(j+1)
    for j in range(m): #j番目の電球はこの条件で付くか
        count=0 #ついているスイッチの数
        for k in range(info[j][0]): #j番目の電球とつながっているスイッチがこの条件ではついているか
            if info[j][k+1] in on:
                count+=1
        if count%2==light[j]:
            onlight+=1
    if onlight==m:
        ans+=1
        #print(on)
        
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
lamps = []
for i in range(0, M):
	inpt = list(map(int, input().split()))
	lamps.append(list(map(lambda v: v-1, inpt[1:])))
onoff = list(map(int, input().split()))
cnt = 0
for i in range(0, 2**N):
	m = i
	drived = []
	for j in range(0, M):
		drived.append(0)
	for j in range(0, N):
		if m % 2 == 1:
			for k in range(0, M):
				if j in lamps[k]:
					drived[k] += 1
		m //= 2
	flag = True
	for j in range(0, M):
		if onoff[j] != drived[j]%2:
			flag = False
			break
	if flag:
		cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np

N, M = map(int, input().split())
bulb = np.zeros((M, N), dtype=bool)

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

    for s in tmp[1:]:
        bulb[i][s - 1] = True

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

ret = 0
for k in range(2 ** N):
    count = np.zeros(M, dtype=int)
    for i in range(N):
        state = k & (1 << i) > 0
        for j in range(M):
            if state and bulb[j][i]:
                count[j] += 1

    f = True
    for c, p in zip(count, P):
        if c % 2 != p:
            f = False
            break

    if f:
        ret += 1

print(ret)

Submission status: Accepted

Solution code:
nm = input().split(" ");
n = int(nm[0]);
m = int(nm[1]);
k = [0]*m;
s = [[0]*n for i in range(m)];

for i in range(m) :
	st = input().split(" ");
	k[i] = int(st[0]);
	for j in range(k[i]) :
		s[i][j] = int(st[j+1]);
p = input().split(" ");
for i in range(m) :
	p[i] = int(p[i]);

ans = 0;
for i in range(2**n) :
	ok = 1;
	for j in range(m) :
		count_s = 0;
		for l in range(k[j]) :
			if ((i >> (n-s[j][l])) & 1) :
				count_s += 1;
		if count_s % 2 != p[j] :
			ok = 0;
	if bool(ok) :
		ans += 1;

print(ans);

Submission status: Accepted

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

def main():
	n, m = map(int, input().strip().split())
	A = [0] * n
	for i in range(m):
		sw = list(map(int, input().strip().split()))[1:]
		for e in sw:
			e -= 1
			A[e] |= 1 << i

	pl = list(map(int, input().strip().split()))
	p = 0
	for i, e in enumerate(pl):
		p |= e << i
		# p = p << i

	j = 0
	ans = 0
	while j < (1 << n):
		t = 0
		for i in range(n):
			if j >> i & 1:
				t ^= A[i]
		if t == p:
			ans += 1
		j += 1

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

v = []
p = []
count = 0
m = 0
def rec(l, n):
	global count
	if len(l) == n:
		c = 0
		st = set()
		for i in range(n):
			if l[i] == 1:
				st.add(i + 1)
		for k, sw in enumerate(v):
			# print(st)
			if len(sw.intersection(st)) % 2 != p[k]:
				return
		# print("c: {}".format(c))
		count += 1
		# print(l)
		return
	l.append(0)
	rec(list(l), n)
	l.pop()
	l.append(1)
	rec(list(l), n)

def main():
	global v
	global p
	global m
	n, m = map(int, input().strip().split())
	for i in range(m):
		tmp = list(map(int, input().strip().split()))
		v.append(set(tmp[1:]))
	p = list(map(int, input().strip().split()))
	rec([], n)
	print(count)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

v = []
p = []
count = 0
m = 0
def rec(l, n):
	global count
	if len(l) == n:
		c = 0
		for k, sw in enumerate(v):
			st = set()
			for i in range(n):
				if l[i] == 1:
					st.add(i + 1)
			# print(st)
			if len(sw.intersection(st)) % 2 != p[k]:
				return
		# print("c: {}".format(c))
		count += 1
		# print(l)
		return
	l.append(0)
	rec(list(l), n)
	l.pop()
	l.append(1)
	rec(list(l), n)

def main():
	global v
	global p
	global m
	n, m = map(int, input().strip().split())
	for i in range(m):
		tmp = list(map(int, input().strip().split()))
		v.append(set(tmp[1:]))
	p = list(map(int, input().strip().split()))
	rec([], n)
	print(count)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

ans = 0

for mask in range(0,1<<N):
    flag = True
    for i, line in enumerate(S):
        cnt = 0
        for s in line:
            if ((mask >> (s-1) & 1)):
                cnt += 1
        if cnt % 2 != P[i]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

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

v = []
p = []
count = 0
m = 0
def rec(l, n):
	global count
	if len(l) == n:
		c = 0
		for k, sw in enumerate(v):
			st = set()
			for i in range(n):
				if l[i] == 1:
					st.add(i + 1)
			# print(st)
			if len(sw.intersection(st)) % 2 == p[k]:
				c += 1
		# print("c: {}".format(c))
		if c == m:
			count += 1
		# print(l)
		return
	l.append(0)
	rec(list(l), n)
	l.pop()
	l.append(1)
	rec(list(l), n)

def main():
	global v
	global p
	global m
	n, m = map(int, input().strip().split())
	for i in range(m):
		tmp = list(map(int, input().strip().split()))
		v.append(set(tmp[1:]))
	p = list(map(int, input().strip().split()))
	rec([], n)
	print(count)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def can(state, m, bulb, p):
	"""For given switch state, determine all bulbs are turned on."""
	for i in range(m):
		cnt = 0 #how many switches are on.
		for j in bulb[i]:
			if (state & (1<<(j-1))):
				cnt += 1
		if cnt % 2 != p[i]:
			return False
	return True

n, m = map(int, input().split())
bulb = []
for i in range(m):
	l = list(map(int, input().split()))
	l = l[1:]
	bulb.append(l)
p = list(map(int, input().split()))

ans = 0
for i in range(1<<n):
	if can(i, m, bulb, p):
		ans += 1
print(ans)