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
from itertools import product

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    bulbs = []
    for _ in range(M):
        b = tuple(map(int, input().split()))
        bulbs.append(b[1:])

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

    ans = 0
    for switch in product((0, 1), repeat=N):
        check = [0] * M
        for i, bulb in enumerate(bulbs):
            cnt = 0
            for b in bulb:
                cnt += switch[b-1]

            if cnt % 2 == P[i]:
                check[i] = True
            else:
                check[i] = False

        if all(check):
            ans += 1

    return ans



if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

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

res = 0
for i in range(2 ** n):
    flag = True
    bit_i = bin(i)[2:].zfill(n)
    for j in range(m):
        sum_s = 0
        for idx in s[j]:
            sum_s += int(bit_i[idx-1])
        if sum_s % 2 != p[j]:
            flag = False
            break
    if flag:
        res += 1

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

MOD = 2  # type: int
import itertools


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N, M = list(map(int,input().split()))

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

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

    swl = list(itertools.product([1,0],repeat=N))
    
    ok_cnt = 0
    for sw in swl:
        bOK = True
        for i,s in enumerate(S):
            on_cnt = 0
            for ss in s:
                if sw[ss-1]:
                    on_cnt += 1

            if (on_cnt % 2) != P[i]:
                bOK = False
                break
        if bOK:
            ok_cnt+=1

    print(ok_cnt)


    pass

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for k in range(M):
    b = list(map(int,input().split()))
    B.append(b[1:])
p = list(map(int,input().split()))

ans = 0
for k in range(2**N):
    a = []
    t = [0 for k in range(M)]
    for l in range(N):
        if (k>>l)&1:
            a.append(l)
    for s in a:
        for l in range(M):
            if s+1 in B[l]:
                t[l] += 1
    u = 0
    for l in range(M):
        if p[l] == t[l]%2:
            u += 1
    if u==M:
        ans+=1
print(ans)

Submission status: Accepted

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

ans = 0
for switchs in range(1<<n):
	switch_on = []
	for j in range(n):
		if (switchs>>j)&1 == 1:
			switch_on.append(j+1)
	for denkyu in range(m):
		tmp = 0
		for s_denkyu in s[denkyu]:
			if s_denkyu in switch_on:
				tmp += 1
		if tmp%2 != p[denkyu]: 
			break
	else:
		ans += 1

print(ans)

Submission status: Accepted

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

N, M  = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
P = [int(v) for v in input().split()]

ans = 0
for i in range(1 << N):
    s = []
    
    for j in range(N):
        if (i >> j) & 1:
            s.append(j)

    cc = 0
    for j in range(M):
        v = L[j][1:]
        
        c = 0
        for k in v:
            if k - 1 in s:
                c += 1
                
        if c % 2 == P[j]:
            cc += 1
            
    if cc == M:
        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()))
bit=[]
ans=0
for i in range(2**N):
    bit+=[list(bin(i)[2:].zfill(N))]
for b in bit:
    for i in range(M):
        on=0
        for j in range(ks[i][0]):
            if b[ks[i][j+1]-1]=="1":
                on+=1
        if on%2!=p[i]:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

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

on = []
for x in ks:
    o = 0
    for s in x[1:]:
        o += 2**(s-1)
    on.append(o)

res = 0
for x in range(2**n):
    flg = True
    for i,o in enumerate(on):
        if p[i] != bin(o&x).count("1") % 2:
            flg = False
            break

    if flg:
        res += 1
       
print(res)

Submission status: Accepted

Solution code:
def getlist():
	return list(map(int, input().split()))

N, M = getlist()

light = [[0 for i in range(N)] for j in range(M)]
for i in range(M):
	A = getlist()
	k = A[0]
	for j in range(k):
		light[i][A[1 + j] - 1] = 1

p = getlist()

ans = 0
for i in range(1 << N):
    output = []
    for j in range(N):
        if ((i >> j) & 1) == 1:
            output.append(0)
        else:
        	output.append(1)

    judge = "YES"
    for j in range(M):
    	c = 0
    	for k in range(N):
    		if output[k] == 1 and light[j][k] == 1:
    			c += 1
    	if c % 2 != p[j]:
    		judge = "NO"
    		break

    if judge == "YES":
    	ans += 1


print(ans)

Submission status: Accepted

Solution code:
count = 0
n,m = map(int, input().split())
sw = {}
lt = {}
for i in range(1, m+1):
    s = map(int, input().split())
    s = list(s)
    k = s[0]
    s = s[1:]
    lt[i] = s
    for j in range(k):
        t = sw.get(s[j], [])
        t.append(i)
        sw[s[j]] = t
p = map(int, input().split())
p = list(p)

for i in range(pow(2, n)):
    sw_sta = [False] * (n + 1)
    for j in range(n):
        if (i & pow(2,j)) != 0:
            sw_sta[j + 1] = True
    allon = True
    for j in range(m):
        c = 0
        for k in lt[j + 1]:
            if sw_sta[k]:
                c += 1
        if c % 2 != p[j]:
            allon = False
            break
    if allon:
        count += 1
print(count)

Submission status: Accepted

Solution code:
n,m = (int(num) for num in input().split())

ls = []

for i in range(m):
    s = [int(num)-1 for num in input().split()]
    s.pop(0)
    ls.append(s)
    
#print(ls)
    
p = [int(num) for num in input().split()]
    
def isOK(k,s,p):
    r = 0
    for i in range (n):
        if (k >> i)%2 == 1 and i in s:
            r += 1
    #print(r,p)
    if r%2 == p:
        return True
    else:
        return False
    
ans = 0
    
for k in range(2**n):
    for i in range(m):
        f = True
        s = ls[i]
        if not isOK(k,s,p[i]):
            f = False
            break
    if f:
        ans += 1
        

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
sw=[[0]*N for m in range(M)]
for m in range(M):
    ks=list(map(int, input().split()))
    for i in ks[1:]:
        sw[m][i-1]=1
p=list(map(int, input().split()))
from itertools import product
ans=0
for x in product((0,1),repeat=N):
    a=1
    for m in range(M):
        s=0
        for i in range(N):
            s+=sw[m][i]*x[i]
        if s%2!=p[m]:
            a=0
            break
    ans+=a
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
def switch(count,onoff):
    global ans
    if count == n:
  #      print(count,onoff)
        l = 0
        for i,P in zip(ks,p):
            c = 0
            for j in i[1:]:
                c += onoff[j-1]
     #       print(c%2,P)
            if c%2 == P:
                l += 1
   #     print(l)
        if l == m:
            ans += 1
    else:
        count += 1
        switch(count,onoff+[1])
        switch(count,onoff+[0])

switch(0,[])
print(ans)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
KS=[]
for i in range(m):
  ks=[int(i) for i in input().split()]
  KS.append(ks)
P=[int(i) for i in input().split()]
ans=0
for Key in itertools.product(range(2),repeat=n):
  Key=list(Key)
  chk=True
  for i in range(m):
    on=0
    for j in range(KS[i][0]):
      on+=Key[KS[i][j+1]-1]
    if on%2!=P[i]:
      chk=False
  if chk==True:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=[]
for i in range(M):
    s=list(map(int,input().split()))
    S.append(s[1:])
P=list(map(int,input().split()))
ans=0
for i in range(2**N):
    i=bin(i)[2:].zfill(N)
    p=[0]*M
    for k in range(N):
        for j in range(M):
            if i[k]=="1" and (k+1 in S[j]):
                p[j]+=1
                p[j]%=2
    if p==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()))

def check(n):
	i = 0
	for k, *s in KS:
		c = 0
		for q in s:
			if n & (1 << (q - 1)):
				c += 1
		if P[i] != c % 2:
			return False
		i += 1
	return True

#print(check(3))
#print()

count = 0
for n in range(2 ** N):
	if check(n):
		count += 1
print(count)

Submission status: Accepted

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

def main():
    N, M = LI()
    s_li = []
    for i in range(M):
        s_li.append(LI()[1:])
    p_li = LI()

    import itertools
    counter = 0
    for i in itertools.product([0,1], repeat=N):  # product of switches
        for s, p in zip(s_li, p_li): # for each lights
            if sum([i[num-1] for num in s])%2 != p:
                break
        else:
            counter += 1
    print(counter)

main()

Submission status: Accepted

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

ans = 0
def isAllOn(switches):
    for i in range(M):
        s = s_list[i]
        p = p_list[i]
        cnt = 0
        for idx in s:
            cnt += switches[idx-1]
        if cnt % 2 != p:
            return False
    return True


def bfs(stack):
    global ans
    global N
    if len(stack) == N:
        if isAllOn(stack):
            ans += 1
        return

    for i in [0, 1]:
        _stack = stack[::]
        _stack.append(i)
        bfs(_stack)

bfs([])
print(ans)

Submission status: Accepted

Solution code:
from itertools import chain,combinations
import numpy as np


# From: https://qiita.com/hrsma2i/items/d98f9b1fceeb23d67eef
def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))


def main():
    n, m = [int(val) for val in input().split()]
    vectors_for_each_switch = [[] for _ in range(n)]
    for light_id in range(m):
        k_and_ss = [int(val) for val in input().split()]
        k = k_and_ss[0]
        if k == 0:
            switches = []
        else:
            switches = k_and_ss[1:]
        switches = [switch - 1 for switch in switches]
        switches = set(switches)
        for switch_id in range(n):
            is_in = switch_id in switches
            vectors_for_each_switch[switch_id].append(is_in)

    vectors_for_each_switch = [np.asarray(vec, dtype=int) for vec in vectors_for_each_switch]
    target_vector = np.asarray([int(val) for val in input().split()], dtype=int)

    count = 0
    for switch_set in powerset(range(n)):
        target = target_vector
        for on_switch in switch_set:
            target = target + vectors_for_each_switch[on_switch]
        if all(target % 2 == 0):
            count += 1
    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
kss = []
for i in range(M):
    tmp = list(map(int, input().split()))
    k = tmp[0]
    s = tmp[1:]
    kss.append([k, s])
ps = list(map(int, input().split()))

def check_on(s_all, s, p):
    oncnt = 0
    for i in s:
        if s_all[i]:
            oncnt += 1
    if oncnt % 2 == p:
        return True
    else:
        return False

def check_all_on(s_all, kss, ps):
    for i in range(M):
        s = kss[i][1]
        p = ps[i]
        if not check_on(s_all, s, p):
            return False
    return True


def rec(s_all, kss, ps, cnt):
    if len(s_all) == N+1:
        if check_all_on(s_all, kss, ps):
            cnt[0] += 1
            return
    else:
        s_all.append(0)
        rec(s_all, kss, ps, cnt)
        s_all.pop()

        s_all.append(1)
        rec(s_all, kss, ps, cnt)
        s_all.pop()

s_all = [0]
cnt = [0]
rec(s_all, kss, ps, cnt)
print(cnt[0])

Submission status: Accepted

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

ks = [np.array(list(map(int, input().split()))[1:]) - 1 for i in range(m)]
p = list(map(int, input().split()))

def get_state(s):
    return np.array([s[k].sum() for k in ks]) % 2 == p

def get_bin(integer, length):
    return (np.array([integer & (2 ** i) for i in range(length)]) > 0).astype(int)

print(sum(get_state(get_bin(i, n)).all() for i in range(2**n)))

Submission status: Accepted

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

connections = []
for _ in range(M):
    k, *S = [int(i) for i in input().split()]
    connections.append([i-1 for i in S])
P = [int(i) for i in input().split()]


def get_bin(x, n=0):
    return format(x, 'b').zfill(n)


switches = [False] * N

count = 0
for i in range(2 ** N):
    binstr = get_bin(i, N)
    switches = [s == '1' for s in binstr]
    for j in range(M):
        conn = connections[j]
        p = P[j]

        f = 0
        for c in conn:
            if switches[c]:
                f += 1
        if f % 2 != p:
            break
    else:
        count += 1
print(count)

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 itertools import product

def main():
    N, M = LI()
    kss = []
    for _ in range(M):
        kss.append(LI_()[1:])
    pp = LI()
    ans = 0
    for sw in product(range(2), repeat=N):
        ok = True
        for ks, p in zip(kss, pp):
            check = 0
            for k in ks:
                if sw[k]:
                    check += 1
            if check % 2 != p:
                ok = False
                break
        if ok:
            ans += 1
    return ans

print(main())

Submission status: Accepted

Solution code:
import numpy as np
N,M=map(int,input().split())
connect=np.zeros((M,N))
for i in range(M):
	c = list(map(int,input().split()))[1:]
	for sw in c:
		connect[i][sw-1]=1
req=np.array(list(map(int,input().split())))
ptns=[]
for i in range(2**N):
	ptns.append(list(format(i, '0{}b'.format(N))))
ptns=np.array(ptns).astype(np.uint8)
ans=0
for i in range(2**N):
	co = np.mod(np.sum(ptns[i] * connect, axis=1),2)
	co = co.reshape((1,-1))
	if np.sum(co!=req)==0:
		ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

s = defaultdict(list)
for i in range(M):
    tmp = [int(x) for x in input().split()]
    s[i] = set(tmp[1:])
p = [int(x) for x in input().split()]

ans = 0
for i in range(1 << N):
    ptn = set()
    for j in range(N):
        if i & (1 << j):
            ptn.add(j + 1)

    flag = True
    for k in range(M):
        c = len(s[k] & ptn) % 2
        if c != p[k]:
            flag = False
            break

    if flag:
        ans += 1
print(ans)

Submission status: Accepted

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

num = 2**N
ans = 0
for i in range(num):
    bit = bin(i)[2:].zfill(N)
    on, off = [], []
    ret = 0
    for j, b in enumerate(bit):
        j += 1
        if b == '1':
            on.append(j)
        else:
            off.append(j)
    for k in range(M):
        on = set(on)
        onon = set(K[k][1:])
        if len(on & onon) % 2 == P[k]:
            ret += 1
    if ret == M:
        ans += 1

print(ans)

Submission status: Accepted

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

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

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

cnt = 0

for i in range(2 ** n):
    bin_i = '{:010b}'.format(i)[::-1]

    for i in range(m):
        ks = kss[i]
        k = ks[0]
        s = ks[1:]

        sum_s = 0

        for j in range(k):
            sum_s += int(bin_i[s[j]-1])

        if sum_s % 2 != p[i]:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from itertools import product


def li():
    return list(map(int, input().split()))


def is_on(state, p, s_list):
    return sum(list(map(lambda x: state[x - 1], s_list))) % 2 == p


if __name__ == '__main__':
    [n, m] = li()
    ks_list = [li() for _ in range(m)]
    p_list = li()

    pattern = 0

    for state in product([0, 1], repeat=n):
        is_all = True
        for index, ks in enumerate(ks_list):
            if not is_on(state, p_list[index], ks[1:]):
                is_all = False
        if is_all:
            pattern = pattern + 1
    print(pattern)

Submission status: Accepted

Solution code:
def solve():
    N,M = map(int,input().split())
    S=[]
    for i in range(M):
        S.append(list(map(int,input().split()))[1:])
    P = list(map(int,input().split()))

    ans = 0
    for i in range(2 ** N):
        st = [(i >> j) & 1 for j in range(N)]
        for j in range(M):
            #print(i,j,S[j])
            if sum([st[k-1] for k in S[j]]) % 2 != P[j]:
                break
        else:
            ans += 1

    print(ans)

solve()

Submission status: Accepted

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

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

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


ans=0
for i in range(2**N):
	ons=[]
	for j in range(N):
		if (i//(2**j))%2:
			ons.append(j+1)
	#print(ons)
	for j in range(M):
		c=0
		for k in range(len(s[j])):
			if s[j][k] in ons:
				c+=1
		#print(c)
		flag=0
		if c%2!=p[j]:
			flag=1
			break
	if flag:
		continue
	else: ans+=1


print(ans)

Submission status: Accepted

Solution code:


def read_input():
    n, m = map(int, input().split())

    slist = []
    for i in range(m):
        temp = list(map(int, input().split()))
        k = temp[0]
        s = temp[1:]
        slist.append((k, s))

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

    return n, m, slist, p


def switch_gen(n):
    curr = 0

    while True:
        bincurr = bin(curr)[2:]

        if len(bincurr) > n:
            return None
        bincurr = [int(c) for c in bincurr]
        t = [0] * (n - len(bincurr))
        t.extend(bincurr)
        yield t

        curr += 1


def check_condition(switch, slist, plist):
    for s, p in zip(slist, plist):
        count = 0
        for i in s[1]:
            if switch[i - 1] == 1:
                count += 1

        if count % 2 != p:
            return False

    return True


def submit():
    n, m, slist, p = read_input()

    count = 0
    for switch in switch_gen(n):
        if check_condition(switch, slist, p):
            count += 1

    print(count)




if __name__ == '__main__':
    submit()

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

ss = []
for i in range(m):
	tmp = list(map(int, input().split()))
	s = [0 for _ in range(n)]
	for t in tmp[1:]:
		s[t - 1] = 1
	ss.append(s)
ss = np.array(ss)
#print(ss)

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

ans = 0
for x in itertools.product(range(2), repeat = n):
	lights = np.dot(ss, np.array(x))
	if sum([1 for i in range(m) if lights[i] % 2 == ps[i]]) == m:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

Ss = []
for i in range(M):
    Ss.append([int(x) for x in input().split()][1:])

Ps = [int(x) for x in input().split()]

c = 0
for onoff in product([0,1], repeat=N):
    d = 0
    for i, S in enumerate(Ss):
        t = sum(onoff[s-1] for s in S)
        if t % 2 == Ps[i]:
            d += 1
    if d == M:
        #print("*", onoff)
        c+=1
print(c)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

def readInt():
    return int(input())

def readList():
    return list(input().split())

def readListI():
    return list(map(int, input().split()))

def pattern(n):
    ret = []
    for i in range(pow(2, n)):
        p = [0 for _ in range(n)]
        for j in range(n):
            if (i >> j) & 1:
                p[j] = 1
        ret.append(p)
    return ret

def main():
    n, m = readListI()
    lk = []
    lls = []
    for _ in range(m):
        d = readListI()
        k = d[0]
        ls = [s-1 for s in d[1:]]
        lk.append(k)
        lls.append(ls)
    lp = readListI()
    ret = 0
    for p in pattern(n):
        ok = True
        for i, ls in enumerate(lls):
            if sum(p[s] for s in ls) % 2 != lp[i]:
                ok = False
                break
        if ok:
            ret += 1
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[]
for i in range(m):
  s+=[list(map(int,input().split()))]
#print(s)
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
  a=[]
  for _ in range(n):
    a+=[i%2]
    i//=2
  #print(a)
  pp=1
  for j in range(m):
    num=0
    for si in s[j][1:]:
      if a[si-1]==1:
        num+=1
    #print(num)
    if num%2!=p[j]:
      pp=0
  if pp==1:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

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

k, s = [], []

for i in range(M):
    line = readline().split()
    k.append(int(line[0]))
    s.append(list(map(int, line[1:])))

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

total = 0
for bits in range(0, 2 ** N):
    flag = True
    for i in range(M):
        bsum = 0
        for b in s[i]:
            bsum += ((bits >> (b - 1)) & 1)
        flag = flag and (bsum % 2 == p[i])
    if flag:
        total += 1

print(total)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
sw = []
for i in range(m):
    L = list(map(int,input().split()))
    L.pop(0)
    sw.append(L)
p = list(map(int,input().split()))
def s(x,N):
    LI = []
    for i in range(N):
        A = x % (2**(N-i))
        B = A // (2**(N-1-i))
        if B == 1:
            LI.append(i+1)
    return LI
ans = 0
for i in range(2**n):
    ansl = []
    for j in range(m):
        C = list(set(sw[j]) & set(s(i,n)))
        if len(C) % 2 == p[j]:
            ansl.append(1)
    if len(ansl) == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

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

def tobinary(i):
    l = [0 for j in range(N)]
    for k in range(N):
        l[k] = i % 2
        i //= 2
    return l

ans = 0
for i in range(2**N):
    swich = tobinary(i)
    for m in range(M):
        cnt = 0
        for k_i in range(k[m]):
            if swich[s[m][k_i]-1]:
                cnt += 1
        if cnt % 2 == p[m]:
            blight = True
        else:
            blight = False
            break
    if blight == True:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict
from functools import reduce
from itertools import product

# s = input()
# n, m = int(input())
# A = list(map(int, input().split()))
n, m = map(int, input().split())

light = defaultdict(list)

for i in range(m):
    A = list(map(int, input().split()))
    for s in range(1, A[0]+1):
        light[i].append(A[s]-1)

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


for state in product([0,1], repeat=n):
    for i in range(m):
        if len(list(filter(lambda s: state[s] == 1, light[i])))%2 != p[i]:
            break
    else:
        res += 1

print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

S = defaultdict(list)

for i in range(M):
    inp = list(map(int,input().split()))
    for j in range(1,inp[0]+1):
        S[inp[j]].append(i)

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

ans = 0
for i in range(int(pow(2,N))):
    u = i
    s_list = [0 for i in range(M)]
    for j in range(1,N+1):
        if u%2==1:
            for s in S[j]:
                s_list[s] += 1
        u//=2
    is_tento = True
    for s in range(M):
        if s_list[s]%2!=P[s]:
            is_tento = False
            break
    if is_tento:ans += 1

print(ans)

Submission status: Accepted

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

flgs = [0]*M
for i in range(M):
	k,*vals = map(int,input().split())
	for v in vals:
		flgs[i] |= 1 << (v-1)

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

cnt = 0
for bit in range(2**N):
	cnt_tmp = 1
	for i,f in enumerate(flgs):
		if len([j for j in range(N) if ((f&bit) & (1<< j)) != 0]) % 2 != p[i]:
			cnt_tmp = 0
	cnt += cnt_tmp
print(cnt)

Submission status: Accepted

Solution code:
import itertools
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
ks = []
for i in range(M):
    ks.append(inpl())
p = inpl()

ans = 0
for s in itertools.product(range(2),repeat=N):
    for i in range(M):
        if (sum([ s[n-1] for n in ks[i][1:]]) - p[i]) % 2:
            break
    else:
        ans += 1

print(ans)