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 sys
inputs = sys.stdin.readlines()

n, m = map(int, inputs[0].split())
connections = []
for i in range(1, m+1):
    connection = [0] * n
    _, *S = map(int, inputs[i].split())
    for s in S:
        connection[s-1] = 1
    connections.append(connection)
*P, = map(int, inputs[i+1].split())

patterns = []
for i in range(2 ** n):
    pattern = [(i >> j) & 1 for j in range(n)]
    on_switches = [sum(c and p for c, p in zip(connection, pattern)) for connection in connections]
    if all(p == s%2 for p, s in zip(P, on_switches)):
        patterns.append(pattern)
print(len(patterns))

Submission status: Accepted

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

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

P = list(map(int, input().split()))
         
## 全探索!!!
## 全ての電球のOn、Offの組み合わせを確認する
ans = 0
from itertools import product
for sw in product([0,1], repeat=N):
  ## 電球ごとに確認する
  for b,p in zip(bubble, P):
    if sum(sw[s-1] for s in b)%2 != p:
      break
  ## for文が正常に回りきったら、ansに1を追加する
  else:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
import sys

n, m = map(int, input().split())
k = []
for i in range(m):
    s = list(map(int, input().split()))[1:]
    k.append(s)
p = list(map(int, input().split()))
# print("k =", k)
# print("p =", p)
# print("n =", n)
# print("m =", m)
ans = 0
for i in range(1 << n):
    on = []
    binary = format(i, "b").zfill(n)
    # print(binary)
    for j in range(len(binary)):
        if binary[j] == "1":
            on.append(j + 1)
    # print(on)
    possible = True
    for j in range(m):
        switch = k[j]
        cnt = 0
        for l in switch:
            if l in on:
                cnt += 1
        if cnt % 2 != p[j]:
            possible = False
    if possible:
        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(2**N):
    on=[0]*N
    tmp=0
    for j in range(N):
        if((i>>j)&1):
            on[j]=1
    for j in range(M):
        count=0
        for h in range(1,ks[j][0]+1):
            if(on[ks[j][h]-1]==1):
                count+=1
        if(count%2==p[j]):
            tmp+=1
    if(tmp==M):
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
def main():
    N,M=map(int,input().split())
    s=[[] for i in range(0,M)]
    for i in range(0,M):
        s[i]+=list(map(int,input().split()))
    p=list(map(int,input().split()))
    ans=0
    for i in range(0,2**N):
        flag=0
        for j in range(0,M):
            x=0
            for k in range(1,s[j][0]+1):
                x+=(i >> (s[j][k]-1) & 1)
            if x%2!=p[j]:
                flag=1
        if flag==0:
            ans=ans+1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
K, S = [], []
for _ in range(M):
    ks = list(map(int, input().split()))
    K.append(ks[0])
    S.append(ks[1:])
P = list(map(int, input().split()))
    
from itertools import product
pattern = list(product(*[[0, 1]]*N))

ans = 0
for patt in pattern:
    success = 1
    for k, s, p in zip(K, S, P):
        on = 0
        for i in range(k):
            on += patt[s[i] - 1]
        if on % 2 != p:
            success = 0
            break
    if success:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def bits2tuple(n):
    ret = []
    i = 0
    while (1 << i) <= n:
        if n & (1 << i) != 0:
            ret.append(i)
        i += 1
    return tuple(ret)


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

    kM = []
    skM = []
    for _ in range(M):
        sk = list(map(int, input().split()))
        k = sk.pop(0)

        kM.append(k)
        skM.append(sk)

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

    ans = 0
    for bits in range(0, 1 << N):
        on_switch = list(map(lambda x: x + 1, bits2tuple(bits)))

        all_on = True
        for p, k, sk in zip(pM, kM, skM):
            if len(set(on_switch) & set(sk)) % 2 != p:
                all_on = False
                break

        if all_on:
            ans += 1

    print(ans)


main()

Submission status: Accepted

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

# 全点灯パターンの個数
ans = 0

# 点灯している電球の数
cnt_s_on = 0

# 電球jに繋がるONのスイッチの数
cnt_switch = 0

for i in range(2**n):
    cnt_s_on = 0
    
    # すべての電球に対して調べる
    for j in range(m):
        cnt_switch = 0
        
        # 電球jに繋がるすべてのスイッチに対してON/OFFを調べる
        for K in range(k[j]):
            if ((i >> (s[j][K]-1)) & 1):
                # スイッチがONならONカウントに＋する
                cnt_switch += 1
        
        if cnt_switch%2 == p[j]:
            # 電球jは点灯している
            cnt_s_on += 1
    
    if cnt_s_on == m:
        ans += 1

print(ans)

Submission status: Accepted

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

# 全点灯パターンの個数
ans = 0

# 点灯している電球の数
cnt_s_on = 0

# 電球jに繋がるONのスイッチの数
cnt_switch = 0

for i in range(2**n):
    # print(bin(i))
    # print(bin(i>>1))
    # print("----")

    # print("i: "+str(bin(i)))
    tmpS=[0]*m
    cnt_s_on = 0
    
    # すべての電球に対して調べる
    for j in range(m):
        cnt_switch = 0
        
        # 電球jに繋がるすべてのスイッチに対してON/OFFを調べる
        for K in range(k[j]):
            if ((i >> (s[j][K]-1)) & 1):
                # スイッチがONならONカウントに＋する
                cnt_switch += 1
        
        # print("cnt_switch: " + str(cnt_switch))
        # print("cnt_switch%2: " + str(cnt_switch%2))
        # print("p[j]: " + str(p[j]))
        if cnt_switch%2 == p[j]:
            # 電球jは点灯している
            cnt_s_on += 1
            tmpS[j] = 1
    
    # print("電球状況："+str(tmpS))
    # print("cnt_s_on: " + str(cnt_s_on))
    if cnt_s_on == m:
        ans += 1

    # print("----------")
print(ans)

Submission status: Accepted

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

#print(k)
#print(p)

ans = 0
for i in range(2**n):
    state = [0] * n
    for j in range(n):
        state[j] = (i >> j) & 1

    #print(state)

    cnt = 0
    for j in range(m):
        num_on = 0
        for l in range(1, len(k[j])):
            if state[int(k[j][l]) - 1] == 1:
                num_on += 1
        if num_on % 2 == p[j]:
            cnt += 1
    if cnt == m:
        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(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:
def count_one(num):
  ret = 0
  while num:
    if num & 1: ret+=1
    num = num >> 1

  return ret

def solve():
  N,M = map(int, input().split())
  switches = []
  for _ in range(M):
    switches_pattern = list(map(int, input().split()))[1:]
    pattern_int = sum(2**(i-1) for i in switches_pattern)
    switches.append(pattern_int)
  ps = list(map(int, input().split()))

  switch_pattern_upper = 2**N

  def check(pattern):
    ret = True
    for i in range(M):
      bit_count = count_one(switches[i] & pattern)
      # print(switches[i] & pattern, bit_count)
      if bit_count % 2 != ps[i]:
        ret = False
        break
      
    return ret
    
  ret = 0
  # print(switches)
  for pattern in range(switch_pattern_upper):
    # print(pattern)
    if check(pattern): ret += 1

  print(ret)
  
solve()

Submission status: Accepted

Solution code:
# coding: utf-8

class Proc:
    def __init__(self):
        (n, m) = [int(i) for i in input().rstrip().split(" ")]
        self.switch_count = n
        self.light_count = m
        self.light_connect = [[int(i) - 1 for i in input().rstrip().split(" ")][1:] for j in range(m)]
        self.light_setting = [int(i) for i in input().rstrip().split(" ")]

    def get_ans(self, index: int, subtotal: int):
        if index >= self.switch_count:
            light_connect_count = [0 for i in range(self.light_count)]
            for i in range(0, self.switch_count):
                if ((1 << i) & subtotal) == 0:
                    continue
                for j in range(self.light_count):
                    if i in self.light_connect[j]:
                        light_connect_count[j] += 1
            if all([light_connect_count[i] % 2 == self.light_setting[i] for i in range(self.light_count)]):
                return 1
            else:
                return 0

        ret = self.get_ans(index + 1, subtotal) + self.get_ans(index + 1, subtotal + (1 << index))
        return ret


print(Proc().get_ans(0, 0))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = []
k = []
for i in range(m):
    s_in = list(map(int,input().split()))
    s.append(s_in[1:])
    k.append(s_in[0])
p = list(map(int,input().split()))
ans = 0
def bfs(switch):
    global ans
    if len(switch)==n:
        ok = 1 #全部の電球がつく
        for i in range(m):
            on_cnt=0
            for j in range(k[i]):
                if switch[s[i][j]-1]==1:
                    on_cnt+=1
            if on_cnt%2!=p[i]:
                ok = 0
        if ok:
            ans+=1
    else:
        bfs(switch+[0])
        bfs(switch+[1])
bfs([])
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N, M = map(int, input().split())
denkyu = [[int(x) for x in input().split()] for _ in range(M)]
P = [int(x) for x in input().split()]
L = list(product([0,1], repeat = N))
ans = 0
for i in L:
    den = 0
    for j in range(M):
        count = 0
        for k in range(denkyu[j][0]):
            if i[denkyu[j][k+1]-1] == 0:
                count += 1
        if count % 2 == P[j]:
           den += 1 
    if den == M:
        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()))

s = []
ans = 0
for i in range(m):
  k = ks[i][0]
  l = [ks[i][j] for j in range(1, k+1)]
  s.append(l)

swh = [False for _ in range(n)]
for i in range(2 ** n):
  #print('######')
  flag = True
  # スイッチの状態
  for j in range(n):
    if ((i >> j) & 1): swh[j] = True
    else: swh[j] = False
      
  # 現在の状態での各電球の点灯をチェック    
  for j in range(m):
      #print('電球{}'.format(j))
      judge = [swh[si-1] for si in s[j]]
      #print(judge)
      if judge.count(True) % 2 != p[j]:
        flag = False
        break
        
  if flag: ans += 1
  #print('ans = {}'.format(ans))
      
print(ans)

Submission status: Accepted

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

P = list(map(int, input().split()))
ans = 0
for i in range(2**N):
  if all([
    sum([i & 2 ** (n-1) > 0 for n in S[m]]) % 2 == P[m] for m in range(M)
  ]):
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
indices = []
for _ in range(m):
  s_map = map(int, input().split())
  next(s_map)
  indices.append([s-1 for s in s_map])
p = list(map(int, input().split()))
count = 0
for i in range(1 << n):
  list_i = [int(bit) for bit in format(i, '0{}b'.format(n))]
  flag = True
  for j in range(m):
    on = 0
    for idx in indices[j]:
      on ^= list_i[idx]
    if on != p[j]:
      flag = False
      break
  if flag:
    count += 1
print(count)

Submission status: Accepted

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

ans = 0
for b in range(2**N):
    for s,p in zip(S,P):
        c = 0
        for t in s:
            if b&(1<<(t-1)): c += 1
        if c%2 != p:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys

n, m = map(int, sys.stdin.readline().split())
s = [set(map(int, sys.stdin.readline().split()[1:])) for _ in range(m)]
*p, = map(int, sys.stdin.readline().split())

def main():
    combs = 0
    for i in range(2 ** n):
        t = set([j + 1 for j in range(n) if i >> j & 1])
        for k in range(m):
            if len(s[k] & t) & 1 != p[k]:
                break
        else:
            combs += 1
    
    return combs

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
def so(l, n, ar):
	if (n < l):
		so(l, n + 1, ar + [True])
		so(l, n + 1, ar + [False])
	elif (n == l):
		global switchOnOff
		switchOnOff.append(ar)
        
switchOnOff = []
n, m = [int(i) for i in input().split()]
denkyus = []
for i in range(m):
	a = [int(j) for j in input().split()]
	denkyus.append(a[1:])
hikaku = [int(i) for i in input().split()]   
so(n, 0, [])

ret = 0
denkyuCnt = [0] * m
for ss in switchOnOff:
	denkyuCnt = [0] * m
	for si, s in enumerate(ss):
		for ji, j in enumerate(denkyus):
			if s and (si + 1) in j:
				denkyuCnt[ji] += 1
	subcnt = 0
	for i, d in enumerate(denkyuCnt):
		if d % 2 == hikaku[i]:
			subcnt += 1
	if subcnt == m:
		ret += 1
print (ret)

Submission status: Accepted

Solution code:
import os, sys, re, math

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

result = 0
for i in range(2 ** N):
    bulbs = bin(i)[2:].zfill(N)
    all_ok = True
    for j in range(len(S)):
        l = sum([int(bulbs[s - 1]) for s in S[j]])
        all_ok &= (l % 2 == P[j])
    if all_ok:
        result += 1

print(result)

Submission status: Accepted

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

v = 0
for i in range(1 << n):
    on = True
    for k, p in zip(ks, ps):
        c = 0
        for b in k[1:]:
            if i & 1 << (b-1) > 0:
                c += 1
        if c % 2 != p:
            on = False
            break
    if on:
        v += 1

print(v)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = [list(map(int, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
print(sum(all(sum((b >> (j - 1)) & 1 for j in k[i]) % 2 == p[i] for i in range(m)) for b in range(2 ** n)))

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split(' ')))
kk = []
ss = []
for i in range(m):
    l = list(map(int, input().split(' ')))
    k = l[0]
    s = l[1:]
    kk.append(k)
    ss.append(s)
    
pp = list(map(int, input().split(' ')))
def ok(switches):
    valid = True
    for i in range(len(ss)):
        s = ss[i]
        temp = 0
        for j in range(len(s)):
            temp += switches[s[j]-1]
        if temp % 2 != pp[i]:
            valid = False
            break
    return valid
# 2^10 = 1024
def f(current, switches):
    if current == n:
        return ok(switches)
    ans = f(current + 1, switches + [1])
    ans += f(current + 1, switches + [0])
    return ans
print(f(0, []))

Submission status: Accepted

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

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

cnt=0
for i in range(2**n):
  flag=True
  i=format(i,'b')
  i=i.zfill(n)
  for j in range(m):
    ans=0
    for k in range(1,lights[j][0]+1):
      ans+=int(i[lights[j][k]-1])
      ans%=2
    if ans==p[j]:
      continue
    else:
      flag=False
  if flag:
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
N_sw, N_ball = map(int, input().split())

switches = [list(map(int, input().split())) for i in range(N_ball)]
P = list(map(int, input().split()))
cnt = 0

def judge_OK(state_2):
    flag = True
    
    for i in range(N_ball):
        S = switches[i]
        count = 0
        
        for j in range(1, len(S)):
            index = S[j] - 1
            count += state_2[index]
        
        if (count % 2 != P[i]):
            flag = False
            break
    
    return(flag)


for state in range(2 ** N_sw):
    state_2 = []
    
    for i in range(N_sw):
        tmp = int((state & 1 << i) == 1 << i)
        state_2.append(tmp)
    
    cnt += judge_OK(state_2)

print(cnt)

Submission status: Accepted

Solution code:
import itertools

n, m = [int(x) for x in input().split()]
lst = []
for _ in range(m):
    a = [int(x) for x in input().split()]
    lst.append(a)
p = tuple([int(x) for x in input().split()])

sta = [0,1]
cnt = 0

for v in itertools.product(sta, repeat=n):
    for i in range(m):
        if sum(v[x - 1] for x in lst[i][1:]) % 2 != p[i]:
            break 
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
lights = []
for i in range(M):
    k, *s = map(int, input().split())
    lights.append(list(map(lambda x: x-1, s)))
P = list(map(int, input().split()))
ans = 0
for b in range(2 ** N):
    flg = True
    for m in range(M):
        cnt = 0
        for switch in lights[m]:
            if (b >> switch) & 1:
                cnt += 1
        if cnt % 2 != P[m]:
            flg = False
    if flg:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n, m = MAP()

l = [LIST() for i in range(m)]
p = LIST()

# bits全探索
bits = product([0, 1], repeat=n)
ans = 0
#print(list(bits))

for b in bits:
    light = 0
    for i, s_l in enumerate(l):
        on = 0
        for s in s_l[1:]:
            on += b[s-1]
        if on % 2 == p[i]:
            light += 1
    if light == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
switch = [0]*N
for m in range(M):
    ss = list(map(int, input().split()))[1:]
    for s in ss:
        switch[s-1] |= 2**m
li = 0
for index,p in enumerate(list(map(int, input().split()))):
    if p==1: li += 2**index
answer = 0
for n in range(2**N):
    l = 0
    for s in range(N):
        if (n>>s)&1: l^=switch[s]
    if li==l: answer+=1
print(answer)

Submission status: Accepted

Solution code:
from numpy import *

n, m = map(int, input().split())
l = []
for _ in range(m):
   *a, = map(int, input().split())
   l.append(a[1:])
*p, = map(int, input().split())

ans = 0
for t in range(2**n):
   tmp = array([t >> s & 1 for s in range(n)])
   if p == [sum(tmp[array(i)-1]) % 2 for i in l]:
      ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
lights=[]
for i in range(M):
    k,*s=map(int,input().split())
    lights.append(list(map(lambda x:x-1,s)))
P=list(map(int,input().split()))
cnt=0
for b in range(1<<N):#bit
    #print("bit="+str(b))
    flg=True
    for m in range(M):#各bitごとに各電球を調べる
        on_cnt=0
        for switch in lights[m]:#つながってるスイッチ番号
            if (b>>switch)&1:
                on_cnt+=1
        #if on_cnt==0 or on_cnt%2 != P[m]:
        if on_cnt%2 != P[m]:
            flg=False
    if flg:
       cnt+=1
       #print(b)
print(cnt)

Submission status: Accepted

Solution code:
# N:SW M:電球

N, M = map(int, input().split())
SW = [[] for _ in range(M)]

for i in range(M):
  SW[i] = [int(s)-1 for s in input().split()[1:]]

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

ans = 0
for bit in range(1<<N): #SW: on, off
  ok = True
  for i in range(M):
    con = 0
    for sw in SW[i]: # 1つずつ
      if bit & (1<<sw):
        con += 1
    if con%2 != P[i]:
      ok = False
  if ok:
    ans += 1
print(ans)

Submission status: Accepted

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

cnt=0
for i in range(2**n):
    Q=0
    light=set([i+1 for i,j in enumerate(format(i,"b").zfill(n)[::-1]) if j=="1"])
    for k,j in enumerate(S):
        if len(light&set(j))%2==P[k]:Q +=1
    if Q==m:cnt +=1

print(cnt)

Submission status: Accepted

Solution code:
def check(l, s, p):
    for i in range(len(l)):
        l_i = l[i]
        cnt = 0
        for j in range(1,len(l_i)):
            cnt += s[l_i[j]-1]
        if cnt % 2 != p[i]:
            return False
    return True


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

ans = 0
for k in range(2**n):
    s = []
    for i in range(n):
        s.append( int(k & 1<<i == 1<<i) )
    ans += int(check(l,s,p))
print(ans)

Submission status: Accepted

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

ans=0
for i in range(2 ** n):
    swi = []
    for j in range(n):
        if ((i >> j) & 1):
            swi.append(1)
        else:
            swi.append(0)
    swi.reverse()

    ok_flag=True
    for lit in range(m):
        sm=0
        for tmp in range(1,len(l[lit])):
            sm += swi[l[lit][tmp]-1]
        if sm % 2 != p[lit]:
            ok_flag=False

    if ok_flag:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
    n, m = map(int, input().split())
    num_list = []
    for i in range(m):
        num_list.append(list(map(int,input().split())))

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

    ans = 0

    for i in itertools.product([0,1], repeat=n):
        check = [0] * m
        for j in range(m):
            tmp = 0
            check[j] = True
            for n in range(1, num_list[j][0] + 1):
                if i[num_list[j][n] - 1] == 1:
                    tmp += 1
            if tmp % 2 != p_list[j] % 2:
                check[j] = False
        if all(check):
            ans += 1

    print(ans)

if __name__ == '__main__':
    main()

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

SS = []

for s in S:
  s.pop(0)
  SS.append(s)

count = 0

for bit in range(1 << N):
  flag = True

  for index, s in enumerate(SS):
    on = 0

    for n in range(N):
      if n+1 in s and bit & (1 << n):
        on += 1

    if on % 2 != P[index]:
      flag = False

  if flag:
    count += 1

print(count)

Submission status: Accepted

Solution code:
k = []

n, m = map(int, input().split())
for i in range(m):
    k.append(list(map(int, input().split())))
    del k[i][0] 

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

cnt = 0
ans = 0
for i in range(2 ** n):
    lis = [False] * n

    for j in range(n):
        if (i >> j) & 1:
            lis[j] = True
    #print(lis)
    cnt = 0
    for j in range(m):
        val = 0
        for l in range(len(k[j])):
            if lis[k[j][l]-1] == True:
                val += 1
            #print(lis[k[j][l]-1])
        if val % 2 == p[j]:
            cnt += 1
        #print(val)
        #print(cnt)
    if cnt == m:
        ans += 1
    #print(ans)



print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
den = []
for _ in range(m):
    i = list(map(int, input().split()))
    i.pop(0)
    tden = [0] * n
    for j in i:
        tden[j - 1] = 1
    den.append(tden)

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

import itertools as it

stat = [i for i in it.product([0, 1], repeat=n)]
ans = 0
for st in stat:
    f = 1
    for no, td in enumerate(den):
        l = [min(i, j) for i, j in zip(st, td)]
        tento = sum(l) % 2
        if p[no] != tento:
            f = 0
            break
    if f: ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    switch = list((str(bin(i)[2:])).zfill(N))
    all_on = True
    for j in range(M):
        on = 0
        for k in range(1,len(light[j])):
            if switch[light[j][k] - 1] == "1":
                on += 1
        if on % 2 != p[j]:
            all_on = False
            break
    if all_on == True:
        ans += 1

print(ans)

Submission status: Accepted

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

ans = 0

for i in range(2 ** n):
    isLightOn = [False] * m
    for k in range(m):
        count = 0
        for j in range(len(s[k])):
            if (i >> s[k][j] - 1) & 1:
                count += 1
        if count % 2 == p[k]:
            isLightOn[k] = True
    if sum(isLightOn) == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#python3

class Light:
    def __init__(self, conect, condition):
        self.conect = conect 
        self.condition = condition

def main():
    n, m = map(int, input().split())
    preArray = []
    for i in range(m):
        tmp = [int(i) - 1 for i in input().split()][1:]
        preArray.append(tmp)
    ps = [int(i) for i in input().split()]


    Lights = []
    for i in range(m):
        Lights.append(Light(preArray[i], ps[i]))



    ans = 0
    for i in range(1<<n):
        swichState = [0 for _ in range(n)]
        for k in range(n):
            if (i >> k) & 1:
                swichState[k] = 1
        
        #print(swichState)

        flag = True
        for j in range(m):
            conec = Lights[j].conect
            cond = Lights[j].condition
            cnts = 0
            for k in range(len(conec)):
                if swichState[conec[k]] == 1:
                    cnts += 1 
            if cnts % 2 == cond:
                continue
            else:
                flag = False
                break
        if flag:
            ans += 1

    print(ans)
main()

Submission status: Accepted

Solution code:
from itertools import product
 
n, m = map(int, input().split())
k = []
s = []
for i in range(m):
    tmp = list(map(int, input().split()))
    k.append(tmp[0])
    s.append(tmp[1:])
p = list(map(int, input().split()))
 
ans = 2 ** n
for prod in (product([0, 1], repeat=n)):
    for i in range(m):
        tmp = 0
        for j in s[i]:
            tmp += prod[j - 1]
        if (tmp % 2 != p[i]):
            ans -= 1
            break
print(ans)

Submission status: Accepted

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

endStr = ("0000000000" + "1"*N)[-10:]
count = 0
#スイッチの付け方
for i in range(0, 2 ** 10):
    binStr = ("0000000000" + format(i, 'b'))[-10:]
    errFlg = 0
    #各電球が点灯するか判定
    for j in range(M):
        s = 0
        for k in range(len(lstMain[j])):
            s += int(binStr[(-1) * lstMain[j][k]])
        if s % 2 != lstP[j]:
            errFlg = 1
        if errFlg == 1:
            break
    if errFlg == 0:
        count += 1
    if binStr == endStr:
        break
    
print(count)

Submission status: Accepted

Solution code:
n,m = map(int, input().split( ))
sw = [0 for _ in range(m)]#でんきゅがつながってるスイッチ
for i in range(m):
    s = list(map(int, input().split( )))
    s = [si-1 for si in s[1:]]
    bt = 0
    for sj in s:#電球
        bt += 1<<sj
    sw[i] = bt
    
p = list(map(int, input().split( )))

#スイッチ
bit = 1<<n
ans = 0
for i in range(bit):#スイッチつけ方
    flag = True
    for j in range(m):#電球
        cnt = 0
        for k in range(n):#スイッチチェック
            cnt += (i&sw[j])>>k
        if cnt%2!=p[j]:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
f = lambda : map(int, input().split())

n, m = f()
ll = [[0]*n for i in range(m)]
for i in range(m):
  _, *t = f()
  for j in t:
    ll[i][j-1] = 1
lp = list(f())

import itertools as it
ans = 0

for p in it.product([0,1], repeat=n):
  if lp == [sum(a*b for a, b in zip(p,l))%2 for l in ll]:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
f = lambda : map(int, input().split())

n, m = f()
ll = [[0]*n for i in range(m)]
for i in range(m):
  k, *t = f()
  for j in range(k):
    ll[i][t[j]-1] = 1
lp = list(f())

import itertools as it
ans = 0

for p in it.product([0,1], repeat=n):
  if lp == [sum(a*b for a, b in zip(p,l))%2 for l in ll]:
    ans += 1

print(ans)