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:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    import copy


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

    all_list = []
    for i in range(n):
        i = str(i)
        for j in copy.deepcopy(all_list):
            all_list.append(j+i)
        all_list.append(i)
    all_list.append('')

    connects = [None]*m

    for i in range(m):
        connects[i] = list(input().split())[1:]

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

    ans = 0

    for pattern in all_list:
        for connect, leave in zip(connects, leaves):
            count = 0
            for num in connect:
                if str(int(num)-1) in pattern:
                    count += 1
            if count%2 != leave:
                break
        else:
            ans += 1

    print(ans)

Submission status: Accepted

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

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

def inc(i):
    if i == N:
        return False
    F[i] += 1
    if F[i] == 2:
        F[i] = 0
        return inc(i + 1)
    return True

def check(i):
    f_cnt = 0
    for j in S[i]:
        f_cnt += F[j-1]
    if f_cnt % 2 == P[i]:
        return True
    return False

cnt = 0
while True:
    flag = True
    for i in range(M):
        if not check(i):
            flag = False
            break
    if flag:
        cnt += 1
    if not inc(0):
        break

print(cnt)

Submission status: Accepted

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

mi = lambda: map(int, input().split())
li = lambda: list(map(int, input().split()))

N, M = mi()
S = [None] * N
B = [li() for _ in range(M)]
P = li()

count = 2**N
for s in itertools.product((0,1), repeat=N):
  for i in range(M):
    if sum([s[si-1] for si in B[i][1:]]) % 2 != P[i]:
      count -= 1
      break

print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000)

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

def rec(k, lst):
    if k == N:
        b = [0] * M
        for i in range(N):
            if lst[i] == 0:
                continue
            for j in range(M):
                if i + 1 in sw[j][1:]:
                    b[j] += 1
        # print("b, lst :", b, lst)
        return M == sum([b[i] % 2 == p[i] for i in range(M)])
    return rec(k + 1, lst + [0]) + rec(k + 1, lst + [1])

a = rec(1, [0])
b = rec(1, [1])
print(a + b)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    switch = [int(bin(i+2**n)[j+3]) for j in range(n)]
    condition = []
    for k in range(m):
        num = 0
        for l in range(ks[k][0]):
            if switch[ks[k][l+1]-1]:
                num += 1
        if num % 2 == p[k]:
            condition.append(True)
        else:
            condition.append(False)
    flag = 1
    for x in range(m):
        flag *= condition[x]
    if flag == True:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsm = lambda: map(str, sys.stdin.readline().split())

n, m = nm()
lis = [[] for _ in range(m)]
k = [0 for _ in range(m)]
for i in range(m):
    tmp = nl()
    k[i] = tmp[0]
    lis[i] = tmp[1:]
p = nl()
ans = 0
for i in range(2 ** n):
    bit = bin(i)[2:].zfill(n)
    ccnt = 0
    for j in range(m):
        cnt = 0
        for ll in lis[j]:
            if bit[ll - 1] == '1':
                cnt += 1
        if cnt % 2 == p[j]:
            ccnt += 1
    if ccnt == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
N,M=[int(i) for i in input().split(" ")]
k_dict={}
for i in range(M):
    _in=[int(j)-1 for j in input().split(" ")]
    k=_in[0]
    s=_in[1::]
    k_dict[i]=s



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

def _switch(pattern):
    lamps=np.zeros(M)
    for i,pat in enumerate(pattern):
        if pat==0:
            continue
        for key in k_dict:
            if i in k_dict[key]:
                lamps[key]+=1



    return np.sum(lamps%2 == p)==M


retval=0
for i in itertools.product([0,1], repeat=N):
    retval+=_switch(i)
print(retval)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def bin_count(x, N):
    count = 0
    for i in range(N):
        mask = 0x01 << i
        if (x & mask) != 0:
            count += 1
    return count


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    mask_list = []
    for i in range(M):
        input_raw = read_func().strip().split()
        [K] = [int(input_raw[0])]
        mask = 0
        for j in range(K):
            mask += 0x01 << (int(input_raw[j + 1]) - 1)
        mask_list.append(mask)


    input_raw = read_func().strip().split()
    P_list = [int(input_raw[i]) for i in range(M)]

    ans = 0
    for i in range((0x01 << N)):
        is_ok = True
        for j in range(len(mask_list)):
            mask = mask_list[j]
            if (P_list[j] != (bin_count(mask & i, N)%2)):
                is_ok = False
                break
        if is_ok == True:
            ans += 1
    print ans




if __name__ == '__main__':
    main()

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()))
check_list = []
for i in range(2 ** n):
    a = bin(i)[2::]
    while len(a) < n:
        a = "0" + a
    #print(len(a))
    check_list.append(a)
#print(check_list)

num = 0
ans = 0
for i in check_list:
    num = 0
    key = 1
    for j in ks:
        cnt = 0
        #print(j, i)
        for k in range(1, len(j)):
            #print(i, j, k)
            #i[j[k] - 1]
            if i[j[k] - 1] == "1":
                #print(i, j, cnt, j[k], i[j[k] - 1], p[num], 321321321)
                cnt += 1
        if cnt % 2 != p[num]:
            #print(i, j, cnt, j[k], i[j[k] - 1], p[num])
            key = 0
            break
        num += 1
    if key:
        ans += 1
print(ans)

Submission status: Accepted

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

c = 0
q = 0
for i in range(2**n):
    t = format(i,"010b")
    s = t[10-n:]
    r = 0
    for j in range(m):
        for u in range(k[j][0]):
            q += int(s[k[j][u+1]-1])
        if q % 2 == p[j]:
            q = 0
            continue
        else:
            q = 0
            r = 1
            break
    if r == 0:
        c += 1

print(c)

Submission status: Accepted

Solution code:
from itertools import permutations

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

ans = [0]
def dfs(l, depth):
    if depth== 0:
        for i in range(m):
            cnt = 0
            for j in ss[i]:
                if l[j-1]:
                    cnt += 1
            if cnt%2 != p[i]:
                return
        ans[0] += 1
        return
    q = l[::]
    q[depth-1] = 1
    dfs(l[::], depth-1)
    dfs(q, depth-1)
dfs([0]*n, n)
print(ans[0])

Submission status: Accepted

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

KS = []
for _ in range(M):
    ks = list(map(int, input().split()))
    KS.append(tuple([ks[0], set(ks[1:])]))

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

cnt = 0
for n in range(2**N):
    on_switchs = set()
    n_tmp = n
    for i in range(0, N):
        if n_tmp == 0:
            break
        else:
            if n_tmp % 2 == 1:
                on_switchs.add(N-i)
            n_tmp //= 2
    
    for m in range(M):
        if (len(on_switchs & KS[m][1]) % 2) != P[m]:
            break
    else:
        cnt += 1
            
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = [0] * M
for i in range(M):
    _, *s, = map(int, input().split())
    for v in s:
        S[i] = S[i] | (1 << (v - 1))

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

ans = 0
for p in range(2**N):
    ok = True
    for i in range(M):
        b = format(p & S[i], 'b')
        if b.count('1') % 2 != P[i]:
            ok = False
            break
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    switch = bin(i)[2:].zfill(N)
    ok = 1
    for j in range(M):
        sum_s = 0
        for k in range(cond[j][0]):
            if switch[cond[j][k+1] - 1] == '1':
                sum_s += 1
        if sum_s % 2 != p[j]:
            ok = 0
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(2**N):
    on_off = list(map(int,list(bin(i)[2:].zfill(N))))
    for j in range(M):
        on = 0
        for index in sw_list[j]:
            on += on_off[index-1]
        if on%2 != zero_or_one[j]:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Accepted

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

switch = []
for i in range(0, m):
    s = map(int, raw_input().split(" "))
    switch.append(s[1:])

power = map(int, raw_input().split(" "))

ans = 0
for state_int in range(0, 2 ** n):
    format_str = "{:0" + str(n) + "b}"
    state_bin = format_str.format(state_int)
    # print(state_bin)

    state = [0 for j in range(0, len(state_bin))]
    for i in range(0, len(state)):
        if state_bin[i] == "1":
            state[i] = True
        else:
            state[i] = False

    # print(state)
    on = True
    for s in range(0, m):
        ts = switch[s]
        count = 0

        for j in range(0, len(ts)):
            if state[ts[j] - 1]:
                count += 1

        if power[s] != count % 2:
            on = False
            break

    if on:
        # print(state_bin)
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = [sum(list(map(lambda x: 2**(int(x) - 1), input().split()[1:]))) for _ in range(m)]
p = list(map(int, input().split()))

ans = 0
for i in range(2**n):
    cnt = 0
    for j in range(m):
        if sum([((i & s[j]) >> k) % 2 for k in range(n)]) % 2 == p[j]:
            cnt += 1
    if cnt == m:
        ans += 1
print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
sw = [[int(_)-1 for _ in input().split()] for i in range(M)]
p = [int(_) for _ in input().split()]

def rec(n, onoff, lmp):
    if n < N:
        onoff[n] = True
        s = rec(n+1, onoff, lmp)
        onoff[n] = False
        s += rec(n+1, onoff, lmp)
        return s
    else:
        sm = 0
        for i in range(M):
            r = 0
            for j in sw[i][1:]:
                if onoff[j]:
                    r+=1
            if r % 2 == lmp[i]:
                sm += 1
        if sm == M:
            return 1
        else:
            return 0

onoff = [False for _ in range(N)]
print(rec(0, onoff, p))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=[]
for i in range(M):
  a=[int(i)-1 for i in input().split()]
  A.append(a[1:])
P=[int(i) for i in input().split()]
ans=0
for i in range(1<<N):
  F=True
  #print(i)
  for a in range(M):
    r=0
    for s in A[a]:
      r+=(((1<<s)&(i))>>s)
    #print(i,r)
    if P[a]!=r%2:
      F=False
      break
  if F:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
def make_cands(num, cands=[[0],[1]]):
    if len(cands[0]) == num:
        return cands
    else:
        newcands = []
        for cand in cands:
            newcands.append(cand+[0])
            newcands.append(cand+[1])
        return make_cands(num, newcands)

N,M = map(int, input().split())
switches = []
for _ in range(M):
    ks = list(map(int, input().split()))
    switches.append(ks[1:])
p = list(map(int, input().split()))
ans = 0
ress = make_cands(N)
for res in ress:
    tentou = 0
    for sw_i, sw in enumerate(switches):
        cnt = 0
        for num in sw:
            cnt += res[num-1]
        tentou += 1 if cnt % 2 == p[sw_i] else 0
    if tentou == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math

n,m = list(map(int, input().split()))
switchlist = []

for i in range(m):
    a = list(map(int, input().split()))
    switchlist.append([])
    for j in range(a[0]):
        switchlist[i].append(a[j+1])
switchval = list(map(int, input().split()))

ans = 0
#print(switchlist)
    
for i in range(2**n):
    zeroone=[]
    ii=i
    flag=1
    for j in range(n):
        zeroone.append(ii%2)
        ii=ii//2
    #print(zeroone)
    for j in range(m):
        count=0
        for k in range(len(switchlist[j])):
            #print(j,k)
            count+=zeroone[switchlist[j][k]-1]
        #print(count,switchval[j])
        if(count%2 != switchval[j]):
            flag=0
            
    if(flag==1):
        ans+=1
        
print(ans)

Submission status: Accepted

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

ans=0
#all_bits=[]
for i in range(1<<n): 
    #print(i)
    all_bits=[] 
    for j in range(n-1,-1,-1):
        all_bits.append((i>>j)&1) 
    check=True    
#&で取るときにbit計算
#左桁から値を見ていきに任意のBitsをリストへ
    for k in range(m):
        cnt=0
        for idx in range(l[k][0]):
            cnt+=all_bits[l[k][idx+1]-1]
        if cnt%2!=p[k]:
            check=False
            break
    if check==True:
        ans+=1
print(ans)

Submission status: Accepted

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

S = []
for i in range(M):
    tmp = list(map(lambda s: int(s)-1, input().split()))
    S.append(tmp[1:])

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



def f(fixed_l, res):
    if res == 0:
        ll = np.array(fixed_l)
        ss = 0
        for i in range(len(P)):
            p = P[i]
            if ll[S[i]].sum() % 2 == p:
                ss += 1
        return 1 if ss == M else 0
        

    a = f(fixed_l + [0], res-1)
    b = f(fixed_l + [1], res-1)
    return a + b

print(f([], N))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
switches = [list(map(int, input().split())) for i in range(m)]
P = list(map(int, input().split()))
ans = 0
for bit in range(2 ** n):
    for switch, p in zip(switches, P):
        count = 0
        for s in switch[1:]:
            if ((bit >> (s - 1)) & 1):
                count += 1
        if count % 2 == p:
            continue
        break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

def cnt(i, de):
    if i == n:
        for di, dk in enumerate(de):
            if dk % 2 != ps[di]:
                return 0
        return 1
    re = 0
    re += cnt(i+1, de)
    nde = copy.deepcopy(de)
    for di in swtode[i]:
        nde[di] += 1
    re += cnt(i+1, nde)
    return re

n, m = map(int, input().split())
swtode = [[] for _ in range(n)]
for di in range(m):
    k, *ss = map(int, input().split())
    for s in ss:
        swtode[s - 1] += [di]
ps = list(map(int, input().split()))
de=[0] * m
print(cnt(0,de))

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()))
ss = [[0 for _ in range(N)] for _ in range(M)]
for i, s in enumerate(ks):
    for j in range(len(s)-1):
        ss[i][s[j+1]-1] = 1
ans = 0
for i in range(2**N):
    tmp = 0
    for j in range(M):
        total = 0
        for k in range(N):
            if (i >> k) & 1 and ss[j][k] == 1:
                total += 1
        if total % 2 == p[j]:
            tmp += 1
    if tmp == M:
        ans += 1
print(ans)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,M=MAP()
lights=[[False]*N for i in range(M)]
for i in range(M):
    K=LIST()
    for j in range(1, K[0]+1):
        lights[i][K[j]-1]=True
P=LIST()

ans=0
for i in range(1<<N):
    cnts=[0]*M
    for j in range(N):
        for k in range(M):
            if i>>j&1:
                if lights[k][j]:
                    cnts[k]+=1
    for j in range(M):
        if cnts[j]%2!=P[j]:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
K = []
S = []
for i in range(M):
  inp = list(map(int, input().split()))
  K.append(inp[0])
  S.append(inp[1:])
P = list(map(int, input().split()))
res = []
def helper(res, tmp, N):
  if len(tmp)==N:
    res.append(tmp)
    return
  else:
    helper(res, tmp+[0], N)
    helper(res, tmp+[1], N)
helper(res,[],N)
cnt = 0
for item in res:
  flag = True
  for m in range(M):
    a = 0
    for s in S[m]:
      a += item[s-1]
    if (a % 2 != P[m]):
      flag = False
      break
  if flag:
    cnt += 1
print (cnt)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
index=0
switchL=[]
while index < m:
    listSw = list(map(int, input().split()))
    switchL.append(listSw)
    index+=1
listP = list(map(int, input().split()))

counter=0
for combi in itertools.product([0, 1], repeat=n):
    listR = list(combi)
    index=0
    while index < len(switchL):
        sumA=0
        index2=1
        while index2 < len(switchL[index]):
            target = switchL[index][index2]-1
            sumA+=listR[target]
            index2+=1
        if sumA%2 == listP[index]:
            index+=1
        else:
            break
    if index == len(switchL):
        counter+=1
print(counter)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
switch = [set() for _ in range(m)]
for i in range(m):
    a = list(map(int, input().split()))
    for j in range(1, len(a)):
        switch[i].add(a[j])
p = list(map(int, input().split()))
def check(i):
    bright = set()
    for j in range(n):
        if i % 2:
            bright.add(j + 1)
        i //= 2
    for j in range(m):
        if len(switch[j] & bright) % 2 != p[j]:
            return False
    return True
ans = 0
for i in range(1 << n):
    ans += int(check(i))
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
l=[]
for i in range(m):
    a,*b=list(map(int,input().split()))
    l.append(b)
p=list(map(int,input().split()))
cnt=0
for x in itertools.product([0,1], repeat=n):
    onl=[0]*m
    for i in range(n):
        for j in range(m):
            if x[i]==1 and i+1 in l[j]:onl[j]+=1
    for i in range(m):
        if p[i]!=onl[i]%2:
            break
    else:cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
s = [0] * m
for i in range(m):
    z = inl()
    s[i] = z[1:]
p = inl()

sum = 0
for i in range(2**n):
    b = []
    for j in range(n):
        b.append((i>>j)%2)  # i to bits
    ok = True
    for j in range(m): # for each bulb
        x = 0
        for k in s[j]:  # switches for bulb J
            x += b[k-1]
        if x%2 != p[j]:
            ok = False
            break
    if ok:
        sum += 1

print(sum)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict
import itertools
import numpy as np

n, m = LI()
ks = []
ss = []
for i in range(m):
    k, *s = LI()
    ks.append(k)
    ss.append(s)
ps = LI()

ans = 0
for comb in itertools.product((0,1), repeat=n):
    for j in range(m):
        o_e = 0 
        for i in ss[j]:
            o_e += comb[i-1]
        if o_e % 2 == ps[j]:
            continue
        else:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
S = []
K = []
for i in range(M):
    tmp = list(map(int,input().split()))
    k= tmp[0]
    S.append([tmp[i] for i in range(1, k+1)])
P = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    s = [0]*N # スイッチが立っているか
    for j in range(N):
        if (i >> j) % 2 == 1:
            s[j] = 1
    LIGHT = [False]*M
    for k in range(M): # 電球ｋが光っているか
        count = 0
        for c in S[k]:
            c -= 1
            if s[c] == 1:
                count += 1
        if count % 2 == P[k]:
            LIGHT[k] = True
    if all(LIGHT):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m = [int(i) for i in input().split()]
sss = [[int(i) for i in input().split()][1:] for _ in range(m)]
ps = [int(i) for i in input().split()]

ans = 0
for pro in itertools.product((0, 1), repeat=n):
    for ss, p in zip(sss, ps):
        pp = sum(pro[s-1] for s in ss) % 2
        if pp != p:
            break
    else:
        ans += 1
        # print(pro)

print(ans)

Submission status: Accepted

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

s = {}

for i in range(1, m+1):
    k, *v = map(int, input().split())
    s[i] = list(v)
p = [0] + list(map(int, input().split()))
ans = 0
for i in range(2**n):
    a = p[:]
    for j in range(n):
        if i & (1 << j) > 0:
            for k in range(1, m+1):
                if j+1 in s[k]:
                    a[k] ^= 1

    if sum(a) == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = [[] for _ in range(N)]
for i in range(M):
    ss = list(map(int, input().split()))[1:]
    for s in ss:
        S[s - 1].append(i)
P = [int(x) for x in input().split()]
ans = 0
for bit in range(1 << N):
    den = [0] * M
    for i in range(N):
        if bit >> i & 1:
            for s in S[i]:
                den[s] += 1
    if all(d % 2 == p for d, p in zip(den, P)):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
switches = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
ans = 0
onofflist = [format(i,'0'+str(N)+'b') for i in range(2**N)]
for onoff in onofflist:
    flag=True
    for i,swittch in enumerate(switches):
        cur = 0
        for s in swittch[1:]:
            cur += int(onoff[s-1])
        if cur % 2 != p[i]:
            flag=False
    if flag:
        ans+=1
print(ans)

Submission status: Accepted

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

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

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

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

def on(s, bit):
    return (bit >> (s-1)) & 1

count = 0
for bit in range(2 ** N):
    flag = False
    for k in range(M):
        state = 0
        for s in switches[k]:
            state += on(s, bit)
        if state % 2 != p[k]:
            flag = True
            break
    if flag:
        continue
    count += 1
print(count)

Submission status: Accepted

Solution code:
import sys

fin = sys.stdin.readline

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

ks = [tuple(map(int, fin().split())) for i in range(M)]
p = tuple(map(int, fin().split()))

count = 0

for i in range(2 ** N):
    switch = format(i, "b").zfill(N)
    ok = 1
    for ks_, p_ in zip(ks, p):
        p__ = p_
        for s in ks_[1:]:
            p__ += int(switch[s - 1])
        if p__ % 2 == 1:
            ok = 0
            break
    if ok:
        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()))

s = []
for i in ks:
    t = 0
    for j in range(1, i[0]+1):
        t += 2**(i[j]-1)
    s.append(t)

pt = 0
for i in range(2**n):
    l = True
    for j in range(m):
        o = bin(i & s[j]).count("1") % 2
        if o != p[j]:
            l = False
            break
    if l: pt += 1

print(pt)

Submission status: Accepted

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

S = [[0] * N for _ in range(M)]

for i in range(M):
    a = [int(i) for i in input().split()]
    for j in a[1:]:
        S[i][j-1] = 1

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

ans = 0

for i in range(2**N):
    K = [0] * M
    for j in range(N):
        if i >> j & 1:
            for k in range(M):
                if S[k][j] == 1:
                    K[k] += 1
    c = 0
    for j in range(M):
        if K[j]%2 == P[j]:
            c += 1
    if c == M:
        ans += 1

print(ans)

Submission status: Accepted

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

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

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

ans = 0

#print(p)
#print(s)

for i in range(2**N):
    #print("i: {}".format(i))
    
    found = True
    for m in range(M):
        #print("m: {}".format(m))
        # 各スイッチを見てゆく
        count = 0
        for k in range(N):
            #print("k: {}".format(k))
            if k+1 not in s[m]:
                continue

            state = (i >> k) & 1
            #print("state: {}".format(state))
            if state == 1:
                count += 1
                #print("count: {}".format(count))

        if p[m] != (count % 2):
            found = False
            break

    if found:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ks_list=[]
for i in range(m):
    sub_list=list(map(int,input().split()))
    sub_list=sub_list[1:]
    ks_list.append(sub_list)
p_list=list(map(int,input().split()))
ans=0
for i in range(2**n):
    s_list=[]
    for j in range(n):
        s_list.append(i&1)
        i=i>>1
    count=1
    for j in range(m):
        Sum=0
        for x in ks_list[j]:
            Sum=Sum+s_list[x-1]
        if Sum%2==p_list[j]:
            count=count
        else:
            count=0
    ans=ans+count
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()


n,m = na()
a = []

for i in range(m):
    b = na()
    a.append(b)
    
p = na()

ans = 0

for i in range(1 << n):
    d = True
    for j in range(len(a)):
        c = 0
        for k in range(1,a[j][0]+1):
            if i >> (a[j][k]-1) & 1:
                c += 1
        if c%2 != p[j]:
            d = False
    if d:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
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()))
ans=0

def check(D):
    ret=True
    for i in range(M):
        l=L[i][1:]
        tmp=0
        for l_ in l:
            tmp+=(D>>(l_-1))&1
        if tmp%2!=P[i]:
            ret=False
            break

    return ret


for d in range(2**N):
    if check(d):
        ans+=1


print(ans)

Submission status: Accepted

Solution code:
n, m=map(int, input().split())
s=[]
for i in range(m):
    inp=input().split()
    k=int(inp[0])
    tmp=[]
    for i in range(k):
        tmp.append(int(inp[i+1]))
    s.append(tmp)
p=list(map(int, input().split()))
result=0
for i in range(2**n):
    switch=[]
    flag=1
    for j in range(n):
        if (i>>j)&1:
            switch.append(1)
        else:
            switch.append(0)
    for j in range(m):
        sum=0
        for k in range(len(s[j])):
            sum=sum+switch[s[j][k]-1]
        if sum%2!=p[j]:
            flag=0
    if flag:
        result=result+1
print(result)