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:
from itertools import combinations


def solve():
    N, M = map(int, input().split())
    k = [0 for _ in range(M)]
    s = [[] for _ in range(M)]
    for i in range(M):
        k[i], *s[i] = map(int, input().split())
    p = list(map(int, input().split()))
    
    ans = 0
    for i in range(1, N+1):
        for on_switches in combinations(range(1, N+1), i):
            flag = True
            for j in range(M):
                count = 0
                for on_switch in on_switches:
                    if on_switch in s[j]:
                        count += 1
                if count % 2 != p[j]:
                    flag = False
                    break
            if flag:
                ans += 1
    
    if 1 not in p:
        ans += 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import numpy as np

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

    k[i] = tmp[0]
    s.append(tmp[1:])
p = [int(i) for i in input().split()]

# N個のスイッチのon/offのパターン2^N通りをすべて調査
# 1がon、0がoff
answer = 0
for i in range(2 ** N):
# M個の電球について調査
    flag = 1 # 1: 全部点灯
    for j in range(M):
        count = 0
        need = s[j]
        for k in need:
            if ((i >> k-1) & 1):
                count += 1
        if np.mod(count, 2) != p[j]:
            flag = 0
    if flag == 1:
        answer += 1

print(answer)

Submission status: Accepted

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

def check(num, i, P):
  SS = S[i]
  PP = P[i]
  on = 0
  for j in range(1,1+SS[0]):
    on += num>>(SS[j]-1) & 1
    on = on%2
  if on == PP:
    return True
  else:
    return False
cnt = 0
for nu in range(2**N):
  ck = True
  for i in range(M):
    ck = ck and check(nu,i,P)
    if ck == False:
      break
  if ck == True:
    cnt +=1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import product

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

# print(n, m, s, p)

ans = 0

for tpl in product([0, 1], repeat=n):
    # print(tpl)
    bl = True

    for j in range(m):
        cnt_on = sum(tpl[k - 1] for k in s[j])
        if cnt_on % 2 != p[j]:
            bl = False
            break
    if bl:
        ans += 1

print(ans)

Submission status: Accepted

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

a = []
def dfs(b):
    if len(b) == N:
        a.append(b)
        return b
    for i in range(2):
        dfs(b + [i])
dfs([])

ans = 0
for i in range(len(a)):
    ok = 0
    switches = a[i]
    for j in range(M):
        on = 0
        for _j in range(k[j][0]):
            if switches[k[j][_j+1]-1] == 1:
                on += 1
        if on % 2 == p[j]:
            ok += 1
    if ok == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
sw = []
for i in range(M):
    tmp = list(map(int,input().split()))
    sw.append(tmp[1:])
p = list(map(int,input().split()))
bit = []
for i in range(2**N):
    tmp = list(map(int,bin(i)[2:].zfill(N)))
    bit.append(tmp)
ans = 0
for i in range(2**N):
    all = True
    for j in range(M):
        num = 0
        for k in range(len(sw[j])):
            if bit[i][sw[j][k]-1] == 1:
                num += 1
        if num%2 != p[j]:
            all = False
            break
    ans += all
print(ans)

Submission status: Accepted

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

ans = 0
#あるつき方について
for i in range(1 << n):
    al = True
    #つき方二進数
    v = [bool(i & (1 << x)) for x in range(n)]
    #電球全体
    for j in range(m):
        #onになってるスイッチの個数
        num = 0
        #スイッチの番号
        for t in s[j]:
            num += v[t - 1]
        if p[j] != num % 2:
            al = False
    ans += al
print(ans)

Submission status: Accepted

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


for i in range(2**n):
    s = [0] * n
    flag=True
    for j in range(n):
        if (i>>j)&1==1:
            s[j]=1

    for k in range(m):
        count=0
        for l in range(a[k][0]):
            if s[a[k][l+1]-1]==1:
                count+=1
        if count%2!=p[k]:
            flag=False
            break
        if not flag:
            break

    if flag:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
conditions = [tuple(map(int,input().split())) for _ in range(m)]
P = tuple(map(int,input().split()))
ans = 0
impossible = False
for i in range(2 ** n):
  switches = []
  for j in range(n):
    if i >> j & 1:
      switches.append(1)
    else:
      switches.append(0)
  for l in range(m):
    s_cnt = 0
    for s_needed in range(conditions[l][0]):
      s = conditions[l][s_needed + 1]
      if switches[s - 1] == 1:
        s_cnt += 1
    if s_cnt % 2 != P[l]:
      impossible =True
      break
  if impossible:
    impossible = False
    continue
  ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
def main():
    N, M = map(int, input().split())
    s = []
    for _ in range(M):
        t = tuple(map(int, input().split()))
        s.append(t)
    p = tuple(map(int, input().split()))
    a = 0
    for i in range(2**N):
        for j in range(M):
            x = 0
            for k in s[j][1:]:
                if i & (1 << (k-1)):
                    x += 1
            if x % 2 != p[j]:
                break
        else:
            a += 1
    return a
print(main())

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
k = [0] * M
s = [0] * M
for i in range(M):
    ks = list(map(int,input().split()))
    for j,x in enumerate(ks):
        if j == 0:
            k[i] = x
            continue
        s[i] += 1 << x-1
p = [int(i) for i in input().split()]

answer = 0
for i in range(2**N):
    count = [0] * M
    for j in range(M):
        tmp = s[j] & i
        while tmp:
            if tmp & 1:
                count[j] += 1
            tmp >>= 1

        # j番目の電球が光る場合 count[j] = 1
        if count[j] % 2 == p[j]:
            count[j] = 1
        else:
            count[j] = 0

    # 全ての電球が点灯する場合
    if not 0 in count:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
k = []
s = []
p = []
for i in range(M):
    tmpk, *tmps = map(int, input().split())
    k.append(tmpk)
    s.append(tmps)
    s[i] = [x-1 for x in s[i]]
*p, = map(int, input().split())
ans = 0
for pattern in range(2**N):
    flag = True
    for light in range(M):
        tmp = 0
        for i in s[light]:
            tmp += (pattern >> i)&1
        if tmp % 2 != p[light]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
lis=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
s=0
for i in range(2**n):
  ok=True
  for k in range(m):
    cnt=0
    for j in range(n):
      if (i>>j)&1:
        if j+1 in lis[k][1:]:
          cnt+=1
    if cnt%2!=p[k]:
      ok=False
  if ok:
    s+=1
print(s)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
den=[0]*M
for i in range(M):
  s=list(map(int,input().split()))[1:]
  for j in range(len(s)):
    num=s[j]-1
    den[i]|=(1<<num)

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

ans=0
for i in range(2**N):
  # ループ一回が各スイッチの状況
  # これに対して、各電球の条件をチェックして、すべての電球が点くかをチェック
  ok=True
  for j in range(len(den)):
    # 電球の条件　例[01001]で1になっているものとスイッチの条件　例：[11001]を
    # 突き合わせて、両方とも1になっているものの数を数える。
    # ＝ANDした数で、いくつ1が立っているかを見る。
    res=i&den[j]
    cnt=0
    while res>0:
      if res&1:
        cnt+=1
      res>>=1
    if cnt%2!=P[j]:
      ok=False
      break
  if ok:
    ans+=1
      
print(ans)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
ks = [[int(i) for i in input().split()] for _ in range(m)]
p = [int(i) for i in input().split()]
cnt = 0
for i in range(2**n):
  on = set(j + 1 for j in range(n) if i >> j & 1 == 1)
  flag = True
  for j in range(m):
    _, *s = ks[j]
    flag &= len(on & set(s)) % 2 == p[j]
  cnt += flag
print(cnt)

Submission status: Accepted

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

    for j in range(m):
        cnt=0
        for k in s[j]:
            if i&1<<(k-1):
                cnt+=1
        if cnt%2!=p[j]:
            break
    else:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N, M = map(int, input().split())
S = []
for _ in range(M):
    xs = list(map(int, input().split()))
    S.append([x - 1 for x in xs[1:]])
P = list(map(int, input().split()))

counter = 0
for sw in product([True, False], repeat=N):
    for i in range(M):
        if sum(1 if sw[j] else 0 for j in S[i]) % 2 != P[i]:
            break
    else:
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
from itertools import product

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

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

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

ans = 0
for j in product([1,0],repeat=n):
    for i, s in enumerate(x):
        if sum([j[k-1] == 1 for k in s]) % 2 != p[i]:
            break
            
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

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

lst = [list(map(int, input().split())) for _ in range(M)]
p_lst = np.array(list(map(int, input().split())))

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

for j, lst2 in enumerate(lst):
    for i in lst2[1:]:
        mat[j][i-1] = 1

mat_np = np.array(mat)

for a in product([0, 1], repeat=N):
    l = np.array(a)
    b = np.dot(mat_np, l)%2
    if np.sum(b==p_lst)==M:ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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

# bit全探索(スイッチの入れ方を全探索する)
for i in range(1 << N):
    for r in range(M):  # 全てのランプがついてるかチェック
        on_sum = 0  # ランプrにおいて、onのスイッチの数
        for j in range(N):  # スイッチのj番目について
            if i >> j & 1 and j in lamps[r]:
                on_sum += 1  # スイッチjがランプrに繋がってて、onならon_sum+=1
        if on_sum % 2 != p[r]:  # on_off check
            break  # 一つでもoffなら次のbitに
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

def isOn(sw, b, p):
    onCount = 0
    for i in range(1,b[0]+1):
        if sw[b[i]-1] == '1':
            onCount += 1
    if onCount % 2 == p:
        return True
    return False

ans = 0
for i in range(1<<N):
    sw = format(i, '0' + format(N, 'd') + 'b')
    for j in range(M):
        if not isOn(sw, B[j], P[j]):
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1 << n):
    al = True
    v = [bool(i & (1 << x)) for x in range(n)]
    for j in range(m):
        num = 0
        for t in s[j]:
            num += v[t - 1]
        if p[j] != num % 2:
            al = False
    ans += al
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
D = tuple(tuple(int(i) for i in input().split())for _ in range(M)) 
# 各電球から見た:D[][0]はつながっているスイッチの個数なことに注意
S = [[]for i in range(N)]
# 各スイッチから見る
for i in range(M):
    for j in D[i][1:]:
        S[j-1].append(i)
P = tuple(int(i) for i in input().split())
ans = 0
for i in range(2**N):
    bit = bin(i)[2:][::-1]
    L = [0 for _ in range(M)]
    for j,s in enumerate(list(bit)):
        if s == '1':
            for k in S[j]:
                L[k] += 1
    flag = True
    for j in range(M):
        if L[j]%2 != P[j]:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


N, M = map(int, input().split())
lamps = [list(map(lambda x:int(x)-1, input().split()))[1:]
         for _ in range(M)]
# 1番目だけを除いて繋がっているスイッチを表している,-1しているのはリストと合わせるため


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


# bit全探索
for i in range(2**N):
    for r in range(M):  # ランプがすべてついているかのチェック
        on_sum = 0  # 何個スイッチがonになっているか
        for j in range(N):  # スイッチのｊ番目について、
            if i >> j & 1 and j in lamps[r]:
                on_sum += 1 # スイッチjがランプrに繋がってて、onならon_sum+=1
        if on_sum % 2 != p[r]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
sw = [list(map(int, input().split())) for _ in range(m)]
for x in sw:
    x.pop(0)
p = list(map(int, input().split()))

ans = 0
for i in range(1<<n):
    s = str(bin(i).replace('0b', '')).zfill(n)
    for j in range(m):
        sum_sw=0
        for k in sw[j]:
            sum_sw+=int(s[k-1])
        if p[j] != sum_sw%2:
            break
    else:
        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()))
A = int("1"*n,2)
cnt = 0
for i in range(A+1):
    a = bin(i)[2:].zfill(n)
    l = list(map(int,list(a)))
    for j in range(m):
        cnt1 = 1
        b = 0
        for s in S[j]:
            b += l[s-1]
        if b%2 != P[j]:
            cnt1 = 0
            break
    cnt += cnt1
print(cnt)

Submission status: Accepted

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

for i in range(M):
    a = list(map(int,input().split()))
    a.pop(0)
    sum = 0
    for j in range(len(a)):
        sum += 2**(a[j]-1)
    array.append(sum)

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

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

total = 0
for switch in range(s+1):
    c = 0
    for i in range(M):
        if (bin(switch & array[i]).count('1'))%2 == p[i]:
            c += 1
    if c == M:
        total += 1

print(total)

Submission status: Accepted

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

ans=0

for i in range(2**n):
    l = [False]*n
    for j in range(n):
        if(i>>j & 1):
            l[j] = True

    light = 0
    for x,aa in enumerate(a):
        cnt = 0
        for y,k in enumerate(aa):
            if y == 0:
                continue
            if l[k-1] == True:
                cnt += 1
        if cnt%2 == p[x]:
            light += 1
    if light == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N, M = MAP()
L = [MAP()[1:] for _ in range(M)]
P = MAP()

#print(N,M,L,P)

switches = []
for i in range(2**N):
	switch = [0]*N
	for j in range(N):
		if ((i>>j) & 1):
			switch[N-j-1] = 1
	switches.append(switch)

ans = 0
for s in switches:
	for idx,l in enumerate(L):
		count = 0
		#print(s, P[idx], l)
		for ll in l:
			count+=s[ll-1]
		if count%2!=P[idx]: break
	else:
		ans += 1

print(ans)

Submission status: Accepted

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

def ri():
    return int(input())

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

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

def main():
    n, m = rli()
    switch = []
    for i in range(m):
        tmp = rli()
        k = tmp[0]
        ls = tmp[1:]
        switch.append(ls)
    lp = rli()
    ans = 0
    def check(mask):
        on_off = []
        for i in range(0, n):
            on_off.append(mask & (1 << i))
        for i in range(m):
            cnt = sum(1 for s in switch[i] if on_off[s-1])
            if cnt % 2 != lp[i]:
                return 0
        return 1
    ans = 0
    for i in range(1 << n):
        ans += check(i)
    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
A = []
for _ in range(m):
  k, *s = map(int, input().split())
  c = 0
  for i in s:
    c += 2**(i-1)
  A.append(c)
P = tuple(map(int, input().split()))
ans = 0
for i in range(2**n):
  f = True
  for j in range(m):
    c = bin(i & A[j]).count("1")
    if c%2 != P[j]:
      f = False
      break
  if f:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
switch = [list(map(int,input().split())) for m in range(M)]
p = list(map(int,input().split()))
# スイッチのONとOFFの組合せ(1がONで0がOFF)
S = list(itertools.product([0,1], repeat=N))
ans = 0
for s in S:
    s_ok = 0
    # 全ての電球に対して
    for m in range(M):
        count = 0
        # 1つの電球の全てのスイッチに対して
        for i in range(1, switch[m][0]+1):
            if s[switch[m][i]-1] == 1:
                count += 1
        if count%2 == p[m]:
            s_ok += 1
        else:
            break
    if s_ok == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
switch = [list(map(int,input().split())) for m in range(M)]
p = list(map(int,input().split()))
S = list(itertools.product([0,1], repeat=N))
ans = 0
for s in S:
    s_ok = 0
    for m in range(M):
        count = 0
        for i in range(1, switch[m][0]+1):
            if s[switch[m][i]-1] == 1:
                count += 1
        if count%2 == p[m]:
            s_ok += 1
        else:
            break
    if s_ok == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
switch = [list(map(int,input().split())) for m in range(M)]
p = list(map(int,input().split()))
S = list(itertools.product([0,1], repeat=N))
ans = 0
for s in S:
    s_ok = 0
    for m in range(M):
        count = 0
        for i in range(1, len(switch[m])):
            if s[switch[m][i]-1] == 1:
                count += 1
        if count%2 == p[m]:
            s_ok += 1
        else:
            break
    if s_ok == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import copy

N,M = map(int, input().split())
jisho = [[] for i in range(N)]
for i in range(M):
    val = input().split()
    for j in val[1:]:
        jisho[int(j)-1].append(i)

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

sw = []
def create_ki(data):
    if len(data) == N:
        sw.append(data)
        return
    tmp = copy.copy(data)
    tmp.append(0)
    create_ki(tmp)
    tmp2 = copy.copy(data)
    tmp2.append(1)
    create_ki(tmp2)

create_ki([])

ans = 0
for val in sw:
    num = 0
    sw2 = [0]*M
    for i in val:
        if i == 0:
            num += 1
            continue
        data = jisho[num]
        for j in data:
            sw2[j] += 1
        num += 1
    cn = 0
    for j in sw2:
        if j % 2 != p[cn]:
            break
        cn += 1
    if cn == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
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 bit in range(2**N):
    lamp = 0
    switch = [0] * N
    # インデックスに対応したランプがついてる(1, 0)ように変換
    for j in range(N):
        if (bit >> j) & 1 == 1:
            switch[j] = 1
    # 各電球ごとに確認
    for i in range(M):
        cnt = 0
        for k in range(N):
            if k+1 in S[i] and switch[k] == 1:
                cnt += 1
        # print("cnt", cnt)
        if cnt % 2 == P[i]:
            lamp += 1
    if lamp == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
tmp=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
k=[tmp[i][0] for i in range(m)]
s=[tmp[i][1:] for i in range(m)]
ans=0
for switch in range(2**n):
  on_all=True
  for light in range(m):
    cnt=0
    for connect in s[light]:
      if switch>>(connect-1)&1==1:
        cnt+=1
    if cnt%2!=p[light]:
      on_all=False
  if on_all:
    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()))

ans = 0

for i in range(2 ** n):
    switch = [0 for i in range(n)]
    for j in range(n):
        if ((i >> j) & 1):
            switch[n - 1 - j] = 1
    for l in range(m):
        cnt = 0
        for s in K[l][1:]:
            cnt += switch[s-1]
        if cnt % 2 != P[l]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
L=[list(map(int,input().split()))[1:] for _ in range(M)]
P=list(map(int,input().split()))
ans=0
for i in range(2**N):
  lit=[0]*M
  for j,switch in enumerate(L):
    cnt=0
    for s in switch:
      if i>>(s-1)&1:
        cnt+=1
    if cnt%2==P[j]:
      lit[j]=1
    else:
      lit[j]=0
  if all(lit): ans+=1 
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
L=[list(map(int,input().split()))[1:] for _ in range(M)]
P=list(map(int,input().split()))
ans=0
for i in range(2**N):
  lit=[0]*M
  for j,switch in enumerate(L):
    cnt=0
    for s in switch:
      if i>>(s-1)&1:
        cnt+=1
    if cnt%2==P[j]:
      lit[j]=True
    else:
      lit[j]=False
  if all(lit): ans+=1 
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
L=[list(map(int,input().split())) for _ in range(M)]
P=list(map(int,input().split()))
ans=0
for i in range(2**N):
  lit=[0]*M
  for j,switch in enumerate(L):
    cnt=0
    for s in switch[1:]:
      if i>>(s-1)&1:
        cnt+=1
    if cnt%2==P[j]:
      lit[j]=True
    else:
      lit[j]=False
  if all(lit):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split(' '))
k = [0] * m
s = [[]] * m
for i in range(m):
  _input = [num for num in map(int, input().split(' '))]
  k[i] = _input[0]
  s[i] = _input[1:]
p = [num for num in map(int, input().split(' '))]

# print(n, m)
# print(k)
# print(s)
# print(p)

# スイッチのパターンデータ作成
s_pattern = [''] * (2**n)
str_format = '{:0' + str(n) + 'b}'
for i in range(2**n):
  s_pattern[i] = str_format.format(i)
# print(s_pattern)

ans = 0

for i in range(2**n):
  pattern = s_pattern[i]
  for j in range(m):
    need_switches = s[j]
    on_count = 0
    for switch in need_switches:
      if pattern[switch-1] == '1':
        on_count += 1
    # print(on_count, p[j])
    # 電球が点灯するか
    if on_count % 2 == p[j]:
      continue
    else:
      break
  else:
    # break で抜けていなければ場合はすべての電球が点灯する
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[[int(i) for i in input().split()] for i in range(m)]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    l=[False]*n
    for j in range(n):
        if(i>>j & 1):
            l[j]=True
    #ランプの状態が決定
    light=0
    for x,aa in enumerate(a):
        cnt=0
        for y,k in enumerate(aa):
            if y==0:
                continue
            if l[k-1]==True:
                cnt+=1
        if cnt%2==p[x]:
            light+=1
    if light==m:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
res=[0 for i in range(n)]
cnt=0

def ch():
    global res,cnt,p,a
    my_cnt=0
    for i in range(m):
        pre=0
        for j in range(len(a[i])):
            if j==0: continue
            pre+=res[a[i][j]-1]
        if p[i]==0:
            if pre%2==0:
                my_cnt+=1
        else:
            if pre%2==1:
                my_cnt+=1
    if my_cnt==m:
        #print(res)
        cnt+=1
        
def abc(i):
    global res
    if i==n:
        ch()
    else:
        res[i]=0
        abc(i+1)
        res[i]=1
        abc(i+1)

abc(0)
print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = [0] * m
s = [[]] * m
t = [set() for _ in range(n)]
for i in range(m):
    ki, *si = map(int, input().split())
    k[i] = ki
    for j in si:
        t[j - 1].add(i)
p = list(map(int , input().split()))
ans = 0
for i in range(2 ** n):
    on = [0] * m
    light = [0] * m
    for j in range(n):
        if((i >> j) & 1):
            for k in t[j]:
                light[k] += 1
            #print(j, t[j], light)
    is_all = True
    for x in range(m):
        is_all = is_all and (light[x] % 2 == p[x])
    if is_all:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

n, m = input().split()
n, m = int(n), int(m)
 
bulbs = []
 
for i in range(m):
    l = input().split()
    arr = [int(x) for x in l][1:]
    bulbs.append(arr)

needs = [int(x) for x in input().split()]
 
combos = 0

def test(lis):
  for i in range(m):
    curr = 0
    need = needs[i]
    for b in bulbs[i]:
      if lis[b-1] == 1:
        curr += 1
    if curr % 2 != need:
      return False
  return True
  
for i in itertools.product([0, 1], repeat=n):
  if test(list(i)):
    combos += 1

print(combos)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
lst = [LI() for _ in range(m)]
p = LI()
ans = 0
for i in range(2**n):
    b = [0]*n
    for j in range(n):
        if (i >> j) & 1:
            b[j] = 1
    for j in range(m):
        tmp = 0
        k = lst[j][0]
        for l in range(1,k+1):
            if b[lst[j][l]-1] == 1:
                tmp += 1
        if tmp % 2 != p[j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

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

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


        switch_num = 0
        for j in range(N):
            if i >> j & 1 and j+1 in conditions[condition_idx][1:]: # つながっているスイッチの押してあるものを数える
                switch_num += 1
        if switch_num%2 == p[condition_idx]:
            light_cnt += 1
    if light_cnt == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
light = []
for i in range(m):
    k = list(map(int, input().split()))
    aaaaa = [0 for i in range(n)]
    for i in range(k[0]):
        aaaaa[k[i+1] - 1] = 1
    aaaaa = int("".join(map(str, aaaaa)), 2)
    light.append(aaaaa)
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    flag = 1
    for j in range(len(light)):
        #print("i{}, j{} light[j] {}".format(i, j, light[j]))
        k = i & light[j]
        if list(bin(k)).count("1") % 2 != p[j]:
            flag = 0
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

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

msk = [0] * m
for i in range(m):
    lst = list(map(int, input().split()))
    for j in range(1, lst[0] + 1):
        msk[i] |= 1 << lst[j] - 1

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

ans = 0
for i in range(2 ** n):
    flg = True
    for j in range(m):
        tmp = i & msk[j]
        cnt = 0
        while tmp > 0:
            if tmp & 1:
                cnt += 1
            tmp >>= 1
        if cnt % 2 != p[j]:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Submission status: Accepted

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

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

K = [0] * M
S = [0] * M
P = [0] * M

for i in range(M):
    t_ = [int(x) for x in input().strip().split()]
    K[i], S[i] = t_[0], t_[1:]

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

def check(sw, s, p, M):
    for m in range(M):
        if sum([sw[i-1] for i in s[m]]) % 2 != p[m]:
            return 0
    else:
        return 1

def f(sw, s, p, M, i, K, N):
    if i == N:
        return check(sw, s, p, M)
    ans = 0
    for j in (0, 1):
        sw_ = sw[:]
        sw_[i] = j
        ans += f(sw_[:], s, p, M, i+1, K, N)
    return ans

print(f([0 for _ in range(N)], S, P, M, 0, K, N))