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=[list(map(int,input().split()))[1:] for i in range(M)]
p=list(map(int,input().split()))
ans=0
for i in range(2**N):
   sw=[0]*N
   n=0
   for k in range(N):
      if (i >> k)&1:
         sw[k] = 1
   for s,j in enumerate(l):
      tmp=0
      for x in j:
         if sw[x-1]==1:
            tmp+=1
      if tmp%2==p[s]:
         continue
      else:
         n=1
         break
   if n==1:
      n=0
      continue
   else:
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
denkyu = [list(map(int, input().split())) for _ in range(m)]
p =list(map(int, input().split()))
ans = 0
for i in range(2 ** n):
    count = [0 for i in range(m)]
    for j in range(n):
        if ((i >> j) & 1):
            for k in range(m):
                if j + 1 in denkyu[k][1:]:
                    count[k] += 1
    for j in range(m):
        count[j] %= 2
    if count == p:
        ans += 1
print(ans)

Submission status: Accepted

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

S = []
for _ in range(M):
    tmp = [int(x) for x in input().split()]
    k = tmp[0]
    S.append(tmp[1:])
P = [int(x) for x in input().split()]

ret = 0
# bitでN個のスイッチ押し方の全パターンを列挙する方針
for pt in range(1<<N):
    allOn = True
    # 電球iが点灯するかどうか
    for i in range(M):
        cnt = 0     # 電球iに対応したスイッチの中で押した数 
        for s in S[i]:
            if pt & (1 << (s-1)):
                cnt += 1
        if cnt % 2 != P[i]:
            allOn = False
    if allOn:
        ret += 1

print(ret)

Submission status: Accepted

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

S = []
for _ in range(M):
    tmp = [int(x) for x in input().split()]
    k = tmp[0]
    S.append(tmp[1:])
P = [int(x) for x in input().split()]

ret = 0
for pt in range(1<<N):
    allOn = True
    for i in range(M):
        swcnt = 0
        for s in S[i]:
            if pt & (1 << (s-1)):
                swcnt += 1
        if swcnt % 2 != P[i]:
            allOn = False
    if allOn:
        ret += 1

print(ret)

Submission status: Accepted

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

for z in product((0, 1), repeat=n):
    righton_count=0
    for i in range(m):
        switc_on_count=0
        for j in range(1,s[i][0]+1):
            if z[s[i][j]-1]==1:              
                switc_on_count+=1
        if switc_on_count%2==p[i]:
            righton_count+=1
    if righton_count==m:
        ans+=1



print(ans)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
# a = list(map(int, input().split()))
# data = [list(map(int, input().split())) for i in range(n)]
# n = int(input())
# n, m = list(map(int, input().split()))
# ab_sorted = sorted(ab, key=lambda x: x[0])
s = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
data = []
for i in range(2**n):
    swich = []
    for j in range(n):
        if((i >> j) & 1):
            swich.append(1)
        else:
            swich.append(0)
    data.append(swich)

ans = 0
flag = True
for i in range(2**n):
    flag = True
    for j in range(m):
        count = 0
        for k in range(1, len(s[j])):
            if data[i][s[j][k]-1] == 1:
                count += 1
        if count % 2 != p[j]:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
def search(x):
    global ans
    cnt = 0
    for i in range(m):
        c = 0
        for j in d[i][1:]:
            if x[j-1]==1:
                c += 1
        if c%2==p[i]:
            cnt += 1
    if cnt==m:ans+=1

from itertools import product
o = product(range(2),repeat=n)
for i in o:
    search(i)
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
ans = 0
light = []
for i in range(m):
    light.append(list(map(int, input().split())))
p = list(map(int, input().split()))
for bit in range(1 << n):
    switch = [0 for i in range(n)]
    for j in range(n):
        if (bit >> j & 1):
            #j番目のスイッチがついている
            switch[j] += 1
    flag = True
    for i in range(m):
        count = 0
        for j in light[i][1:]:
            count += switch[j-1]
        if count % 2 != p[i]:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
def main():
    n, m = map(int, input().split())
    t = [[False]*n for _ in range(m)]
    for i in range(m):
        a = list(map(int, input().split()))
        for v in a[1:]:
            t[i][v-1] = True
    p = list(map(int, input().split()))
    ans = 0
    for a in product([True, False], repeat=n):
        f = True
        for i in range(m):
            cnt = 0
            for j in range(n):
                if t[i][j] and a[j]:
                    cnt += 1
            if cnt%2 != p[i]:
                f = False
                break
        if f:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import product

# input
N, M = map(int, input().split())
switch = {}
for i in range(M):
    inp = list(map(int, input().split()))
    switch[i] = {
        "k": inp[0],
        "s": inp[1:]
    }
inp = list(map(int, input().split()))
for i, p in enumerate(inp):
    switch[i]["p"] = p

# check
case = list(product([0, 1], repeat=N))
for k in switch.keys():
    
    case = [
        c
        for c in case
        if sum(
            [
                n
                for i, n in enumerate(c)
                if i + 1 in switch[k]["s"]
            ]
        ) % 2 == switch[k]["p"]
    ]

    if len(case) == 0:
        break

print(len(case))

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 i in range(2**n):
    light = 0
    
    for j in range(m):
        on = 0
        
        for k in S[j]:
            k -= 1
            
            if (i >> k) & 1:  #### k番目のスイッチがonか確認
                on += 1
                
        if on % 2 == P[j]:
            light += 1
            
    if light == m:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
n , m = map(int, input().split())
k=[]
z=[]
for i in range(m):
    t = list(map(int,input().split()))
    k.append(t[0])
    z.append(t[1:])
p = list(map(int,input().split()))
s = [list(map(int,bin(x)[2:].zfill(n))) for x in range(2**n)]

ans =0
for i in s:
    light=0
    for j in range(m):
        b=0
        for l in range(k[j]):
            if i[z[j][l]-1]==1:
                b+=1
        if b%2==p[j]:
            light+=1
    if light==m:
        ans+=1
print(ans)

Submission status: Accepted

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

sl = [[]] * m

for i in range(m):
  s = [num for num in map(int, input().split())]
  sl[i] = s

  
p = [num for num in map(int, input().split())]
# print(p, sl)

ans = 0
# すべてのスイッチの状態を bit全探索 (各bit 1: on, 0: off)
for i in range(1 << n):
  # print('i: ', i)
  # そのスイッチの状態で各電球が光るか
  for j in range(m):
    s = sl[j]
    ons = 0
    # 光ってる数を数える
    for k in range(1, s[0]+1):
      # bit桁 = スイッチ番号 - 1 なので、現在のスイッチの状態はこの電球の対象か
      if i & (1 << (s[k]-1)):
        ons += 1
    # 1つでも光っていないと break
    if ons % 2 != p[j]:
      break
  else:
    # すべての処理でbreakしない == すべての電球が光っている
    ans += 1


print(ans)

Submission status: Accepted

Solution code:
import sys
#import numpy as np
#import math
from fractions import Fraction
import itertools

input=sys.stdin.readline

n,m=map(int,input().split())
v=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
c=0
for i in range(2**n):
    s=[0]*n
    for j in range(n):
        if i>>j&1==1:
            s[j]=1
        else:
            s[j]=0
    for k in range(m):
        cnt=0
        for j in v[k][1:]:
          cnt+=s[j-1]
        if cnt%2!=p[k]:
          break
    else:
        c+=1
print(c)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n, m = map(int, input().split())
    l = [list(map(int, input().split())) for i in range(m)]
    guki = list(map(int, input().split()))
    ans=0
    for i in range(2 ** n): # ｎは2進法にしたときの桁数
        # スイッチon/offリスト作る
        switch=[False]*n
        for j in range(n):
            # 一番右の桁から１になってるかどうかチェッ
            if (i >> j) & 1:
                switch[n-j-1]=True

        # 電球ごとに光ってるかチェック
        # 何個の電球が光ってるかカウント
        light=0
        for k in range(m):
            # 電球に対応しているスイッチが何個onになってるかカウント
            cnt=0
            for x in range(l[k][0]):
                if switch[l[k][x+1]-1]:
                    cnt+=1
            if cnt%2==guki[k]:
                light+=1
        if light==m:
            ans+=1
    print(ans)
resolve()

Submission status: Accepted

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

for i in range(1<<N):
    FLG = True
    for j,lst in enumerate(connected):
        count2 = 0
        for s in lst[1:]:
            if (i>>(s-1)) & 1:
                count2 += 1
        if count2 % 2 != condition[j]:
            FLG = False
            break
    if FLG:
        ans += 1

print(ans)

Submission status: Accepted

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

for i in range(1<<N):
    count1 = 0
    for j,lst in enumerate(connected):
        count2 = 0
        for s in lst[1:]:
            if (i>>(s-1)) & 1:
                count2 += 1
        if count2 % 2 == condition[j]:
            count1 += 1
    if count1 == M:
        ans += 1

print(ans)

Submission status: Accepted

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


case_cnt = 0
for i in range(2**N):
  bulbs = []
  ons = []
  #N個のswitchがON/OFFの入力ケース作成
  for j in range(N):
    if (i >> j) & 1:
      ons.append(j)
  #print("case#{0} switch : {1}".format(i, ons))    
  #入力ケースに対するして、各電球ごとのSwithがONとなる数をカウント
  for k in range(M):
    cnt = 0
    for s in K[k][1:]:
      if s-1 in ons:
        cnt += 1
    #bulbsに電球が光ればTrue, 光らなければFalse
    if P[k] == cnt % 2 :
      bulbs.append(True)
    else:
      bulbs.append(False)
  #全電球が光っているのであれば、カウント
  if all(bulbs):
    case_cnt += 1
print(case_cnt)

Submission status: Accepted

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

# 各行のスイッチ
switches_list = []
for i in range(M):
    line = input().split()
    switch_count = int(line[0])
    switches = [0] * N
    for j in range(switch_count):
        switches[int(line[j + 1]) - 1] = 1
    switches_list.append(switches)
# print(switches_list)

# 余り
surpluses = input().split()

count = 0
# bit全検索
# on/offのような二択なら、自分で組み合わせを作らなくても
# 2のN乗の数値のビット演算で表現ができる
for k in range(2 ** N):
    for i in range(len(switches_list)):
        switches = switches_list[i]
        surplus = int(surpluses[i])
        on_count = 0
        for j in range(len(switches)):
            if switches[j] == 1 and ((k >> j) & 1):
                on_count += 1
        if on_count % 2 != surplus:
            break
        # 全電球分のチェックを通ったらOKとする
        if i == len(switches_list) - 1:
            count += 1
print(count)

Submission status: Accepted

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

rec = 0
for i in range(2**n):
    on_off = [0] * n

    for j in range(n):
        #j桁目が1の時
        if (i>>j)&1:on_off[j] = 1

    for j in range(m):
        on_cnt = 0
        for sj in s[j]:
            if on_off[sj - 1]:on_cnt = on_cnt^1

        if on_cnt != p[j]:break
    else:
        rec += 1
print(rec)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n,m=map(int, input().split())
    l=[list(map(int,input().split())) for i in range(m)]
    guki=list(map(int,input().split()))
    ans=0
    for i in range(2 ** n):
        cnt=[0]*m
        for j in range(n):  # このループが一番のポイント
            if ((i >> j) & 1):
                for k in range(m):
                    if j+1 in l[k][1:]:
                        cnt[k]+=1
        check = 0
        for x in range(m):

            if cnt[x]%2==guki[x]:
                check+=1
        if check==m:
            ans+=1
    print(ans)

resolve()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
k = []
l = []
ans = 0
for i in range(m):
    t = input().split()
    k.append(int(t[0]))
    l.append(list(map(int,t[1:])))
p = list(map(int,input().split()))
for i in range(2**n):
    sw = []
    for j in range(n):
        if (i>>j)&1:
            sw.append(True)
        else:
            sw.append(False)
    b = []
    for i in range(m):
        a = 0
        for si in l[i]:
            if sw[si-1]:
                a+=1
        b.append(a%2==p[i])
    ans+=all(b)
print(ans)

Submission status: Accepted

Solution code:
import math


def number2bit(n):
    return int(math.pow(2, n - 1))


def count_bit(n):
    return bin(n)[2:].count('1')


N, M = map(int, input().split(' '))
lights = [tuple(map(int, input().split(' ')))[1:] for _ in range(M)]
light_bits = [sum(map(number2bit, light)) for light in lights]
mods = tuple(map(int, input().split(' ')))

count = 0
for i in range(int('1' + '0' * N, base=2)):
    for light_bit, mod in zip(light_bits, mods):
        if count_bit(i & light_bit) % 2 != mod:
            break
    else:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import math


def number2bit(n):
    return int(math.pow(2, n - 1))


def count_bit(n):
    count = 0
    while n > 0:
        if n & 1 == 1:
            count += 1
        n >>= 1
    return count


N, M = map(int, input().split(' '))
lights = [set(tuple(map(int, input().split(' ')))[1:]) for _ in range(M)]
light_bits = [sum(map(number2bit, light)) for light in lights]
mods = tuple(map(int, input().split(' ')))

count = 0
for i in range(int(math.pow(2, N))):
    for j, light_bit in enumerate(light_bits):
        if count_bit(i & light_bit) % 2 != mods[j]:
            break
    else:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = []
s = []
for _ in range(m):
    inp = list(map(int, input().split()))
    k.append(inp[0])
    s.append(set(inp[1:]))
p = list(map(int, input().split()))
 
cnt = 0
for i in range(2 ** n):
    pattern = list(bin(i)[2:].zfill(n))
    lamp = p.copy()
    for j in range(n):
        if pattern[j] == "1":
            for l in range(m):
                if (j+1) in s[l]:
                    lamp[l] ^= 1
    f = False
    for j in range(m):
        f |= lamp[j]
 
    if not f:
        cnt += 1
 
print(cnt)

Submission status: Accepted

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

cnt = 0
for i in range(2 ** n):
    pattern = list(bin(i)[2:].zfill(n))
    ramp = p.copy()
    for j in range(n):
        if pattern[j] == "1":
            for l in range(m):
                if (j+1) in s[l]:
                    ramp[l] ^= 1
    f = False
    for j in range(m):
        f |= ramp[j]

    if not f:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N, M = MAP()
s = [LIST()[1:] for _ in range(M)]
p = LIST()
 
ans = 0
for x in product([0, 1], repeat=N):
	for i in range(M):
		cnt = 0
		for n in s[i]:
			if x[n-1] == 1:
				cnt += 1
		if cnt%2 != p[i]:
			break
	else:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N, M = MAP()
ks = [LIST() for _ in range(M)]
p = LIST()
 
ans = 0
for x in product([0, 1], repeat=N):
	#print(x)
	for i in range(M):
		cnt = 0
		for j in range(ks[i][0]):
			#print(i, ks[i][j+1])
			if x[ks[i][j+1]-1] == 1:
				cnt += 1
		if cnt%2 != p[i]:
			break
	else:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N, M = MAP()
ks = [LIST() for _ in range(M)]
p = LIST()
 
ans = 0
 
for i in range(1<<N):
	flg = True
	i = list("{:b}".format(i).zfill(N))
	#print(i)
	for j ,lis in enumerate(ks):
		lis = lis[1:]
		tmp = 0
		for l in lis:
			if i[l-1] == "1":
				tmp += 1
		if tmp%2 != p[j]:
			flg = False
			break
	if flg:
		ans += 1
 
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ks=[]
cnt=0
for _ in range(m):
    tmp=(list(map(int,input().split())))
    t=set([])
    for item in tmp[1:]:
        t.add(item-1)
    ks.append(t)
#print(ks)
p=list(map(int,input().split()))

for i in range(2**n):
    #print(bin(i))
    tmp=[0]*m
    for j in range(n):
        if i>>j&1==1:
            for index,item in enumerate(ks):
                if j in item:
                    tmp[index]+=1
    flag=0
    for index,item in enumerate(tmp):
        if item%2!=p[index]:
            flag=1
    if flag==0:
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, M = list(map(int,_in[0].split(' ')))  # type:list(int)
    k_arr = []
    s_arr = []
    for i in range(M):
        _ = list(map(int,_in[i+1].split(' ')))  # type:list(int)
        k_arr.append(_[0])
        s_arr.append(_[1:])
    p_arr = list(map(int,_in[M+1].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    for bit in range(1<<N):
        # bit = 0: off, 1: on
        for i in range(M):
            sum_ = 0
            for s in s_arr[i]:
                if bit&(1<<(s-1)): # on
                    sum_ += 1
            if sum_%2 != p_arr[i]:
                break
        else:
            cnt += 1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
sss=0
for c in itertools.product([0,1],repeat=n):
  ans=0
  for i in range(m):
    cnt=0
    for j in range(l[i][0]):
      if c[l[i][j+1]-1]==1:
        cnt+=1
    if cnt%2==p[i]:
      ans+=1
  if ans==m:
    sss+=1
print(sss)

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 i in range(2**N):
  bulb=[0]*M
  judge=True
  for j in range(N):
    if (i>>j)&1==1:
      for k in range(M):
        if j+1 in S[k]:
          bulb[k]+=1
  for t in range(M):
    if bulb[t]%2!=P[t]:
      judge=False
  if judge:
    ans+=1
            
print(ans)

Submission status: Accepted

Solution code:
import itertools
n , m = map(int,input().split())
sw = [[] for _ in range(m)]
for i in range(m):
    sw[i] = list(map(int,input().split()[1::]))
p = [int(x) for x in input().split()]
ans = 0

for tpl in itertools.product([0,1],repeat = n):
    bl = True
    for i in range(m):
        s = sum(tpl[s-1] for s in sw[i])
        if (s-p[i])%2 != 0:
            bl = False
            break
    if bl:
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ks = [LIST() for _ in range(M)]
p = LIST()

ans = 0

for i in range(1<<N):
	flg = True
	i = list("{:b}".format(i).zfill(N))
	#print(i)
	for j in range(M):
		cnt_sk = 0
		for k in range(ks[j][0]):
			#print(k, ks[j][k+1])
			#print(i[ks[j][k+1]-1] == "1")
			if i[ks[j][k+1]-1] == "1":
				cnt_sk += 1
		#print(cnt_sk)
		if cnt_sk%2 != p[j]:
			flg = False
	if flg:
		ans += 1

print(ans)

Submission status: Accepted

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

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

    res=0
    for SwichStatus in range(pow(2,N)):
        flag=0
        for i in range(M):
            Link=0
            for swich in swiches[i]:
                Link+=1<<(swich-1)
            OnSwich=SwichStatus&Link
            OnCounter=0
            while OnSwich!=0:
                OnCounter+=OnSwich&1
                OnSwich>>=1
            if OnCounter%2!=P[i]:
                flag=1
                break
        if flag!=1:
            res+=1
    print(res)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n,m = list(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):
    flag = True
    for j in range(m): #電球
        cnt = 0
        for k in range(1,len(ks[j])):
            w = ks[j][k]
            if i >> (w-1) & 1 :
                cnt+=1
        if cnt%2 != p[j]:
            flag = False
    if flag:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
kss=[list(map(int,input().split())) for _ in range(m)]
ps=list(map(int,input().split()))
ans=0
for i in range(2**n):
    stt=bin(i)[2:].zfill(n)
    cmp=0
    for ks,p in zip(kss, ps):
        c=0
        for k in ks[1:]:
            if stt[k-1]=='1':
                c+=1
        if c%2==p:
            cmp+=1
        else:
            break
    if cmp==m:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
import copy
k = [0 for i in range(m)]
ans = 0
import copy
for i in range(m):
    k[i] = list(map(int,input().split()))
p = list(map(int,input().split()))
for i in range(2**n):
    v = 1
    d = [0 for i in range(n)]
    q = copy.deepcopy(i)
    for j in range(n):
        if q &1:
            d[j] = 1
        q = q >> 1
    for g in range(m):
        u = 0
        for c in range(1,k[g][0]+1):
            u += d[k[g][c]-1]
        if u%2 == p[g]:
            continue
        else:
            v = 0
            break
    if v:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
k = []
s = []
for i in range(m):
    ks = list(map(int,input().split()))
    k.append(ks[0])
    s.append(ks[1:])
p = list(map(int,input().split()))
count = 0
for bit in range(2**n):
    counta = 0
    sw = [False for i in range(n)]
    for i in range(n):
        if bit >> i & 1:
            sw[i] = True
    for i in range(m):
        countb = 0
        for j in s[i]:
            if sw[j-1]:
                countb += 1
        if countb % 2 == p[i]:
            counta+=1
    if counta == m:
        count+=1
print(count)

Submission status: Accepted

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

# bit全探索
ans = 0
for i in range(2**n):
    c = 0

    # スイッチのOn/Offの状態
#    print (i,bin(i))

    # 各ライトについて
    for j in range(m):
        sum = 0
        for x in s[j]:
            sum += i >> x-1
        if sum%2==p[j]:
            c += 1
        if c == m:
            ans += 1

print (ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
#二次元リストに電灯と接続スイッチを入力
data = [] 
for i in range (m) :
  a=list(map(int,input().split()))
  a=a[1:]
  data.append(a)
#modはP系統を全部入力したリスト、要素数ｍ
mod = list(map(int,input().split()))
#ここからビット全探索開始
ans=0
for i in range (2**n):
  checker=0 #点灯する電球の数
  switch=[]#このパターンでONのスイッチ
  for j in range (n):
    if (i>>j)&1:
      switch.append(j+1)
  for x in range(m) :#各電球に対してチェック
    cnt=0 #オンになってる接続スイッチ数
    for k in switch:#switch内全要素探索
      if data[x].count(k)!=0:
        cnt+=1
    if cnt%2==mod[x]:
      checker+=1
  if checker == m:
    ans+=1
    
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
den_lists = []
for m in range(M):
    den_lists.append(list(map(int, input().split())))
p = list(map(int, input().split()))
count = 0

for i in range(2**N):
    s_list = []
    for j in range(N):
        if (i >> j) & 1:
            s_list.append(j+1)
    #print(f"s_list:{s_list}")     
    den_count = 0
    for m, den in enumerate(den_lists):
        tmp = 0
        for d in den[1:]:
            if d in s_list:
                tmp += 1# 繋がったスイッチのうち何個ついてるか
        #print(f"tmp:{tmp}")        
        if tmp % 2 == p[m]:
            #print(m)
            den_count += 1# 今のスイッチのon,offの組み合わせで全体の電球が何個ついてるか.
    #print(f"den_count:{den_count}")
        
    if den_count == len(den_lists):
        count += 1
        
    
    

print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
k=[]
s=[]
for i in range(m):
    l=list(map(int,input().split()))
    k.append(l[0])
    s.append(l[1:])
p=list(map(int,input().split()))
ans=0
for i in range(1<<n):
    cnt=0
    for j in range(m):
        sum=0
        for x in s[j]:
            sum+= i >> x-1
        if sum%2==p[j]:
            cnt+=1
        if cnt==m:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
import itertools
import heapq
import sys
sys.setrecursionlimit(10**6)

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
input_list = lambda : list(map(int,input().split()))


n,m=input_list()
a=[input_list() for _ in range(m)]
p=input_list()
ans=0
for i in range(2**n):
    bit=bin(i)[2:].zfill(n)
    flag=True
    for num,each in enumerate(a):
        now=0
        light=each[1:]
        #print(light)
        for v in light:
            
            if bit[int(v)-1]=="1":
                now=1-now
        if now!=p[num]:
            flag=False
            break
    if flag:
        ans+=1
print(ans)