Problem:


Score : 300 points

Problem Statement

We have N switches with "on" and "off" state, and M bulbs. The switches are numbered 1 to N, and the bulbs are numbered 1 to M.

Bulb i is connected to k_i switches: Switch s_{i1}, s_{i2}, ..., and s_{ik_i}. It is lighted when the number of switches that are "on" among these switches is congruent to p_i modulo 2.

How many combinations of "on" and "off" states of the switches light all the bulbs?

Constraints

1 \leq N, M \leq 10

1 \leq k_i \leq N

1 \leq s_{ij} \leq N

s_{ia} \neq s_{ib} (a \neq b)

p_i is 0 or 1.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
k_1 s_{11} s_{12} ... s_{1k_1}
:
k_M s_{M1} s_{M2} ... s_{Mk_M}
p_1 p_2 ... p_M

Output

Print the number of combinations of "on" and "off" states of the switches that light all the bulbs.

Sample Input 1

2 2
2 1 2
1 2
0 1

Sample Output 1

1

Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.

Bulb 2 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

There are four possible combinations of states of (Switch 1, Switch 2): (on, on), (on, off), (off, on) and (off, off). Among them, only (on, on) lights all the bulbs, so we should print 1.

Sample Input 2

2 3
2 1 2
1 1
1 2
0 0 1

Sample Output 2

0

Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.

Bulb 2 is lighted when there is an even number of switches that are "on" among the following: Switch 1.

Bulb 3 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

Switch 1 has to be "off" to light Bulb 2 and Switch 2 has to be "on" to light Bulb 3, but then Bulb 1 will not be lighted. Thus, there are no combinations of states of the switches that light all the bulbs, so we should print 0.

Sample Input 3

5 2
3 1 2 5
2 2 3
1 0

Sample Output 3

8



Sample input:
2 2
2 1 2
1 2
0 1


Sample output:
1

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n, m = na()
ks = nan(m)
p = na()

ans = 0
for i in range(2 ** n):
    ok = True
    for j in range(m):
        k, s = ks[j][0], ks[j][1:]
        sum_on = 0
        for a in range(k):
            if (i >> (s[a] - 1)) & 1:
                sum_on += 1
        if sum_on % 2 != p[j]:
            ok = False
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n, m = na()
ks = nan(m)
p = na()

ans = 0
for i in range(2 ** n):
    on = dict()
    for j in range(n):
        if (i >> j) & 1:
            on[j + 1] = True
    l = 0
    for j in range(m):
        k, s = ks[j][0], ks[j][1:]
        sum_on = 0
        for a in range(k):
            if on.get(s[a], False):
                sum_on += 1
        if sum_on % 2 == p[j]:
            l += 1
    if l == m:
        ans += 1

print(ans)

Submission status: Accepted

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


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


for i in range(M):
    tmp = list(map(int, input().split()))
    for j in tmp[1:]:
        K[i][j-1] = 1
p = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    tmp = [0]*M
    for j in range(N):
        if (i >> j) % 2 == 1:
            for k in range(M):
                tmp[k] += K[k][j]
    for j in range(M):
        if tmp[j] % 2 != p[j]:
            break
        if j == M-1:
            ans += 1


print(ans)

Submission status: Accepted

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

l = [[0] * n for _ in range( m )]
for i in range( m ):
  k = list( map( int, input().split() ))
  for j in range( 1, k[0] + 1 ):
    l[i][ k[ j ] - 1] = 1
p = list( map( int, input().split() ) )

ret = 0
for i in range( 2 ** n ):
  b = [ int(k) for k in str( format(i,'b').zfill(n))]
  cnt = 0
  for j in range( m ): 
    a = 0
    for k in range( n ):
      a += b[ k ] * l[ j ][ k ]
    if a % 2 == p[ j ]:
      cnt += 1
  if cnt == m:
    ret += 1
print( ret )

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product

def main():
    n, m = [int(i) for i in input().split()]
    sw = np.zeros((m, n), int)
    for i in range(m):
        for s in input().split()[1:]:
            sw[i][int(s)-1] = 1

    p = np.array([int(i) for i in input().split()])
    res = 0
    for t in product((0, 1), repeat=n):
        stat = np.array(t)
        if np.array_equal(p, np.dot(sw, stat) % 2):
            res += 1
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

l = []
ans = 0
for i in range(2**n):
    l = []
    for j in range(n):
            if i & (1<<j):
                l.append(j+1)

    flag = True
    for j in range(m):
        kosu = 0
        for k in l:
            if k in s[j][1:]:
                kosu += 1
        if kosu % 2 != p[j]:
            flag = False
            break

    if flag:
        ans += 1


print(ans)

Submission status: Accepted

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


for i in range(2**n):
    ok = True
    for j in range(m):
        on_cnt = 0
        for k in range(q[j]):
            for l in range(n):
                if i >> l & 1:
                    if l == s[j][k] - 1:
                        on_cnt += 1
        if on_cnt % 2 != p[j]:
            ok = False
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

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

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 bit in range(1 << N):
    for i in range(M):
        cnt = 0
        for s in S[i]:
            if bit >> (s-1) & 1:
                cnt += 1
        if cnt % 2 != p[i]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = [0] * m
for i in range(m):
    s[i] = list(map(int, input().split()))[1:]
p = list(map(int, input().split()))
ans = 0
for bit in range(2 << (n-1)):
    l = [0] * n
    for i in range(n):
        if bit >> i & 1:
            l[i] += 1
    for i in range(m):
        cnt = 0
        flag = True
        for j in s[i]:
            if l[j-1] == 1:
                cnt += 1
        if cnt % 2 != p[i]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

def dfs(cnt):
    global ans
    if cnt == N:
        onF = True
        for i in range(M):
            tmp = 0
            for j in range(ks[i][0]):
                if bit[ks[i][j + 1] - 1] == 1:
                    tmp += 1
            if tmp % 2 != p[i]:
                onF = False
                break
        if onF:
            ans += 1
        return
    for i in range(2):
        bit[cnt] = i
        dfs(cnt + 1)


N, M = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
bit = [0] * N
ans = 0
dfs(0)
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):
  q=[0]*n
  for j in range(n):
    if i>>j&1:
      q[j]=1
  for j in range(m):
    cnt=0
    for k in ks[j][1:]:
      if q[k-1]==1:
        cnt+=1
    if cnt%2!=p[j]%2:
      break
  else:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m = inpl()
s = [inpl() for i in range(m)]
p = inpl()
res = 0
for flag in itertools.product([0,1], repeat=n):
    on = set()
    for i,j in enumerate(flag):
        if j: on.add(i+1)
    ok = True
    for i,j in enumerate(s):
        cnt = 0
        for k,l in enumerate(j):
            if k == 0: continue
            if l in on: cnt += 1
        if cnt%2 != p[i]:
            ok = False
            break
    if ok: res += 1
print(res)

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    S = []
    for _ in range(M):
        k, *s = (int(i)-1 for i in input().split())
        S.append(set(s))
    P = [int(i) for i in input().split()]
    ans = 0
    for bit in range(1 << N):
        on = set()
        for i in range(N):
            if bit & (1 << i):
                on.add(i)
        if all(len(S[i] & on) % 2 == P[i] for i in range(M)):
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    s = []
    for i in range(m):
        a = LI()[1:]
        for j in range(len(a)):
            a[j] -= 1
        s.append(a)
    p = LI()
    ans = 0
    for b in range(1<<n):
        su = [0]*m
        for i in range(m):
            for j in s[i]:
                if b&(1<<j):
                    su[i] ^= 1
        if su == p:
            ans += 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N,M = map(int,input().split()) #N:スイッチ　＃M：電球
light=[]
for i in range(M):
    light.append(list(map(int,input().split())))



p = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    #print("num {}" .format(i), end="")
    sw = [0]*N
    for j in range(N):
        if ((i >>j) & True):
            sw[j]=1
    On_Light_nmb = 0
    for m in range(M): #電球ごとに判定
        sum = 0
        for k in range(light[m][0]):
            s_nmb = int(light[m][k+1])
            sum += sw[s_nmb-1]

        if sum%2 == p[m]: #電球mのOnスイッチの合計が
            #Ans.append(1)
            On_Light_nmb +=1


    #もしすべてのライトがついていたら
    if On_Light_nmb == m+1:
        ans +=1

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    clear = True
    for idx, l in enumerate(lamps):
        on = 0
        for j in range(N):
            if ((i>>j) &1):
                if j+1 in l:
                    on += 1
        if not on%2==Ps[idx]:
            clear = False
            break
    if clear:
        ans += 1
print(ans)

Submission status: Accepted

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


def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))

# mod=10**9+7
# rstrip().decode('utf-8')


def main():
	n,m=MI()
	ks=[LI() for _ in range(m)]
	s=[i[1:] for i in ks]
	p=LI()
	ans=0

	for i in range(1<<n):
		li=[0]*m
		for j in range(n):
			for k in range(m):
				if 1&i>>j:
					if j+1 in s[k]:
						li[k]=1-li[k]
		if p==li:
			ans+=1
	print(ans)










if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

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

    ans = 0
    # スイッチのパターン
    for i in range(2**N):
        # 電球
        flg = True
        for j in range(M):
            # 電球に繋がれたスイッチ
            c = 0
            for k in range(ks[j][0]):
                if (i>>(ks[j][k+1]-1))&1:
                    c += 1
            if c%2!=p[j]:
                flg = False
        if flg:
            ans += 1
    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
K=[]
for i in range(m):
    _,*a=map(int,input().split())
    K.append(a)
P=list(map(int,input().split()))

ans=0
for i in range(2**n):
    S=[]
    flag=0
    for j in range(n):
        S.append(i>>j)
    for j in range(m):
        lamp=K[j]
        cnt=0
        for k in lamp:
            cnt+=S[k-1]
        if cnt%2!=P[j]:
            flag=1
            break
    if flag==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
# 入力の受取
n, m = map(int, input().split())
k = [0] * (m+1)
s = [[] for _ in range(m+1)] 
for i in range(1, m+1):
    tmp = list(map(int, input().split()))
    k[i] = tmp[0]
    s[i] = tmp[1:]

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

# ビット全探索用のシーケンスを生成
seq = [0, 1]
import itertools
arr = itertools.product(seq, repeat=n)
#for v in arr:
#    print(v)

# ビット全パターンでスイッチの状態を判定
# 全て点灯の場合，ansに1を加算
ans = 0
for v in arr:
    v = [0] + list(v)
    flag = True
    # m個の電球をそれぞれ判定
    for light in range(1,m+1):
        t = s[light]
        count = 0
        for i in range(len(t)):
            count += v[t[i]]
        if count % 2 != p[light-1]:
            flag = False
    if flag:
        ans += 1


print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import combinations

def readlines(n):
    for _ in range(n):
        k, *s = map(int, input().split())
        yield s

def on(s, p, comb):
    return len([s_ for s_ in s if s_ in comb]) % 2 == p

def main():
    n, m = map(int, input().split())
    switches = list(range(1, n+1))
    S = list(readlines(m))
    P = list(map(int, input().split()))
    for i in range(n+1):
        for comb in combinations(switches, i):
            if all(on(s, p, set(comb)) for s, p in zip(S, P)):
                yield 1

print(sum(main()))

Submission status: Accepted

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

ans = 0
for i in range(2**N):#スイッチONの全探索
    judge = True
    for l in range(M): #電球点灯チェック
        cnt = 0
        for j in range(N):#スイッチのj番目について
            if (i >> j) & 1 and (j in Lamp[l]):
            #スイッチがONの時 and スイッチと電球がつながっているか
                cnt += 1
        if cnt % 2 != p[l]:#一個でも点灯しなければNG
            judge = False
            break
    if judge:#pの条件を全てクリアするスイッチの状態を追加
        ans += 1

print(ans)

Submission status: Accepted

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

mbit=[0]*M
allon=2**M-1

ret=0

for i,ks in enumerate(kslst):
    k=ks[0]
    for j in range(1,k+1):
        mbit[i]+=2**(ks[j]-1)

for i in range(2**N):
    cstate=0
    for j in range(M):
        cnt=0
        for k in range(N):
            if (i>>k)&1==1 and (mbit[j]>>k)&1==1:
                cnt+=1
        
        cstate+=2**j if cnt%2==p[j] else 0
    
    if cstate&allon==allon:
        ret+=1

print(ret)

Submission status: Accepted

Solution code:
from collections import deque

N, M = [int(x) for x in input().split()]
k = [None] * M
s = [None] * M
for i in range(M):
    lst = input().split()
    k[i] = int(lst[0])
    s[i] = [int(x) - 1 for x in lst[1:]]  # index調整
p = [int(x) for x in input().split()]

# BFS
que = deque([[]]) # 探索候補キュー
ans = 0
while len(que) > 0:
    sw = que.popleft()  # 各スイッチの状態
    if len(sw) >= N:
        all_on = True
        for i in range(M):  # 各電球がONしているか確認
            light = 0
            for j in s[i]:  # 各スイッチの値の和
                light = (light + sw[j]) % 2
            if light != p[i]:
                all_on = False
                break
        ans += int(all_on)
    else:
        que.append(sw + [0])
        que.append(sw + [1])

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
light = [list(map(int,input().split())) for _ in range(m)]
check = list(map(int,input().split()))
ans = 0

for i in range(2 ** n):
    swicth = [0] * n
    
    for j in range(n):
        if ((i >> j) & 1):
            swicth[n - 1 -j] = 1
            
    check_cnt = 0        
    for k in range(m):
        a = light[k][0]
        swicth_on_cnt = 0
        for b in range(a):
            swicth_number = light[k][1+b]
            if swicth[swicth_number - 1] == 1:
                swicth_on_cnt += 1
        if swicth_on_cnt%2 == check[k]:
            check_cnt += 1

    if check_cnt == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
lamp=[list(map(int,input().split())) for _ in range(M)]
restrict=list(map(int,input().split()))
l=[0]*N
cnt=0
flag=0
ans=0
for i in range(pow(2,N)):
    for j in range(N):
        l[j]=(i>>j)&1
    for j in range(M):
        for k in range(len(lamp[j])-1):
            cnt=cnt+l[lamp[j][k+1]-1]
        if (cnt%2)==restrict[j]:
            flag=flag+1
        cnt=0
    if flag==M:
        ans=ans+1
    flag=0
print(ans)

Submission status: Accepted

Solution code:
from itertools import  product

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

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

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

for z in product((0, 1), repeat=n):
    for i in range(m):    
        k=ks[i][0]
        on_count=0
        for j in range(1,k+1):
            if z[ks[i][j]-1]==1:
                on_count+=1
        if  on_count%2!=p[i]:
            break
    else:
        ans+=1
print(ans)   
#print(z)

Submission status: Accepted

Solution code:
#n = int(input())
#n,k = map(int,input().split())
#x = list(map(int,input().split()))


def calc_dis(A,B,li,N):
    dis = 0
    for i in range(N):
        dis += abs(A-li[i][0]) + abs(li[i][0]-li[i][1]) + abs(B-li[i][1])
    return dis

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

    ans = 0
    for i in range(1<<(N)):
        li = [0 for i in range(M)]
        for j in range(N):
            if (i>>j)&1: #スイッチがon
                for k in range(M):
                    if (j+1) in S[k]:
                        li[k] += 1
        # print(bin(i),li)
        for j in range(M):
            if li[j]%2!=P[j]:
                break
        else:
            # print(bin(i))
            ans += 1
        # print(i)

    print(ans)



    

main()

Submission status: Accepted

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

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

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

ans = 0
for mask in range(1<<N):
    swithes_status = [0] * M
    for i in range(N):
        if mask & (1<<i) >= 1:
            # push switch
            for j, light in enumerate(lights):
                if (i+1) in light:
                    swithes_status[j] += 1
    full_on = True
    for condition, status in zip(light_on_condition, swithes_status):
        if condition != status % 2:
            full_on = False
            break
    if full_on:
        ans += 1

print(ans)

Submission status: Accepted

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

#print(N, M, ks, p)

pos=[None]*N
pattern=0

def check(pos):
    #print(pos)
    count=0
    for i in range(M):
        temp=0
        for j in range(1, len(ks[i])):
            temp+=pos[ks[i][j]-1]
        if temp%2==p[i]:
            #print('OK')
            count+=1
    #print(count)
    if count==M:
        #print(pos)
        return 1
    else:
        return 0

def set(n):
    global pattern
    if n==N-1:
        for i in range(2):
            pos[n]=i
            pattern+=check(pos)
    else:
        for i in range(2):
            pos[n]=i
            set(n+1)
set(0)

print(pattern)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from itertools import product
def I(): return [int(iI) for iI in input().split()]
n,m=I() ; a=[]
for i in range(m):
    a.append(I()[1:])
p=I()
l=[list(p) for p in product([0,1], repeat=n)]
ans=0
for i in l:
    flag=0
    for j in range(len(a)):
        s=0
        for k in a[j]:
            if i[k-1]==1: s+=1
        if s%2!=p[j]%2:
            flag=1
            break
    if flag==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
def mySum(L, indexs):
    result = 0
    for i in indexs:
        if (L >> i & 1):
            result += 1
    return result


N, M = map(int, input().split())
S = []
for _ in range(M):
    S.append(list(map(lambda a: int(a)-1, input().split()))[1:])
P = list(map(int, input().split()))
count = 0
for bi in range(1 << (N)):
    for i, s in enumerate(S):
        if P[i] != (mySum(bi, s)) % 2:
            break
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import decimal
import heapq
import collections
import itertools
from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

s = getSomeInputListInt(m)
p = getInputListInt()

s_bit = []

for tmp_s in s:
    tmp_bit = 0
    for i in range(1, tmp_s[0] + 1, 1):
        aaa = 1 << (tmp_s[i] - 1)
        tmp_bit = aaa | tmp_bit
    s_bit.append(tmp_bit)

ans = 0
for i in range(int(pow(2, n))):
    flg = True
    for j in range(m):
        cnt = bin(s_bit[j] & i).count("1")
        if cnt % 2 != p[j]:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc128/tasks/abc128_c


def check_switch_on(S, btn, P):
    for i, s_row in enumerate(S):
        on_cnt = 0
        # print(s_row)
        for s in s_row:
            if btn[s-1]:
                on_cnt += 1
        if P[i] != on_cnt % 2:
            return False
    return True


if __name__ == "__main__":
    N, M = map(int, input().split())

    S = []
    for _ in range(M):
        l = list(map(int, input().split()))
        k = l[0]
        s_row = l[1:]
        S.append(s_row)

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

    cnt = 0
    for bit in range(1 << N):
        btn = [False] * N
        for i in range(N):
            if bit & (1 << i):
                btn[i] = True
        if check_switch_on(S, btn, P):
            # print(btn)
            cnt += 1

    print(cnt)

Submission status: Accepted

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

ans = 0
for bit in range(2 ** N):
    ons = set([i + 1 for i in range(N) if bit >> i & 1])
    flg = True
    for i in range(M):
        k, *s = X[i]
        p = P[i]
        flg &= len(set(s) & ons) % 2 == p
    ans += int(flg)
    
print(ans)

Submission status: Accepted

Solution code:
def main():
    from builtins import int, str, map, list, dict, float, print, len, sorted, max, min
    from itertools import accumulate, permutations, combinations
    from collections import deque, defaultdict, Counter
    from operator import itemgetter
    from bisect import bisect_left, bisect_right, bisect
    from heapq import heappop, heappush
    from fractions import gcd
    import sys, re, math, copy
    sys.setrecursionlimit(10 ** 6)

    input = sys.stdin.readline
    input_list = (lambda: input().rstrip().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    N, M = input_number_list()
    k = []
    s = []
    p = []
    for i in range(M):
        ls = input_number_list()
        k.append(ls[0])
        s.append(ls[1:])
    p = input_number_list()
    switch_max = 2 ** N
    ans = 0
    for i in range(switch_max):
        cnt_if = 0
        for j, switchs in enumerate(s):
            cnt = 0
            for sw in switchs:
                h = 1 << (sw - 1)
                if h & i:
                    cnt += 1
            if cnt % 2 == p[j]:
                cnt_if += 1
        if cnt_if == M:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
light = []
for i in range(m):
  light.append(list(map(int,input().split())))
p = list(map(int,input().split()))
# bit全探索 nで スイッチのパターンを全てためす
# 
ans = 0
for i in range(2**n):
  ng = 0
  for j in range(m):
    ans_j = 0
    for k in range(n):
      if i >> k & 1 and k+1 in light[j][1:]:#電球on かつk[i]の電球がついているなら+=1
        #print(light[j][1:],k)
        ans_j += 1
    #print(ans_j,i,p[j],ng)
    if ans_j % 2 != p[j]:
      ng = 1
  if ng == 0:
    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()))
 
cnt = 0
 
for i in range(2 ** N):  # スイッチの全部の組み合わせについて
    flag = True
    for j in range(M): # 全ての電球がonとなる条件となっているか確認, i>>k-1で数値iをbitに変換、1(ON)の立っている数を数える
        if not([(i >> k-1) & 1  for k in s[j]].count(1) % 2 == p[j]):
            flag = False
    if flag:
        cnt += 1
 
print(cnt)

Submission status: Accepted

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

ans = 0
for n in range(2**N):
  #print(f'n: {n}')
  alllight = True
  for pi, S in enumerate(Switch):
    mask = n
    swon = 0
    for i in range(N):
      if (mask >> i) & 1:
        if i+1 in S: swon += 1
    #print(f'  sw: {pi}, p:{P[pi]}, swon: {swon}')
    if swon % 2 != P[pi]:
      alllight = False
      break
  if alllight: 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()))

count = 0
for i in range(2 ** n):

    # switch state
    switches = [0] * n
    for j in range(n):
        if ((i >> j) & 1):
            switches[j] = 1
    
    # light state
    lights = [0] * m
    for k in range(m):
        on_num = sum(map(lambda x: switches[x-1], S[k]))
        if on_num % 2 == P[k]:
            lights[k] = 1
    
    # are all lights on?
    if all(light == 1 for light in lights):
        count += 1

print(count)

Submission status: Accepted

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

ans = 0
for bit in range(1 << N):
    on_counts = [0] * M
    for i in range(N):
        if bit & (1 << i):
            for m in range(M):
                if i in s[m]:
                    on_counts[m] += 1
    if [x % 2 for x in on_counts] == p:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ks = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
cnt = 0
for i in range(2**n):
  cnt_on = [0 for i in range(m)]
  for j in range(n):
    if (i >> j) & 1:
      for k in range(m):
        g = ks[k][1:]
        for a in g:
          if a == j+1:
            cnt_on[k] += 1
  for l in range(m):
    if cnt_on[l]%2 != p[l]:
      break
    if l == m-1:
      cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

N, M = map(int, input().split())
liS_all = []
denkyuM = [0 for i in range(M)]
cnt = 0

for j in range(1, M + 1):
    liS = list(map(int, input().split()))
    denkyulist = [0 for k in range(N)]
    for l in liS[1:]:
        denkyulist[l-1] = 1
    liS_all.append(denkyulist)

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

bit_list = list(product([0, 1], repeat = N))

for bit in bit_list:
    n = 0
    judge = True
    for denkyu in liS_all:
        ronriseki = np.logical_and(bit, denkyu)
        if sum(ronriseki) % 2 != liP[n]:
            judge = False
        n += 1
    if judge == True:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(int, input().split())
ks = []
for i in range(m):
    k, *arg = map(int, input().split())
    ks.append((k, arg))
p = list(map(int, input().split()))

res = 0
for pattern in product((0, 1), repeat=n):
    for i in range(m):
        cnt = 0
        k, s = ks[i]
        for j in range(k):
            cnt += pattern[s[j] - 1]
        if cnt % 2 != p[i]:
            break
    else:
        res += 1

print(res)