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 = [int(i) for i in input().split()]
K = []
S = []
for mi in range(m):
    k, *s = [int(i) for i in input().split()]
    K.append(k)
    S.append(s)
P = [int(i) for i in input().split()]

ans = 0
for ni in range(2**n):
    bin_ni = format(ni, "010b")
    ok_flag = True
    for mi in range(m):
        sum_on = 0
        for ki in range(K[mi]):
            sum_on += int(bin_ni[-S[mi][ki]])
        if sum_on%2 != P[mi]:
            ok_flag = False
            break
    if ok_flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split(" ")))
sw=[]
for z in range(M):
  buf=list(map(int,input().split(" ")))
  k=buf[0]
  mask=0
  for x in range(1,k+1):
    mask|=2**(buf[x]-1)
  sw.append(mask)


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

cnt=0

for z in range(2**N):
  flag=True
  for i,x in enumerate(sw):
    y=z&x
    bitcount=0
    while y!=0:
      if y&1==1:
        bitcount+=1
      y=y>>1

    if bitcount%2!=p[i]:
      flag=False
  if flag:
    cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)

# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

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

	KS = []
	for i in range(M):
		tmp = input().split(" ")
		tmp = [int(s) for s in tmp]
		KS.append(tmp[1:])
	
	P = input().split(" ")
	P = [int(s) for s in P]

	ans = 0
	for den in range(0, 2**N):
		flg = True
		for j, val in enumerate(KS):
			tmp = 0
			for vol in val:
				aa = vol-1
				#print("{} {} {}".format(den, vol-1, (den & 2**aa) >> 1))

				if ((den & 2**(vol-1)) >> (vol-1)) == 1:
					tmp += 1
			if (tmp % 2) != P[j]:
				flg = False
		if flg == True:
			ans += 1

	print(ans)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import numpy as np
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(list(map(int,input().split())))
p=list(map(int,input().split()))
chk=[]
for i in range(m):
    tmp=[0]*n
    for k in range(1,len(l[i])):
        tmp[l[i][k]-1]+=1
    chk.append(np.array(tmp))
chk=np.array(chk)

cnt=n
sw=[]
for i in range(2**cnt):
    ln=[0]*cnt
    for j in range(cnt):
        if ((i>>j)&1):
            ln[cnt-j-1]=1
    sw.append(np.array(ln))
sw=np.array(sw)
cnt=0
for k in range(len(sw)):
    flag=True
    for i in range(m):
        if np.sum(sw[k]*chk[i])%2!=p[i]:
            flag=False
    if flag:
        cnt+=1
       
print(cnt)

Submission status: Accepted

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

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

import itertools

binary_list = [0, 1]

all_comb = list(itertools.product(binary_list, repeat=N))

count = 0

for sw_state in all_comb:
    flag = False
    
    for lamp, lamp_sw in zip(pre_list, binary_sw):
        swvalue = 0
        for lamp_single in lamp:
            swvalue += sw_state[lamp_single - 1]
        
        if swvalue % 2 == lamp_sw:
            continue
        
        else:
            flag = True
            break
        
        if flag:
            break

    if not flag:
        count += 1
        
print(count)

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
# import math
# import random
# import fractions
# import sys
# sys.setrecursionlimit(100000)
# N = int(stdin.readline().rstrip().split()[0])
# A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]
# S = stdin.readline().rstrip().split()[0]
N, M = [int(x) for x in stdin.readline().rstrip().split()]
K = []
S=[]
for i in range(M):
  A = [int(x) for x in stdin.readline().rstrip().split()]
  K.append(A[0])
  S.append(A[1:])
P = [int(x) for x in stdin.readline().rstrip().split()]
ans = 0
for i in range(2**N):
  bi = bin(1024+i)
  # print(bi)
  arr = [int(s=="1") for s in bi[13-N:]]
  # print(arr)
  Frag = True
  for j in range(M):
    sarr = S[j]
    on_sw = sum([arr[sidx-1] for sidx in sarr])
    if on_sw%2!=P[j]:
      Frag=False
      # print("x", sarr)
      break
  if Frag:
    # print(i, arr)
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy

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

switchs = []
for i in range(m):
    switchs.append([int(e) for e in input().split(" ")])

on_state = [int(e) for e in input().split(" ")]

switch_connect = numpy.zeros((m,n),dtype="int64")

for k,i in enumerate(switchs):
    for j in i[1:]:
        switch_connect[k,j-1] = 1

ret = 0
for i in itertools.product([0,1],repeat=n):
    result = numpy.dot(switch_connect, numpy.array(i).T)
    result = result%2
    ret += numpy.all(result == on_state)
print(ret)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections


N,M = map(int, sys.stdin.readline().rstrip().split(" "))
switches = []
for _ in range(M):
    k, *s = map(int, sys.stdin.readline().rstrip().split(" "))
    # switches.append(s)
    switch_bit = sum(2**(v-1) for v in s)
    # print(bin(switch_bit))
    switches.append(switch_bit)
ps = list(map(int, sys.stdin.readline().rstrip().split(" ")))



result = 0
for i in range(2**N):
    # print(bin(i))
    for j,switch in enumerate(switches):
        pattern = switch & i
        # print(bin(switch), bin(i), bin(switch & i), ps[j], bin(pattern).count("1") % 2 == ps[j])
        if not bin(pattern).count("1") % 2 == ps[j]:
            break
    else:
        result += 1
print(result)


exit(0)

Submission status: Accepted

Solution code:
from itertools import islice

R = lambda: map(int, input().split())
n, m = R()
a = [list(islice(R(), 1, None)) for _ in range(m)]
p = list(R())
r = sum(all(sum(i >> (j - 1) & 1 for  j in r) & 1 == pi
            for r, pi in zip(a, p)) for i in range(1 << n))
print(r)

Submission status: Accepted

Solution code:
import itertools
N,M = [int(x) for x in input().split()]
d = [[]]*M
for i in range(M):
    s = [int(x) for x in input().split()]
    d[i] = s[1:]
p = [int(x) for x in input().split()]

l = [(0,x) for x in range(1,N+1)]
kumi = itertools.product(*l)
ans = 0

for s in kumi:
    ok = True
    for i in range(M):
        if not ok:
            break
        if len(set(s) & set(d[i]))%2 != p[i]:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = [list(map(int, input().split()))[1::] for _ in range(M)]
P = list(map(int, input().split()))
ans = 0
for i in range(2 ** N):
    f = True
    bag = []
    jotai = [False for _ in range(M)]
    for j in range(0, N):  # このループが一番のポイント
        if (i >> j) & 1:  # 順に右にシフトさせ最下位bitのチェックを行う
            bag.append(j + 1)

    # for k, s in enumerate(S):
    #     total = 0
    #     for l in range(len(s)):
    #         for b in range(len(bag)):
    #             if l == b:
    #                 total += 1
    #     # print(total, k)
    #     if total % 2 == P[k]:
    #         jotai[k] = True
    #     if all(jotai):
    #         ans += 1

    for s in S:
        total = 0
        for ss in s:
            if ss in bag:
                total += 1
        if total % 2 != P[S.index(s)]:
            f = False
    if f:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
i = input().split(" ")

N = int(i[0])
M = int(i[1])

m = []

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

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

from itertools import product

co = 0

s = list(product([True, False], repeat=N))

for comb in s:
	#print(comb)
	allon = True
	for l, b in enumerate(m):
		look = [comb[i - 1] for i in b]
		#print(l, look)
		if look.count(True) % 2 != p[l]:
			allon = False
			break
	if allon:
		co += 1

print(co)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
SWs = []
# 電球がどのスイッチに繋がっているか
from collections import defaultdict
d = defaultdict(list)
for i in range(N):
    d[i+1].append(0)


for i in range(M):
    As = list(map(int,input().split()))
    SWs.append(As[1:])
    for A in As[1:]:
        d[A].append(i+1)

# 正しい電球のON状態
ps = list(map(int,input().split()))
ans = 0

# スイッチ状態の全通り
for i in range(2**N):
    light = [0] * (M+1)
    flg = True
    x = bin(i)[2:]
    #調整
    a = "0"*(N-len(x))+x
    for i,s in enumerate(a):
        if int(s) == 0:
            for A in d[i+1]:
                light[A] += 1
    # print(a,light,ps)
    for p,l in zip(ps,light[1:]):
        if p != l%2:
            flg = False
    if flg:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M = (int(i) for i in input().split())

l = [[0] * N for i in range(M)]

for x in range(M):
    s = [int(i) for i in input().split()]
    for ind in range(1, s[0]+1):
        l[x][s[ind]-1] = 1

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

res = 0
all = list( itertools.product([0,1], repeat=N))

for pos in all:
    f = True
    for dn in range(M):
        r = 0
        for mm in range(len(pos)):
            r += pos[mm] * l[dn][mm]
            r = r % 2
        if p[dn] != r:
            f = False
    if f :
        res += 1


#print(all)
print(res)
#print(l)

Submission status: Accepted

Solution code:
from sys import stdin
from numpy import array
from numpy import dot
import itertools


def main():
     n,m = [int(x) for x in stdin.readline().split()]
     A = array([[0]*n for _ in range(m)])
     for i in range(m):
          tmp = [int(x) for x in stdin.readline().split()]
          for j in tmp[1:]:
               A[i][j-1] = 1
     k = array([int(x) for x in stdin.readline().split()])
     swt = [0,1]
     
     ans = 0
     for i in itertools.product(swt, repeat=n):
          i = array(i)
          Ai = dot(A,i)
          if (Ai%2 == k).all():
               ans += 1
     print(ans)
          
     
if __name__ == '__main__':
     main()

Submission status: Accepted

Solution code:
def solve(n, m, list1, listp):
    cnt = 0
    loopflag = 0
    for i in range(2**n):
        list2 = [(i%(2**(j+1)))//(2**j) for j in range(n)]  #スイッチリスト生成
        for j in range(m):  #j番目の電球について
            s = sum([list2[k] for k in list1[j][1:]])
            if s%2 != listp[j]:
                loopflag = 1
                break
        if loopflag == 0:
            cnt += 1
        loopflag = 0
    return cnt

n, m = map(int, input().split())
list1 = []
for i in range(m):
    list1 += [list(map(int, input().split()))]
    list1[i][1:] = list(map(lambda x: x-1, list1[i][1:]))
listp = list(map(int, input().split()))
print(solve(n, m, list1, listp))

Submission status: Accepted

Solution code:
#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
#n=int(input())
#import fractions
#S=input()
#import math
#n=int(input())

ans=0
lis=list(map(int,input().split()))
k=[]
for i in range(lis[1]):
    a=list(map(int,input().split()))
    k.append(a)
p=list(map(int,input().split()))
for i in range(2**lis[0]):
    a=str(bin(2**(lis[0]+1)-i-1))[3:]
    #print(a)
    for j in range(lis[1]):
        flag=0
        s=0
        for l in range(k[j][0]):
            s+=int(a[k[j][l+1]-1])
        if s%2!=p[j]:
            flag=1
            break
    if flag==0:
        ans+=1


print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
d = dict()
cnt = 0
for i in range(n):
  d[i] = []
for x in range(m):
  s = list(map(int, input().split()))
  for i in s[1:]:
    d[i-1].append(x)
p = list(map(int, input().split()))
for bi in range(2**n):
  l = [0]*m
  for k in range(n):
    if bi & 2**k:
      for x in d[k]:
        l[x] = 1-l[x]
  if l == p:
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
#for i in range(b):
#    A=list(map(int,input().split()))
As=[]
for i in range(b):
    A=list(map(int,input().split()))
    As.append(A)
B=list(map(int,input().split()))

count=0
arr=[]
for i in range(2**a):
    tmp=bin(i)
    tmparr=[int(j) for j in tmp[2:]]
    while len(tmparr)<a:
        tmparr.insert(0,0)
    #arr.append(tmparr)
    #print(tmparr)

    for num,j in enumerate(As):
        on=0
        flag=1
        #print(j,tmparr)
        for k in j[1:]:
            on=on^tmparr[k-1]
        if  B[num]!=on:
            flag=0
            break
            #count+=1
            #print(tmparr)
    if flag==1:
        count+=1
print(count)

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

out = 0
for i in range(2 ** n):
    i2 = bin(i)[2:].zfill(n)
    flag = True

    for j in range(m):
        k = int(ks[j][0])
        s = ks[j][1:]
        _p = p[j]

        total = 0
        for _s in s:
            total += int(i2[_s - 1])

        if total % 2 != _p:
            flag = False

    if flag:
        out += 1
print(out)

Submission status: Accepted

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

s = []
for i in [0]*M:
	s.append(list(map(int,input().split(' ')))[1:])

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

bs = []
for t in s:
	rep = 0
	for i in t:
		rep += (1 << (i-1))
	bs.append(rep)

ans = 0
for i in range(0,2**N):
	f = True
	for j,cp in zip(bs,p):
		ch = i & j
		if (bin(ch).count("1") - cp) % 2:
			f = False
			break
	if f:
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

tmp = [[int(x) for x in input().split(' ')] for i in range(M)]
k, s = zip(*[(t[0], t[1:]) for t in tmp])
p = [int(x) for x in input().split(' ')]

pats = itertools.product([0,1], repeat=N)

count = 0
for pat in pats:
    flag = True
    for m in range(M):
        tmp = [pat[ss-1] for ss in s[m]]
        flag = flag and sum([pat[ss-1] for ss in s[m]]) % 2 == p[m]
    if flag:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import numpy as np

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

def transform_sw(sw):
    if sw[0] == 0:
        sw[0] = 1
        return sw
    else:
        sw[0] = 0

    for i, s in enumerate(sw[1:]):
        if s == 0:
            sw[i + 1] = 1
            return sw
        elif s == 1:
            sw[i + 1] = 0
    
    return sw


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

e_balls = []

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

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

sw = np.array([0 for _ in range(N)])
cnt = 0

while np.sum(sw == 1) != N:
    if test_switch(e_balls, sw, p):
        cnt += 1
    transform_sw(sw)

if test_switch(e_balls, sw, p):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=[]
total = 0
for i in range(M):
  iin = list(map(int,input().split()))
  k = iin[0]
  sin = 0
  for j in range(k):
    sin |= 1 << (iin[j+1] - 1) 
  S.append(sin)
p = list(map(int,input().split()))
for i in range(2**N):
  ok = 1
  for j in range(M):
    tmp = i & S[j]
    tmp2 = 0
    for ii in range(10):
      tmp2 += ((tmp >> ii) & 1)
    if (tmp2%2) != p[j]:
      ok = 0
      break
  if ok == 1:
    total += 1
print(total)

Submission status: Accepted

Solution code:
import itertools
n,m = map(int, input().split())
ks = []
c = 0
for i in range(m):
  ks.append(list(map(int, input().split())))
p = list(map(int, input().split()))
for i in list(itertools.product((0,1), repeat=n)):
  count = 0
  for j in ks:
    if sum([i[j[k+1]-1] for k in range(len(j)-1)]) % 2 == p[ks.index(j)]:
      count += 1
  if count == m:
    c += 1
print(c)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    s = []

    for _ in range(m):
        r = [int(x) for x in input().split()]
        s.append(r[1:])
    
    p = [int(s) for s in input().split()]

    print(solve(m, n, s, p))

def solve(m, n, s, p):
    c = 0
    for bits in range(2 ** n):
        for i in range(m):
            if not check(bits, s[i], p[i]):
                break
        else:
            c += 1
    return c

def check(bits, si, pi):
    n = 0
    for sij in si:
        if bits & (1 << (sij - 1)):
            n += 1
    
    if n % 2 == pi:
        return True

    return False


main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
klist = []
slist = []
for i in range(M):
  ks = list(map(int,input().split()))
  klist.append(ks[0])
  slist.append(ks[1:])
plist = list(map(int,input().split()))

cnt = 0
for i in range(2**N):  
  sbin = format(i, '0'+str(N)+'b')
  
  ison = True
  for j in range(M):
    cnt_k = 0
    for sk in slist[j]:
      if sbin[sk-1] == "1":
        cnt_k += 1
      
    if cnt_k%2 != plist[j]:
      ison = False
      break
      
  if ison:
    cnt += 1
    
print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,raw_input().split())
switch = []
for i in xrange(m):
	a = map(int,raw_input().split())
	conn = [0]*n
	for x in a[1:]:
		conn[x-1] = 1
	switch.append(conn)
p = map(int,raw_input().split())
res = 0
for i in xrange(2**n):
	temp = i
	lit = [0]*m
	for j in xrange(n):
		if temp%2 == 1:
			for b in xrange(m):
				if switch[b][j]:
					lit[b] += 1
		temp /= 2
	res += 1
	for j in xrange(m):
		if lit[j]%2 != p[j]:
			res -= 1
			break
print res

Submission status: Accepted

Solution code:
from operator import itemgetter
import itertools

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

cnt = 0

for b in list(itertools.product(range(2),repeat = N)):
  flag = 1
  for i in range(M):
    k = L[i][0]
    b_sum = 0
    for j in range(1,k+1):
      b_sum += b[L[i][j]-1]
    if b_sum % 2 != P[i]:
      flag = 0
  if flag == 1:
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
L = [[int(i) - 1 for i in input().split()] for _ in range(M)]
P = [int(i) for i in input().split()]

ans = 0
for i in range(2 ** N):
    su = 0
    for k in range(M):
        count = 0
        for l in L[k][1:]:
            if (i >> l) & 1:
                count += 1
        if count % 2 == P[k]:
            su += 1
    if su == M:
        ans += 1
print(ans)

Submission status: Accepted

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

def count_one(s):
    return bin(s).count('1')

all_pat = [i for i in range(2**N)]
masks = [sum([2**(s-1) for s in ks[1:]]) for ks in kss]

res = [sum([1 for i, mask in enumerate(masks) if count_one(pat & mask)%2 == ps[i]]) for pat in all_pat]
print(res.count(M))

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

count = 0
for i in range(2 ** N):
    state = ''.join(list(reversed(str(bin(i))[2:].zfill(N))))
    flg = True
    for m in range(M):
        on = 0
        for s in S[m]:
            if state[s - 1] == '1':
                on += 1
        if on % 2 != P[m]:
            flg = False
            break
    if flg:
        count += 1
print(count)

Submission status: Accepted

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

ans=0
for i in range(2**N):
	for m in range(M):
		tmp=0
		for s in S[m]:
			tmp+=( i>>(N-s) ) & 1

		tmp%=2

		if tmp!=P[m]:
			break
	else:
		ans+=1

print ans

Submission status: Accepted

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

s_list = []

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

    s_list.append(s)

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

on_off_list = [0] * N


def rec(index_on_off):

    if index_on_off == N:

        all_on = True

        for index_m in range(M):

            on_count = 0

            for s_value in s_list[index_m]:
                if on_off_list[s_value - 1] == 1:
                    on_count += 1

            if (on_count % 2) != p[index_m]:
                all_on = False

        if all_on:
            return 1
        else:
            return 0

    counter = 0

    on_off_list[index_on_off] = 0
    counter += rec(index_on_off + 1)

    on_off_list[index_on_off] = 1
    counter += rec(index_on_off + 1)

    return counter


print(rec(0))

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
dic = []
for i in range(m):
    dic.append(list(map(int, input().split()))[1:])
P = list(map(int, input().split()))
cn = 0
for i in range(2**n):
    b = format(i,"b").rjust(n)
    for j in range(m):
        swcn = 0
        for s in dic[j]:
            swcn += 1 if b[s-1] == "1" else 0
        if swcn%2 != P[j]: break
    else:
        cn += 1
print(cn)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    num = 0
    for j in range(N):
        if (i >> j) & 1 == 1:
            SS[j] = 1
    flg = True
    for j, s in enumerate(S):
        num = 0
        for e in s:
            if SS[e-1] == 1:
                num += 1
        if num % 2 != P[j]:
            flg = False
            break
    if flg:
        ans += 1
    SS = [0] * N   
print(ans)

Submission status: Accepted

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

C=0

for i in range(2**n):
    bin_i=format(i,'b')
    l=len(bin_i)
    for j in range(n-l):
        bin_i='0'+bin_i
    bin_i=list(bin_i)
    # print(bin_i)

    count=0

    for j in range(m):
        check=line[j]
        # print(check)
        s=0
        for k in range(check[0]):
            s+=int(bin_i[check[k+1]-1])
        s+=p_line[j]
        if s%2==0:
            count+=1
    
    # print(count)
    if count==m:
        C+=1
        # print('OK')

print(C)

Submission status: Accepted

Solution code:
from sys import stdin
import math
import fractions
from collections import deque
import itertools

INF = 10 ** 10

# N個のスイッチとM個の電球
N, M = [int(x) for x in stdin.readline().rstrip().split()]
ks =  [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]
p = [int(x) for x in stdin.readline().rstrip().split()] # 0 or 1

# on:1 off;0
nums = [0, 1]
data = list(itertools.product(nums, repeat=N))

ans = 0

for d in data:
    result = True
    for i in range(M):
        k = ks[i][0]
        s = ks[i][1:]

        count = 0
        for ss in s:
            count += d[ss-1]

        if count % 2 != p[i]:
            result = False
            break
    
    if result:
        ans += 1
        
print(ans)

Submission status: Accepted

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

for i in range(2**N):
    sw = [(i//2**x)%2 for x in range(N)]
    for j in range(M):
        a = True
        sums = 0
        for k in range(s[j][0]):
            if sw[s[j][k+1]-1] == 1:
                sums += 1
        if sums%2 != p[j]:
            a = False
            break
    if a:   ans += 1

print(ans)

Submission status: Accepted

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

K = []

for i in range(m):
    l = list(map(int,input().split()))
    K.append(l[1:])
res = 0
p = list(map(int,input().split()))
for s in itertools.product([0,1],repeat=n):
    cnt = [0]*m
    for j in range(len(s)):
        if s[j] == 0:
            continue
        for k in range(len(K)):
            if (j+1) in K[k]:
                cnt[k]+=1
    flag = True

    for j in range(len(cnt)):
        if cnt[j]%2 != p[j]:
            flag = False
            break
    if flag:
        res += 1 
print(res)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
A=[list(map(int,input().split())) for i in range(m)]
#print(A)
P=list(map(int,input().split()))
B=[]
for i in range(2**n):
    B.append(format(i,'b').zfill(n))
#print(B)


ans = 0
for i in range(len(B)):
    ok = 1
    for j in range(m): # 電球
        aa = 0
        for k in range(1,len(A[j])):
            if B[i][A[j][k]-1]=="1":
                aa += 1
        #print(aa)
        if aa%2 != P[j]:
            ok=0
    if ok==1:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:

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

ps  = list(map(int,input().split(" ")))
ans = 0
for i in range(2 ** N):
    temp = [0] * M
    for j in range(0,N): #スイッチを押していく
        if ((i >> j) & 1): #スイッチjが押されている状態ならスイッチを押す
            for di,denkyu in enumerate(denkyus):
                if j+1 in denkyu:
                    temp[di] +=1

    for pind,p in enumerate(ps):
        flag = True
        if temp[pind] %2 != p:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 2  # type: int


def main():
    N, M = map(int, input().split())
    K = []
    S = []
    for _ in range(M):
        kk, *rest = map(int, input().split())
        K.append(kk)
        S.append(rest)
    P = list(map(int, input().split()))
    # print(N, M)
    # print(K, S, P)

    counter = 0
    for n in range(2**N):    # 全探索
        flag = True
        # print("{0:04b}".format(n))
        for k, s, p in zip(K, S, P):
            # print(k, s, p)
            sumof = 0
            for ss in s:
                sumof += (n >> (ss-1))
            sumof %= 2
            if sumof != p:
                flag = False
                break
        if flag:
            counter += 1
    print(counter)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
K = [[int(i) for i in input().split()] for j in range(M)]
P = [int(i) for i in input().split()]
ALL = 0
for i in range(2**N):
    state = [((i >> j) & 1) for j in range(N)]
    for j in range(M):
        k = K[j][1:]
        p = sum([int(state[l-1]) for l in k])%2
        if p != P[j]:
            break
    else:
        ALL += 1
print(ALL)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
data = []
for x in range(M):
    line = input().split()
    data.append(list(map(int, line[1:])))
turns = list(map(int, input().split()))

def check(i, s, data, turns):
    count_on = 0
    for x in data[i]:
        if s[x - 1] == '1':
            count_on = count_on + 1
    return count_on % 2 == turns[i]

def exec(s, n, data, turns, cases):
    if n == 0:
        ans = True
        for x in range(M):
            if check(x, s, data, turns) == False:
                ans = False
                break
        if ans == True:
            # print(s)
            cases.append(1)
        return
    for i in range(2):
        exec(s + str(i), n - 1, data, turns, cases)

cases = []
exec('', N, data, turns, cases)
print(len(cases))

Submission status: Accepted

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

for i in range(M):
    li = list(map(int, input().split()))
    ki = li[0]
    for sij in li[1:]:
        S[i][sij - 1] = 1
P = list(map(int, input().split()))

# print(S)

states = [0 for _ in range(N)]

def dfs(j, jon, states):
    if j == N:
        return 1 if isok(states) else 0
    states[j] = 1 if jon else 0
    count = 0
    count += dfs(j + 1, True, states)
    count += dfs(j + 1, False, states)
    return count

def isok(states):
    for i in range(M):
        x = 0
        for j in range(N):
            x += states[j] if S[i][j] == 1 else 0
        if x % 2 != P[i]:
            return False
    return True

ans = dfs(0, True, states) + dfs(0, False, states)
print(ans // 2)

Submission status: Accepted

Solution code:
from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

N, M = [int(x) for x in input().split(" ")]
Ss = [0] * N
bulbs = []
for i in range(M):
    s = [int(x) for x in input().split(" ")]
    k = s[0]
    ss = set(s[1:])
    bulbs.append(ss)
ps = [int(x) for x in input().split(" ")]
bulbs = list(zip(bulbs, ps))

def checkPattern(subset, bs, p):
    inter = subset.intersection(bs)
    res = len(inter) % 2 == p
    return res

count = 0
for subset in powerset(set(range(1, N+1))):
    subset = set(subset)
    pts = [checkPattern(subset, bs, p) for bs, p in bulbs]
    if all(pts):
        count += 1

print(count)