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:
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
lt = [p for p in it.product([0,1], repeat=n)]

ans = 0
for p in lt:
  lj = []
  for l in ll:
    lj.append(sum(a*b for a, b in zip(p,l))%2)
  if lp == lj:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
def fbit(k,n):
    t=[]
    kk=k
    for i in range(n):
        t.append(kk%2)
        kk=int(kk/2)
    return t        

n,m=map(int,input().split())
s=[]
for i in range(m):
    si=[]
    for j in range(n):
        si.append(0)
    s.append(si)
    
for j in range(m):
    str=input().split()
    k_m=int(str[0])
    for k in range(k_m):
        ii=int(str[k+1])-1
        s[j][ii]=1

str=input().split()
p=[]
for k in range(m):
    p.append(int(str[k]))

icnt=0
for k in range(2**n):
    icnt2=0
    bit=fbit(k,n)
    for im in range(m):
        icnt3=0
        for kn in range(n):
            icnt3=icnt3+bit[kn]*s[im][kn]
        if icnt3%2==p[im]:
            icnt2=icnt2+1
    if icnt2==m:
        icnt=icnt+1
print(icnt)

Submission status: Accepted

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

sss = []
for _ in range(M):
    k, *ss = map(lambda x: int(x) - 1, input().split())
    sss.append(ss)
ps = list(map(lambda x: x == '0', input().split()))

# print(ps)

# 全てのスイッチのパターンをチェック
cnt = 0
for i in range(2 ** N):
    lights = ps[:]
    # print(bin(i))
    for j, ss in enumerate(sss):
        for s in ss:
            if i >> s & 1:
                lights[j] = not lights[j]
    # print(ps)
    if all(lights):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
skss = []
for _ in range(M):
    k, *sks = map(int, input().split())
    skss.append(set(sks))
pMs = list(map(lambda x: x == '0', input().split()))

count = 0
for i in range(2 ** N):
    pMstmp = pMs[:]
    for j, b in enumerate(format(i, '0' + str(N) + 'b')):
        if b == '0':
            continue
        for k, sks in enumerate(skss):
            if j + 1 in sks:
                pMstmp[k] = not pMstmp[k]
    if all(pMstmp):
        count += 1

print(count)

Submission status: Accepted

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

sss = []
for _ in range(M):
    k, *ss = map(lambda x: int(x) - 1, input().split())
    sss.append(ss)
ps = list(map(lambda x: x == '0', input().split()))

# 全てのスイッチのパターンをチェック
cnt = 0
for i in range(2 ** N):
    lights = ps[:]
    for j, ss in enumerate(sss):
        for s in ss:
            if i >> s & 1:
                lights[j] = not lights[j]
    if all(lights):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
bulbs = []
for _ in range(m):
    bulbs.append([int(i) for i in input().split()][1:])

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


def all_on(switches):
    for idx, bulb in enumerate(bulbs):
        switched = 0
        for s in bulb:
            switched = 1 - switched if s in switches else switched
        if switched != conds[idx]:
            return 0
    return 1


def count_all_right(curr_switches, pos):
    if pos == n - 1:
        return all_on(curr_switches) + all_on(curr_switches + [pos + 1])
    return count_all_right(curr_switches + [pos + 1], pos + 1) + count_all_right(
        curr_switches, pos + 1
    )


print(count_all_right([], 0))

Submission status: Accepted

Solution code:
import numpy as np
n, m = map(int, input().split())

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

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

ans = 0
# bit全探索
for t in range(2 ** n):
  # N個のスイッチのうち,onになっているスイッチの数を調べる
  on_switch_list = np.array([t >> s & 1 for s in range(n)])
  
  # 各電球に対しonになっているスイッチの合計%2のリストを作り,pと等しければカウント
  # iは 1 ~ Mの値を取るので-1してインデックスに使えるように
  if p == [np.sum(on_switch_list[np.array(i) - 1]) % 2 for i in switches]:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import _collections
import string

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

def main():
    N,M = cin.mapInt()
    S = [[] for i in range(N)] 
    for i in range(M):
        s = cin.mapInt()
        k = s[0]
        for j in range(k):
            a = s[j + 1] - 1
            S[a].append(i)
    ans = 0
    P = cin.mapInt()
    for i in range(1 << N):
        tmp = [0] * M
        isOK = True
        for j in range(N):
            if i >> j & 1:
                for k in S[j]:
                    tmp[k] += 1
        for j in range(M):
            if P[j] % 2 != tmp[j] % 2:
                isOK = False
        if isOK:
            ans += 1
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Mat = [[0 for i in range(N)] for i in range(M)]
for i in range(M):
  sw = list(map(int, input().split()))
  for j in range(1, sw[0]+1):
    Mat[i][sw[j]-1] = 1
p = list(map(int, input().split()))
pat = 2**N
cnt = 0
for i in range(pat):
  A = []
  for j in range(N):
    A.append(i%2)
    i //= 2
  B = [sum(A[i]*Mat[j][i] for i in range(N)) % 2 for j in range(M)]
  if B == p:
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = [list(map(int,input().split()))[1:]for i in range(m)]
p = list(map(int,input().split()))
form = "0"+str(n)+"b"
ans = 0
for i in range(2**n):
    ptn = format(i,form)
    light = True
    for j in range(m):
        s = sum(int(ptn[k-1])for k in l[j])
        if s%2 != p[j]:
            light = False
    if light == True:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
n, m = map(int, input().split())
cnct = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))

ans = 0

for i in range(2 ** n):
    for idx, j in enumerate(cnct):
        switch_num = j[0]
        res = 0
        for k in range(1, switch_num + 1):
            if i & (1 << (j[k] - 1)):
                res += 1
        if res % 2 == p[idx]:
            continue
        else:
            break
        
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

N, M = [int(i) for i in input().split()]
KS = []
for _ in range(M):
    KS.append(tuple([int(i) for i in input().split()]))
P = tuple([int(i) for i in input().split()])

ans = 0
for t in itertools.product([0, 1], repeat=N):
    for m in range(M):
        if sum(t[x - 1] for x in KS[m][1:]) % 2 != P[m]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    x = str(bin(i))[2:]
    if len(x) < n:
        x = "0" * (n - len(x)) + x
    a = 1
    for j in range(m):
        check = 0
        for k in light[j][1:]:
            if x[k-1] == "1":
                check += 1
        if check % 2 != p[j]:
            a = 0
            break
    if a:
        ans += 1
print(ans)

Submission status: Accepted

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

k = []
s = []
switch = list([[0 for i in range(m)]for i in range(n)])
switch_1 = [0 for i in range(n)]
cnt = 0

for i in range(1,len(p)+1):
    if p[i-1] == 1:
        cnt += 2**(m-i)
    if i == m:
        p_1 = cnt

for i in range(m):
    k.append(k_and_s[i][0:1][0])
    s.append(k_and_s[i][1:])

for i in range(len(s)):
    for j in range(len(s[i])):
        switch[s[i][j]-1][i] = 1

for i in range(len(switch)):
    cnt = 0
    for j in range(1,len(switch[i])+1):
        if switch[i][j-1] == 1:
            cnt += 2**(m-j)
        if j == m:
            switch_1[i] = cnt

ans = 0
for i in range(1<<n):
    t = 0
    for j in range(n):
        if i >> j & 1 != 0:
            t ^= switch_1[j]
    if t==p_1:
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  l=[]
  for _ in range(m):
    a=LI()
    l.append(a[1:])

  lp=LI()

  a=[]
  for i in range(1<<n):
    _a=[]
    for j in range(n):
      if i&(1<<j):
        _a.append(1)
      else:
        _a.append(0)
    a.append(_a)

  ans=0
  for x in a:
    f=True
    for i,y in enumerate(l):
      _sum=0
      for z in y:
        _sum+=x[z-1]
      if _sum%2!=lp[i]:
        f=False
        break
    if f:
      ans+=1

  return ans

# main()
print(main())

Submission status: Accepted

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

for i in range(2**n):
    check2 = [0]*m
    for j in range(n):
        if ((i>>j) & 1):
            for k in range(m):
                
                if j+1 in check[k]:
                    check2[k] += 1
                    
    check3 = True
    for l in range(m):
        if check2[l]%2 != p[l]:
            check3 = False
    if check3 :
        count += 1
        

print(count)

Submission status: Accepted

Solution code:

si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
snm = lambda: map(str, input().split())
nl = lambda: list(map(int, input().split()))

n,m=nm()
s=[]
o=[]
for i in range(m):
    s.append(nl())
p=nl()

for i in range(2**n):
    op = [0]*n
    for j in range(n):
        if ((i>>j)&1):
            op[n-1-j]=1
    o.append(op)

ans=0
denkyu=0
for oo in o:
    denkyu=0
    for i in range(m):
        cnt=0
        k=s[i][0]
        for j in range(k):
            if oo[s[i][j+1]-1]==1:
                cnt+=1
        if cnt%2==p[i]:
            denkyu+=1
    if denkyu==m:ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
li = [list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
#n進数への変換関数の定義
#Python 3.7とかではデフォであるが，Python 3.4.3(AtCoder仕様)ではまだない
########10進法からn進法への変換関数部分##############
def format(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out
############################

########10進法からn進法への変換関数(m桁埋める)部分##############
def format0(X, n, m):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    if len(out) < m:
        out = "0" * (m - len(out)) + out
    return out
############################
ans = 0
for i in range(2**n):
  i = format0(i,2,n)
  switch = [int(i[j]) for j in range(n)]
  on=0
  for j in range(m):
    if sum([switch[li[j][l+1]-1] for l in range(li[j][0])]) % 2 == p[j]:
      on += 1
  if on == m:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split()))[1:] for i in range(m)]
p=list(map(int,input().split()))
form = "0" + str(n) + "b"
ans=0
for i in range(2**n):
	ptr = format(i,form)
	flg = True
	for j in range(m):
		s= sum(int(ptr[k-1]) for k in l[j])
		if s%2 != p[j]:
			flg = False
	if flg == True:
		ans+=1
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()

  l=[]
  for _ in range(m):
    a=LI()
    l.append(a[1:])

  l2=LI()

  pattern=[]
  for i in range(1<<n):
    _l=[]
    for j in range(n):
      _l.append(1 if i&(1<<j) else 0)
    pattern.append(_l)

  ans=0
  for x in pattern:
    f=True
    for i,y in enumerate(l):
      on_num=0
      for z in y:
        on_num+=x[z-1]

      if not f:
        break
      if f and l2[i]!=on_num%2:
        f=False
        break

    if f:
      ans+=1

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
slis=[]
counter=0
for i in range(m):
	s=list(map(int,input().split()))
	s.remove(s[0])
	slis.append(s)
plis=list(map(int,input().split()))

for i in range(2**n):
	sw_st=list(format(i,"b").zfill(n))
	alis=[]
	for j in range(m):
		c=0
		for k in range(n):
			if sw_st[k]=="1" :
				if k+1 in slis[j]:
					c+=1
		alis.append(c%2)
	if alis==plis:
		counter+=1
print(counter)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
KS = []
for _ in range(M):
    KS.append(tuple(map(int, input().split())))
P = tuple(map(int, input().split()))

ans = 0
for t in itertools.product([0, 1], repeat=N):
    for m in range(M):
        if sum(t[x - 1] for x in KS[m][1:]) % 2 != P[m]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

for i in range(M):
    a=list(map(int,input().split()))
    k[i]=a[0]
    s[i]=a[1:]
    s[i].sort()

p=list(map(int,input().split()))
    
ans=0
for i in range(pow(2,N)):
    light=0
    for j in range(M):
        temp=0
        for kk in range(k[j]):
            a=i>>(s[j][kk]-1)
            if a&1==1:
                temp+=1
        if temp%2!=p[j]:
            break
        light+=1
    if light==M:
        ans+=1
               
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split(" "))
    S = []
    for _ in range(M):
        tmp = list(map(int, input().split(" ")))[1:]
        binary_s = 0
        for t in tmp:
            binary_s += 2 ** (t - 1)
        S.append(binary_s)
    P = list(map(int, input().split(" ")))
    result = 0
    for i in range(2 ** N):
        for s, p in zip(S, P):
            if not bin(s & i).count("1") % 2 == p:
                break
        else:
            result += 1
    print(result)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
switchState = [0]*n


def dfs(i, tukeru):
    #print(i, tukeru)
    if(i == n):
        sumOfTento = 0
        for denkyu in range(m):
            sumOfswitch = 0
            for switch in switches[denkyu]:
                sumOfswitch += switchState[switch-1]
            if(sumOfswitch % 2 == p[denkyu]):
                sumOfTento += 1
        # print(switchState)
        if(sumOfTento == m):
            return 1
        else:
            return 0
    switchState[i] = tukeru
    return dfs(i+1, 0) + (dfs(i+1, 1) if i != n-1 else 0)


print(dfs(0, 0)+dfs(0, 1))

Submission status: Accepted

Solution code:
import sys
 
 
def check(bits, M, k, s, p):
    for x in range(M):
        dec = 0
        for K in range(k[x]):
            if bits >> (s[x][K] - 1) & 1:
                dec += 1
            else:
                pass
 
        if dec % 2 == p[x]:
            pass
        else:
            return 0
 
    return 1
 
 
def main():
    N, M = map(int, input().split())
 
    k = [0] * M
    s = [0] * M
    for i in range(M):
        k[i], *s[i] = map(int, input().split())
 
 
    p = list(map(int, input().split()))
 
    ans = 0
    for bits in range(2 ** N):
        ans += check(bits, M, k, s, p)
 
    print(ans)
 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans=0
for bit in range(1<<n):
  x=0
  for i in range(m):
    y=0
    for j in s[i]:
      if bit&(1<<(j-1)):
        y+=1
    if y%2==p[i]%2:
      x+=1
  if x==m:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

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

li = [0,1]
ans = 0
for elm in itertools.product(li,repeat=n):
    for i in range(m):
        mm = 0
        for j in range(1,s[i][0]+1):
            if elm[s[i][j]-1]==1:
                mm += 1
        if mm%2!=p[i]:
            break
    else:
        ans += 1
        #print(elm)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
k=[0]*m
s=[[]for _ in range(m)]
for i in range(m):
  k[i], *s[i] = map(int, input().split())
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
  res=0
  for a in range(m):
    tmp=p[a]^1
    for j in s[a]:
      if (i >> (j-1)) & 1:
        tmp^=1
    res+=tmp
  if res==m:
    ans+=1
print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
l_list = []
for _ in range(M):
    data = list(map(int, input().split()))[1:]
    l_list.append(sum(2**(x-1) for x in data))

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

# ビット全探索
count = 0
for sw in range(2**N):
    for l, p in zip(l_list, p_list):
        A = l & sw
        A = (0x55555555 & A) + ((0xAAAAAAAA & A)>>1)
        A = (0x33333333 & A) + ((0xCCCCCCCC & A)>>2)
        A = (0x0f0f0f0f & A) + ((0xf0f0f0f0 & A)>>4)
        A = (0x00ff00ff & A) + ((0xff00ff00 & A)>>8)
        A = (0x0000ffff & A) + ((0xffff0000 & A)>>16)
        if A % 2 != p:
            break
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
def calculate(n,m,arr,p):
    total = 0
    for i in range(2**n):
        #某一种情况

        check = [False for i in range(m)]
        for indexOfBlub in range(len(arr)):
            # 第几个灯泡
            onNumOfTheBlub = 0
            for indexOfSwitch in range(len(arr[indexOfBlub])):
                if i >> (arr[indexOfBlub][indexOfSwitch] - 1) & 1:
                    onNumOfTheBlub += 1

            # 该灯泡所有的switch都循环结束以后，统计on的数量是否和给定的一样

            if onNumOfTheBlub % 2 == p[indexOfBlub]:
                check[indexOfBlub] = True

        if all(check):
            total += 1

    return total

n = 5
m = 2

S = input()
S = S.split(" ")
n = int(S[0])
m = int(S[1])


inputArr = []


for i in range(m):
    S = input()
    inputArr.append([int(s) for s in S.split(" ")][1:])

S = input()
inputP = [int(s) for s in S.split(" ")]


res = calculate(n,m,inputArr,inputP)

print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
# 始点を0にするため1を引く
# kを除くために[1:]
connected_switches = [[int(i) - 1 for i in input().split()[1:]]
                      for _ in range(M)]
ps = list(map(int, input().split()))

# https://atcoder.jp/contests/abc128/submissions/9251177 がとてもわかりやすいので参考にする

ans = 0
# どのスイッチがONになっているかの全パターン
for bit in range(2 ** N):
    ok = True
    # 各電球について回す、これは電球個（M個）あるpsが全て条件を満たしているかを確認するため
    for i in range(M):
        # i番目の電球に繋がっている、状態onのスイッチ個数
        connected_on_num = 0
        for s in connected_switches[i]:
            """
            今確認しているパターン（bit）で
            i番目の電球に繋がっているスイッチsがonとなる場合
            例: Nが4、bitが3は
            0番目: ON
            1番目: ON
            2番目: OFF
            3番目: OFF
            を想定している
            このケースで、forで回しているs（i番目の電球に繋がっているスイッチ）が
            0番目もしくは1番目のとき、connected_numが加算され2となる
            """
            if bit & (1 << s):
                """
                1 を左にsだけシフトする（10進数では2 ** s を掛けることと同じ）
                1 << 0 は 2進数で0001、10進数で1
                1 << 1 は 2進数で0010、10進数で2
                1 << 2 は 2進数で0100、10進数で4...
                bitが3のとき（2進数で0010のとき）
                bit & (1 << s) は
                0011 & (1 << s) という演算が行われる
                これがTrueとなるのは
                sが0: (1 << s) → (1 << 0) → 0001
                sが1: (1 << s) → (1 << 1) → 0010
                のときだけ
                """
                connected_on_num += 1
        if connected_on_num % 2 != ps[i]:
            ok = False
            break
    # 今確認しているパターン（bit）で
    # すべての電球が点灯している場合（connected_on_num % 2 != ps[i] が全てFalseだった場合）
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def is_all_switches_on(on_case):
    for i, s in enumerate(S):
        on_switch_num = 0
        for si in s:
            if on_case[si] == '1':
                on_switch_num += 1

        if on_switch_num % 2 != switches[i]:
            return False
    return True

if __name__ == '__main__':
    N, M = map(int, input().split())
    S = []
    for _ in range(M):
        k, *s = map(int, input().split())
        S.append(s)

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

    ans = 0
    for i in range(2 ** N):

        on_case = '0' + bin(i)[2:].zfill(N)
        if is_all_switches_on(on_case):
            ans += 1
    print(ans)

Submission status: Accepted

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

for j in range(2 ** N):
  ss = format(s, "010b")[10 - N:]
  m = 0
  for k in range(M):
    if sum([int(ss[i-1]) for i in Lumps[k]]) % 2 == p[k]:
      m += 1
    else:
      break
  if m == M:
    ans += 1
  s += 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(1 << N):
    flg = True
    for j in range(M):
        cnt = 0
        for s in S[j]:
            if i & (1<<(s-1)):
                cnt += 1
        if cnt % 2 != P[j]:
            flg = False
            break

    if flg:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin


def dfs(s, p, P, i):
    # 再帰
    # スイッチを順に見ていく
    if len(s) == i:
        return 1 if P == p else 0
    # 場合の数
    # そのスイッチを使用しなかった場合 + 使用した場合
    return dfs(s, p, P, i + 1) + dfs(s, p, P ^ s[i], i + 1)


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    sn = [[int(j) for j in i.split()[1:]] for i in lines[1:-1]]
    pn = (int(i) for i in lines[-1].split())
    # s[スイッチ]
    # 二進法で表した数における各桁はそのスイッチを使用している電球
    s = [0] * N
    for i in range(M):
        for j in sn[i]:
            s[j - 1] |= (1 << i)
    # p
    # 二進法で表した数における各桁は電球
    # スイッチONの数 MOD 2 におけるゼロイチを二進法で表す
    # 一致する場合に 全ての電球が点灯
    p = 0
    for i, j in enumerate(pn):
        p |= (1 << i) if j == 1 else 0
    print(dfs(s, p, 0, 0))


main()

Submission status: Accepted

Solution code:
def examA():
    A, P = LI()
    ans = (A*3+P)//2
    print(ans)
    return

def examB():
    N = I()
    SP = [[]for _ in range(N)]
    for i in range(N):
        SP[i] = LSI()
        SP[i][1] = int(SP[i][1])
        SP[i].append(i)
#    print(SP)
    SP = sorted(SP,key = lambda x:x[1], reverse = True)
    SP = sorted(SP,key = lambda x:x[0])
#    print(SP)
    for v in SP:
        print(v[2]+1)
    return

def examC():
    N, M = LI()
    S = [LI() for _ in range(M)]
    P = LI()
    ans = 0
    loop = 2**N
    for i in range(loop):
        flag = True
        d = defaultdict(bool)
        for j in range(N):
            if i&(1<<j)==(1<<j):
                d[j+1] = True
        for l,j in enumerate(S):
            cur = 0
            for k in range(1,j[0]+1):
                if d[j[k]]:
                    cur +=1
            if cur%2!=P[l]:
#                print(cur,l,i)
                flag = False
                break
        if flag:
            ans +=1
    print(ans)

    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

Submission status: Accepted

Solution code:
from itertools import product
n,m=map(int,input().split())#nはスイッチの数,mは電球の数
KS=[list(map(int,input().split())) for _ in range(m)]
P=list(map(int,input().split()))#m個の電球
kumiawase = list(product([0,1], repeat=n))#2^n通りのスイッチ on/off
cnt=0
flag=0
for i in range(2**n):
    flag=0#flagの初期化←これを忘れていた
    junban=kumiawase[i]#on/offパターン
    for j in range(m):#j+1個目の電球(j=[0,m-1])
        joutai=0      #初期化
        for k in range(KS[j][0]):
            joutai+=junban[KS[j][k+1]-1]#KSに入っている電球番号でjunbanでもonだったらjoutaiに+1
        if joutai%2==P[j]:#joutaiは電球onの数になっているはずなので2で割ってあまりをば
            flag+=0#すべてOKならカウントしたいのでこちらはflag+=0
        else:#逆に1回でもアウトならflag=1
            flag=1
    if flag==0:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
b = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
c = 0
for i in range(1 << n):
    a = [0]*n
    for j in range(n):
        if ((i >> j) & 1) == 1:
            a[j] = 1
    for k in range(m):
        if sum(a[l-1] for l in b[k][1:])%2 == p[k]:
            continue
        else:
            break
    else:
        c += 1
print(c)

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

answer = 0
for i in range(2 ** N):
  cnt = 0
  for j in range(M):
    tmp = 0
    for s in S[j]:
      if (i >> (s - 1)) & 1:
        tmp = 1 - tmp
    if tmp % 2 == P[j]:
      cnt += 1
  if cnt == M:
    answer += 1
    
print(answer)

Submission status: Accepted

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

ans = 0

# bit全探索
for i in range(2 ** N):
    switch_list = [0] * N
    flag = True     # 一つでも電球とスイッチの条件を満たさないならFalseにする
    for j in range(N):
        if i & (1 << j):    # 0 or 1 を調べるためのループ
            switch_list[j] = 1
    for k in range(M):  # 電球kについて
        on_swtich = 0
        for s in range(ks[k][0]):   # 繋がっているks[k][0]個のスイッチの状態を調べる
            if switch_list[ks[k][s+1] - 1] == 1:
                on_swtich += 1
        if on_swtich % 2 == p[k]:
            pass
        else:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

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 = [int(i) for i in input().split()]
ans = 0
for bit in range(1 << N):
  ok = True
  for i in range(M):
    cnt = 0
    for v in S[i]:
      if bit & (1<<(v-1)):
        cnt += 1
    if cnt%2!=P[i]:
      ok = False
  if ok:
    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):
  switch = [0]*n
  j = 0
  while j < n:
    if (i>>j) & 1:
      switch[j] = 1
    j += 1
  light = [0]*m
  for l in range(m):
    for x in range(ks[l][0]):
      if switch[ks[l][x+1]-1] == 1:
        light[l] += 1
  on = 0
  for l in range(m):
    if light[l]%2 != p[l]:
      continue
    on += 1
  if on == m:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

def check(bits, M, k, s, p):
    for x in range(M):
        dec = 0
        for K in range(k[x]):
            if bits >> (s[x][K] - 1) & 1:
                dec += 1
            else:
                pass

        if dec % 2 == p[x]:
            pass
        else:
            return 0

    return 1


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

    k = [0] * M
    s = [0] * M
    for i in range(M):
        k[i], *s[i] = map(int, input().split())

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


    ans = 0
    for bits in range(2 ** N):
        ans += check(bits, M, k, s, p)

    print(ans)


if __name__ == '__main__':
    main()