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

res = 0
for bit in range(1 << n):
  flag = 0
  for i in range(m):
    count = 0
    for j in range(1, l[i][0]+1):
      if (1 << (l[i][j] - 1)) & bit:
        count += 1
      else:
        pass
    if count % 2 == p[i]:
      flag = 1
    else:
      flag = 0
      break
  if flag:
    res += 1
  else:
    pass

print(res)

Submission status: Accepted

Solution code:
light=input().split(' ')
line=[]
for i in range(int(light[1])):
  line.append(input().split(' ')[1:])
  
switch=input().split(' ')

length=2**int(light[0])
count=0
for i in range(length):
  li=[]
  for j in range(int(light[0]),0,-1):
    if i%2 == 1:
      li.append(1)
    else:
      li.append(0)
      
    i//=2

  flg=True
  for j in range(int(light[1])):
    light_count=0
    for k in line[j]:
      if li[int(k)-1]==1:
        light_count+=1
        
    if light_count%2!=int(switch[j]):
      flg=False
      break

  if flg:
    count+=1
    
print(count)

Submission status: Accepted

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

N, M = map(int, input().split())
sm = [list(map(int, input().split()))[1:] for _ in range(M)]
pm = list(map(int, input().split()))


tmp = [[0] * N for _ in range(M)]
for i in range(len(sm)):
    for si in sm[i]:
        tmp[i][si - 1] = 1
sm = tmp


def check(state):
    ret = 0
    for i, k in enumerate(sm):
        c = 0
        for j, s in enumerate(state):
            c += k[j] if s == '1' else 0
        if (c % 2) != pm[i]:
            break
    else:
        ret = 1

    return ret


def count(state):
    ret = 0
    if len(state) == N:
        ret += check(state)
    else:
        for s in '01':
            ret += count(state + s)
    return ret


print(count(''))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
switch = [0] * m
for i in range(m):
    s = list(map(int, input().split()))
    for j in s[1:]:
        switch[i] |= 1 << (j - 1)
p = list(map(int, input().split()))
ans = 0
for bit in range(1 << n):
    for i in range(m):
        if bin(bit & switch[i]).count('1') % 2 != p[i]:
            break
    else:
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
import sys

def all_lighted(input, mod, pattern):
    for i, bulb in enumerate(input):
        if bin(bulb & pattern).count('1') % 2 == mod[i]:
            next
        else:
            return False
    
    return True


def main():
    num_switch, num_bulb = [int(x) for x in sys.stdin.readline().split()]
    input = [0] * num_bulb

    for i in range(num_bulb):
        for x in sys.stdin.readline().split()[1:]:
            input[i] += 2**(int(x) - 1)

    mod = [int(x) for x in sys.stdin.readline().split()]

    count = 0

    for pattern in range(2 ** num_switch):
        if all_lighted(input, mod, pattern): count += 1

    print(count)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools

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

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

all_list = list(itertools.product(range(2),repeat=N))

count = 0
for l in all_list:
    is_ok = True
    for light_num, s in enumerate(Ss):
        summation = 0
        for index in s:
            summation += l[index - 1]
        if summation % 2 != Ps[light_num]:
            is_ok = False
            break
    if is_ok:
        count += 1

print(count)

Submission status: Accepted

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

# abc128_c

def main():
    # Input
    n, m = [int(s) for s in input().split()]
    reports = [[int(s) for s in input().split()] for _ in range(m)]
    ps = [int(s) for s in input().split()]
    # Get ans
    def get_switch_lists():
        for i in range(2**n):
            yield [(i//2**k)%2 for k in range(n)]
    def get_odd(switch_list, repo):
        return sum(switch_list[r-1] for r in repo[1:]) % 2
    ans = 0
    for switch_list in get_switch_lists():
        qs = [get_odd(switch_list, repo) for repo in reports]
        if all(p==q for p, q in zip(ps, qs)):
            ans += 1
    # Output
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
onptns = []
for i in range(M):
    k, *s= list(map(int, input().split()))
    onptn = 0
    for i in s:
        onptn += 1 << (i - 1)
    onptns.append(onptn)
ps = list(map(int, input().split()))

ans = 0

s = 0
while s < (1 << N):
    ans += 1
    for onptn, p in zip(onptns, ps):
        if bin(s & onptn).count('1') % 2 != p:
            ans -= 1
            break
    s += 1

print(ans)

Submission status: Accepted

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

ans=0

for i in range(2**n):
    flug=True
    for l in range(m):
        count=0
        for j in range(List[l][0]):
            if ((i >> (List[l][j+1]-1))&1)==1:
                count += 1
        if count%2 != P[l]:
            flug=False
    if flug==True:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

count = 0
for state in product(*([range(2)] * N)):
  for i in range(M):
    sum_on = 0
    for m in s[i]:
      if state[m - 1]:
        sum_on += 1
    if sum_on % 2 != p[i]:
      break
  else:
    count += 1
print(count)

Submission status: Accepted

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

import sys

n,m = [ int(x) for x in sys.stdin.readline().split() ]
s = list()
for _ in range(m):
    t= [ int(x) for x in sys.stdin.readline().split() ][1:]
    flag = 0
    for x in t: flag|= 2**(x-1)
    s.append( flag )
p = [ int(x) for x in sys.stdin.readline().split() ]
#
ans= 0
for test in range(2**n):
    fail= False
    for i in range(m):
        if bin(s[i]&test).count("1")%2 != p[i]:
            fail= True
            break
    #
    if not fail: ans+= 1
#
print( ans )

Submission status: Accepted

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

switch = 2**N
answer = 0

for i in range(switch):
  lamp = []
  bit = format(i,"#010b")[::-1]
  for j in range(len(each_s)):
    count = 0
    for k in each_s[j]:
      if(bit[k-1] == "1"):
        count += 1
    lamp.append(count % 2)
  if lamp == p:
    answer += 1
print(answer)

Submission status: Accepted

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

s = ''
lamp = [0]*M
ans = 0

for i in range(2**N):
    lamp = [0] * M
    s = format(i, '#012b')[::-1]
    for j in range(M):
        for k in link[j]:
            if s[k-1] == '1':
                lamp[j] ^= 1
    if p == lamp:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
import itertools


class Light:
    def __init__(self, _switch_list: list, p: int):
        self.switch_list = _switch_list
        self.p = p

    def is_on(self, all_switch_states: list) -> int:
        implemented_switches = itemgetter(*self.switch_list)(all_switch_states)
        if isinstance(implemented_switches, int):
            return implemented_switches == self.p
        else:
            return sum(implemented_switches) % 2 == self.p


if __name__ == '__main__':
    i = input()
    switch_total_number = int(i.split()[0])
    lights_total_number = int(i.split()[1])
    lines = [input() for i in range(lights_total_number)]
    p_list = [int(x) for x in input().split()]
    lights = []
    for index, line in enumerate(lines):
        switch_list = [int(x)-1 for x in line.split()]
        del switch_list[0]
        lights.append(Light(switch_list, p_list[index]))

    number_of_all_on = 0
    switch_pattern_iter = itertools.product([1, 0], repeat=switch_total_number)
    for switch_pattern in switch_pattern_iter:
        for light in lights:
            if not light.is_on(list(switch_pattern)):
                break
        else:
            number_of_all_on += 1
    print(number_of_all_on)

Submission status: Accepted

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

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

ans = 0

"""
s0, s1, s2, ... , sn
d0, d1, d2, ... , dm
"""

for i in range(2**N):
    light = 0
    for j in range(M):
        cnt = 0
        for k in range(1, ks[j][0]+1):
            if i & 2**(ks[j][k]-1) == 2**(ks[j][k]-1):
                cnt += 1
        if cnt % 2 == ps[j]:
            light += 1

    if light == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
num1, num2 = [int(i) for i in input().split()]

numArray = [[0]*2]*num2

for index1 in range(num2):
    numArray[index1] = [int(j) for j in input().split()]

num3 = [int(k) for k in input().split()]

numArray2 = [[0 for i in range(num1)] for j in range(num2)]

for index5 in range(num2):
    for index4 in range(numArray[index5][0]):
        numArray2[index5][int(numArray[index5][index4+1])-1] = 1

count1 = 0

for index2 in range(2 ** num1):
    num4  = format(index2, 'b').zfill(num1)

    for index6 in range(num2):
        num5 = "".join(map(str,numArray2[index6]))
        num6 = bin(int(num4, 2) & int(num5, 2))
        num7 = sum(list(map(int,num6[2:])))

        if num7 % 2 != num3[index6]:
            break
        if index6 == num2-1:
            count1 +=1

print(str(count1))

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(2**n):
  light = 0
  for j in range(m):
    cnt = 0
    for k in range(1,ks[j][0]+1):
      if i & 2**(ks[j][k]-1) == 2**(ks[j][k]-1):
        cnt += 1
    if cnt % 2 == p[j]:
      light += 1
  if light == m:
    ans += 1
print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(1, 2 ** n + 1):
    for j, l in enumerate(s):
        c = 0
        for k in l:
            c += (i >> (k - 1)) % 2
        if (c % 2 != p[j]):
            break
        if (j == m - 1):
            cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import itertools

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

for i in range(M):
    string_k = input().split()
    ls_k.append(list(map(int, string_k)))
    del ls_k[i][0]

string_p = input().split()
ls_p = list(map(int, string_p))

ans = 0


def S_gen(N):
    S_pat = []
    set_lis = list(range(1, N+1))
    for i in range(1, N+1):
        S_pat.extend(list(itertools.combinations(set_lis, i)))
    return S_pat


S_pat = S_gen(N)
S_pat.extend(("a"))
count = 0

for i in S_pat:
    correct = True
    for j in range(M):
        check = []
        # print(set(ls_k[j][:]))
        # print(set(i))
        check = list(set(ls_k[j][:]) & set(i))
        # print(check)
        if len(check) % 2 != ls_p[j]:
            correct = False
    # print(correct)
    if correct:
        count += 1

print(count)

Submission status: Accepted

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

ans = 0
for i in range(2 ** N):
    count = 0
    for m in range(M):
        tmp_str = str(bin(i))[2:].zfill(N)
        tmp_ones = 0
        for j in s[m]:
            tmp_ones += int(tmp_str[j - 1])
        if tmp_ones % 2 == p[m]:
            count += 1
            if count == M:
                ans += 1
        else:
            break

print(ans)

Submission status: Accepted

Solution code:
"""
2回目:
    kの考慮(ki, si1, ... と, k が最初に連携されてくること) が抜けていた

"""

def solve():
    N, M = map(int, input().split())
    S = [sum([2 ** (int(i) - 1) for i in input().split()][1:]) for _ in
              range(M)]
    P = [int(i) for i in input().split()]
    count = 0
    for i in range(2 ** N):
        for s, p in zip(S, P):
            if bin(s & i).count('1') % 2 != p:
                break
        else:
            count += 1
            # print(bin(i))

    print(count)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def bit_patterns(n):
  if n <= 0:
    return []
  
  patterns = [[0],[1]]
  for i in range(n - 1):
    grow = []
    for pattern in patterns:
      #print(pattern)
      for b in range(2):
        clone = pattern[:]
        clone.append(b)
        grow.append(clone)
    patterns = grow  
  #print(patterns)    
  return patterns


def main():
  lights = []
  #スイッチ個数、電球個数を取得
  n, m = [int(val) for val in input().split()]
  #print(n, m)
  #各電球のスイッチへの接続状態を取得
  for i in range(m):
    #一番目はスイッチ個数だが配列長を見ればよいので捨てる。
    #0スタートにしたいので1引く
    lights.append([int(val) - 1 for val in input().split()][1:]) 

  #点灯条件 pi を取得
  pis = [int(val) for val in input().split()]

  #スイッチの全パターン2^nを順次テストしてすべて点灯するパターンを数える
  all_count = 0
  patterns = bit_patterns(n)
  #print(patterns)
  for pattern in patterns:
    on_count = 0
    for li in range(len(lights)):
      light = lights[li]
      pi = pis[li]
      
      switch_count = 0
      for si in light:
        switch_count += pattern[si]
      if switch_count % 2 == pi:
        on_count += 1
    if on_count == m:
      all_count += 1
  print(all_count)
  
main()

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    flag = True
    for a in range(M):
        cnt = 0
        for b in lightList[a][1:]:
            if (1 & (i>>(b-1))):
                cnt += 1
        if cnt % 2 != P[a]:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy
def light(s,p,l,m):
    a = 0
    for i in range(m):
        k = list(s[i])
        del k[0]
        t = copy.copy(k)
        for j in range(len(k)):
            if l[(k[j]-1)] == "0":
                t.remove(k[j])
        if p[i] == ((len(t))%2):
            a = a + 1
    if a == m:
        return 1
    else:
        return 0
n,m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
count = 0
for i in range(2**n):
    b = str(bin(i))
    b = b.lstrip("0b")
    c = b.zfill(n)
    l = list(c)
    count = count + light(s,p,l,m)
print(count)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
S = list()
for i in range(M):
  s = list(map(int, input().split()))
  S.append(s[1:])
    
P = list(map(int, input().split()))
 
A = [0, 1]
ans = 0
for i in itertools.product(A, repeat = N):
  flag = 0
  for j in range(M):
    cnt = 0
    for s in S[j]:
      if i[s - 1] == 1:
        cnt += 1
    if cnt % 2 != P[j]:
      flag = 1
  if flag == 0:
    ans += 1
    
print(ans)

Submission status: Accepted

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

ans = 0

for i in range(2**n):
    light = 0
    for j in range(m):
        count = 0
        for k in range(1, ks[j][0]+1):
            if i & 2**(ks[j][k]-1) == 2**(ks[j][k]-1):
                count += 1
        if count % 2 == p[j]:
            light += 1
    if light == m:
        ans += 1

print(ans)

Submission status: Accepted

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

c = 0
for i in range(2 ** n):
    for j in range(m):
        if bin(i & s[j]).count("1") % 2 != p[j]:
            break
    else:
        c += 1
print(c)

Submission status: Accepted

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

switch_list = [list(map(int , input().split())) for _ in [0]*M]

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

for i in range(1<<N):
    switch_info = list(str(bin(i)[2:]).rjust(N , '0'))
    ramp_data =[]
    for j in range(M):
        count = 0
        for k in switch_list[j][1:]:
            if switch_info[k-1] == '1':
                count +=1
        ramp_data.append(count%2)
    if ramp_data == p:
        ans +=1


print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ss = []
for mi in range(m):
  splus = [0]*n
  s = list(map(int,input().split()))[1:]
  for ni in range(n):
    if (ni+1) in s:
      splus[ni] = 1
  ss.append(splus)
p = list(map(int,input().split()))
score = 0
swi = [0]*n
while True:
  judge = 1
  for mi in range(m):
    count = 0
    for ni in range(n):
      count += ss[mi][ni] * swi[ni]
    judge *= bool(count%2==p[mi])
  if judge == 1:
    score += 1
  swi[0] +=1
  for ni in range(n-1):
    if swi[ni] == 2:
      swi[ni] = 0
      swi[ni+1] += 1
  if swi[-1] == 2:
    break
print(score)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
K = []
S = []
for i in range(M):
    _input = list(map(int, input().split()))
    k = _input[0]
    s = _input[1:]
    s_bin = 0
    for j in s:
        cur_bin = 1 << (N-j)
        s_bin = s_bin | cur_bin
    K.append(k)
    S.append(s_bin)
P = list(map(int, input().split()))

def count_set_bit(i):
    n_count = 0
    while i:
        n_count += (i & 1)
        i = i >> 1
    return n_count

ans = 0

for i in range(2**N):
    is_ans = True
    for j in range(M):
        if count_set_bit(i & S[j]) % 2 != P[j]:
            is_ans = False
    if is_ans:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#n : switch
#m : light
n, m = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))

ans = 0

#generate all n-bit patern
for i in range(2 ** n):
    #generate pattern(i)
    pattern = bin(i)[2:].rjust(n, '0')
    flag= True
    #print(pattern)
    #print(type(pattern))
    for j in range(m):
        #count on-state
        tmp = 0
        for k in range(1, s[j][0] + 1):
            if pattern[s[j][k] - 1] == "1":
                tmp += 1

        if tmp % 2 != p[j] % 2:
            flag = False

    if flag:
        ans += 1



print(ans)

Submission status: Accepted

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

list_k = [list(map(int, input().split())) for i in range(m)] 
list_p = list(map(int, input().split()))

nn = 1
for i in range(n):
    nn *= 2

x = 0
for i in range(nn): #各スイッチ全状態数でループ
    y = 1
    for im in range(m): #電球数
        rslt = 1 + list_p[im] #偶奇をずらす
        tmp = i
        for iii in range(n): #その状態に対して全スイッチを判定
            if (tmp&1 == 1): #そのスイッチがonなら
                for ik in range(1,list_k[im][0]+1): #リスト長さ
                    if ((list_k[im][ik]-1) == iii): #一致したらカウント
                        rslt += 1
            tmp >>= 1
        y *= (rslt%2) #全部つくときだけ
    x += y

print(x)

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


N, M = map(int, input().split())
lamps = [list(map(lambda x:int(x)-1, input().split()))[1:]
         for _ in range(M)]
p = list(map(int, input().split()))
ans = 0

# bit全探索(スイッチの入れ方を全探索する)
for i in range(1 << N):
    for r in range(M):  # 全てのランプがついてるかチェック
        on_sum = 0  # ランプrにおいて、onのスイッチの数
        for j in range(N):  # スイッチのj番目について
            if i >> j & 1 and j in lamps[r]:
                on_sum += 1  # スイッチjがランプrに繋がってて、onならon_sum+=1
        if on_sum % 2 != p[r]:  # on_off check
            break  # 一つでもoffなら次のbitに
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def brute_force():
    N, M = map(int, input().split())
    lamps = [list(map(lambda x:int(x)-1, input().split()))[1:]
             for _ in range(M)]
    p = list(map(int, input().split()))
    ans = 0

    for i in range(1 << N):
        for r in range(M):
            on_sum = 0
            for j in range(N):
                if i >> j & 1 and j in lamps[r]:
                    on_sum += 1
            if on_sum % 2 != p[r]:
                break
        else:
            ans += 1
    print(ans)


brute_force()

Submission status: Accepted

Solution code:
n, M = map(int, input().split())
s = [[] for _ in range(M)]
for i in range(M):
    li = list(map(int, input().split()))  # -> li = [1,2,3,...n]
    s[i] = li[1:]
p = list(map(int, input().split()))
ans = 0
for i in range(2 ** n):
    f = True
    for j in range(M):
        ss = s[j]
        x = 0
        for sss in ss:
            if (i >> (sss-1)) & 1:
                x += 1
        if p[j] != (x%2):
            f = False
    if f:
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0

for i in range(2**n):
    pika = 0
    for j in range(m):
        count = 0
        for k in range(1, ks[j][0]+1):
            if i & 2**(ks[j][k]-1) == 2**(ks[j][k]-1):
                count += 1
        if count % 2 == p[j]:
            pika += 1
    if pika == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
binlist=[]
for iii in range(m):
  ks=[int(_) for _ in input().split()]
  k=ks[0]
  s=ks[1:]
  binn=0
  for kkk in range(k):
    binn+=2**(s[kkk]-1)
  binlist.append(binn)
q=[int(_) for _ in input().split()]
cnt=0
for iii in range(2**n):
  res=[]
  for jjj in binlist:
    res.append(bin(jjj & iii).count("1")%2)
  if res==q:
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
kslist=[(list(map(int,input().split()))) for i in range(M)]
plist=list(map(int,input().split()))
ls=list((itertools.product(range(2),repeat=N)))
n=0
for tup in ls:
    n+=1
    for j in range(M):
        sum1=0
        for k in range(1,kslist[j][0]+1):
            sum1+=tup[kslist[j][k]-1]
        if sum1%2!=plist[j]:
            n=n-1
            break
print(n)

Submission status: Accepted

Solution code:
n,m = map(int,input().split()) #nがスイッチ、mが電球の数
s = []
sw = []
 
for i in range(m):
  x = list(map(int,input().split()))
  s.append(x)
p = list(map(int,input().split()))
#print(s,p)
 
for i in range(0,2**n): #1は点灯とする
  x = format(i, 'b')
  x = x.zfill(n)
  sw.append(x)

ans = []
for x in sw:
  y = 0 #ａｎｓに加えるかどうかの判定
  for i in range(m):
    z = 0 #あまりの判定
    if y == 0:
      for j in range(s[i][0]):
        if x[s[i][j+1]-1] == "1":
          z += 1
      if z%2 != p[i]:
        y += 1
  if y == 0:
    ans.append(x)
print(len(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()))
result=0
for i in range(1<<n):
    lst=[]
    flag=True
    for j in range(n):
        if 1&(i>>j)==1:
            lst.append(1)
        else:
            lst.append(0)
    for k in range(m):
        count=0
        for l in switch[k]:
            count+=lst[l-1]
        if count%2!=p[k]:
            flag=False
    if flag==True:
        result+=1
print(result)

Submission status: Accepted

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n , m = f()

    cons = [f() for i in range(m)]
    p = f()

    ans = 0
    for i in range(1<<n):
        on = [0] * n
        for j in range(n):
            if i&(1<<j):
                on[j] = 1
        
        cnt_on = [0] * m
        for j in range(m):
            for k in range(1, len(cons[j])):
                if on[cons[j][k]-1]:
                    cnt_on[j] += 1
        
        ok = 1
        for j in range(m):
            if (cnt_on[j] + p[j])%2 != 0:
                ok = 0
        if ok:
            ans += 1
    
    print(ans)

            



solve()

Submission status: Accepted

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

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

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

result = 0
for i in range(2 ** N):
  for j, v in enumerate(k):
    s = [1 for temp in v if 2 ** (temp-1) & i]
    if sum(s) % 2 != p[j]:
      break
  else :
    result += 1
  

print(result)

Submission status: Accepted

Solution code:
N,M = map(int,input().split(' '))
S = []
for i in range(M):
  X = list(map(int,input().split(' ')))
  s = tuple(X[1:])
  S.append(s)
P = list(map(int,input().split(' ')))
num = 0
for i in range(1<<N):
  Flag = True
  for j in range(M):
    numON = 0
    for k in S[j]:
      if (i >> k-1) & 1:
        numON += 1
    if numON % 2 != P[j]:
      Flag = False
      break
  if Flag:
    num += 1
print(num)

Submission status: Accepted

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

buff = []
for m in range(M):
    lst = list(map(int,input().split()))
    k=lst.pop(0)
    ss=[s-1 for s in lst]
    buff.append((k,ss))

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

pats = []
for (k,ss),p in zip(buff, ps):
    pats.append((k,ss,p))


base = int('1'*N,2)

format = '{:0' + str(N) + 'b}'

cnt = 0
for i in range(base+1):
    check_tar = [int(x) for x in format.format(i)]
    ress = []
    for k,ss,p in pats:
        res = sum([check_tar[s] for s in ss])%2 == p
        ress.append(res)
    #print(ress, all(ress), format.format(i))
    if all(ress):
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, p = LI()
    print((a*3+p)//2)
    return

#B
def B():
    n = II()
    sp = []
    for i in range(n):
        sp.append(input().split())
    another = [(s[0], -1 * int(s[1]),num) for num,s in enumerate(sp)]
    another.sort()
    for s,p,q in another:
        print(q+1)

    return

#C
def C():
    n, m = LI()
    ks = LIR_(m)
    p = LI()
    patern = itertools.product(range(2), repeat=n)
    ans = 0
    for on in patern:
        ki = [0 for i in range(m)]
        for num, oni in enumerate(on):
            if oni:
                for i,ksi in enumerate(ks):
                    ksi = ksi[1::]
                    if num in ksi:
                        ki[i] ^= 1
        #print(ki)
        for num, pi in enumerate(p):
            if pi != ki[num]:
                break
        else:
            ans += 1
    print(ans)

            
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
def pow2(n):
	v = 1
	for i in range(0, n):
		v *= 2
	return v

def switchlist(x, n):
	m = x
	lst = []
	while m != 0:
		lst.append(m%2)
		m = int(m/2)
	for i in range(len(lst), n):
		lst.append(0)
	return lst

N, M = map(int, input().split())
bulb = []
for i in range(0, M):
	inpt = list(map(int, input().split()))
	bulb.append(inpt[1:])
rule = list(map(int, input().split()))
cnt = pow2(N)
for i in range(0, pow2(N)):
	switches = switchlist(i, N)
	for j in range(0, M):
		oncount = 0
		for k in range(0, len(bulb[j])):
			if switches[bulb[j][k]-1] == 1: oncount += 1
		if oncount % 2 != rule[j]:
			cnt -= 1
			break
print(cnt)

Submission status: Accepted

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

r = 2 ** n
x = []
y = [[0 for i in range(k)]for i in range(r)]
z = 0

for i in range(r):
    x.append(str(bin(i).split('b')[1]).zfill(n))
    for j in range(k):
        for l in ks[j][1:]:
            y[i][j] += int(x[i][l - 1])
        if y[i][j] % 2 != p[j]:
            break
    else:
        z += 1

print(z)

Submission status: Accepted

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