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:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
c=0
for i in range(2**n):
    xi=format(i,'b').zfill(n)
    light_count=0
    for j in range(m):
        xl=[i+1 for i, x in enumerate(xi) if x == '1']
        c1=0
        for k in range(1,len(l[j])):
            if l[j][k] in xl:c1+=1
        if c1%2==p[j]:light_count+=1
    if light_count==m:c+=1
print(c)

Submission status: Accepted

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

s = [[] for _  in range(M)]
k=[0]*M

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

cnt = 0

for i in range(1<<N):
    
    switch = []
    #各電球でOnのスイッチの数
    result =[0]*M
    
    #点灯しているスイッチを取得
    for j in range(N):
        if (i>>j&1):
            switch.append(j+1)
        else:
            continue
        

    #各ボタンの店頭している数をチェック
    for  w in range(len(switch)):
        temp = switch[w]
        for x in range(M):
            if s[x].count(temp)>0:
                result[x]+=1
                    
    flg =  True
    
    for u in range(M):
        if result[u]%2!=p[u]:
            flg = False
            
    if flg ==True:
        cnt+=1
        

print(cnt)

Submission status: Accepted

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

ans=0
for i in range(2**n):
    f=1
    for j in range(m):
        c=0
        for x in sw[j][1:]:
            x-=1
            c+=(i>>x)&1
        if c%2!=p[j]:
            f=0
    ans+=1 if f else 0
print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(2**N):
    check = [False] * M
    for j, bulb in enumerate(bulbs):
        on_sum = 0
        for b in bulb:
            if i >> (b-1) & 1:
                on_sum += 1
        
        if on_sum%2 == p[j]:
            check[j] = True
        
    if all(check):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from itertools import product
 
N, M = map(int, input().split())
switches = [list(map(int, input().split()[1:])) for _ in range(M)]
p = list(map(int, input().split()))
 
num_pattern = 0
for pattern in product(*[range(2) for _ in range(N)]):
    on_switches = [0]*M  # the number of on switches for each bulb
    for i, switch in enumerate(switches):
        for s in switch:
            if pattern[s-1] == 1:
                on_switches[i] += 1
                
    for i, on_num in enumerate(on_switches):
        if on_num % 2 != p[i]:
            break
    else:
        num_pattern += 1
print(num_pattern)

Submission status: Accepted

Solution code:
from itertools import product

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

num_pattern = 0
for pattern in product(*[range(2) for _ in range(N)]):
    on_switches = [0]*M  # the number of on switches for each bulb
    for i, switch in enumerate(switches):
        for s in switch:
            if pattern[s-1] == 1:
                on_switches[i] += 1
                
    for i, on_num in enumerate(on_switches):
        if on_num % 2 != p[i]:
            break
    else:
        num_pattern += 1
print(num_pattern)

Submission status: Accepted

Solution code:
N, M  = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(M)]
P = list(map(int, input().split()))
count = 0
for i in range(2**N):
    bit = format(i, 'b').zfill(N)
    light = [0] * M
    for j in range(M):
        num = 0
        for k in range(S[j][0]):
            num += int(bit[S[j][k+1]-1])
        if num % 2 == P[j]:
            light[j] = 1
    if all([on == 1 for on in light]):
        count += 1
print(count)

Submission status: Accepted

Solution code:
#ABC 128C
def main():
    import sys
    import itertools as ite
    N, M = map(int, sys.stdin.readline().split())
    Light = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
    P = list(map(int, sys.stdin.readline().split()))
    S = list(ite.product([0,1], repeat=N)) #スイッチの状態
    ans = 0
    for s_state in S:
        L_result = [0 for _ in range(M)]
        for m in range(M):
            for s_no in Light[m][1:]:
                L_result[m] += s_state[s_no-1]
        L_result = list(map(lambda x:x%2, L_result))
        if P == L_result:
            ans +=1
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
#ABC 128C
def main():
    import sys
    N, M = map(int, sys.stdin.readline().split())
    Light = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
    P = list(map(int, sys.stdin.readline().split()))
    #print(Light)
    #print(P)
    ans = 0
    for i in range(2**N):
        cnt = [0 for _ in range(M)]
        for m in range(M):
            for s in Light[m][1:]:
                cnt[m] += (i>>N-s)&1
        cnt = list(map(lambda x:x%2, cnt))
        if cnt == P:
            ans +=1
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s_input = [[] for i in range(m)]
k_input = [0]*m

for i in range(m):
    k_input[i],*s_input[i] = map(int,input().split())
p_input = list(map(int,input().split()))

#全探索？スイッチのonoffでビット全探索したときに条件と一致するかひとつづつ
ans=0
for i in range(2**n):
    flag = True
    switch = [0]*n
    for j in range(n):
        if ((i>>j)&1):
            switch[j]=1
    for k in range(m):
        tmp=0
        for s in s_input[k]:
            tmp+=switch[s-1]
        if tmp%2!=p_input[k]:
            flag=False
            break
    if flag:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M=[int(x) for x in input().rstrip().split()]
l=[]
for i in range(M):
  ks=[int(x) for x in input().rstrip().split()]
  l.append(ks)
p=[int(x) for x in input().rstrip().split()]

ans=0
onof=[False for i in range(N)]
for i in range(2**N):
  for j in range(N):
    if i>>j & 1:
      onof[j]=True
  
  cnt=0
  
  for s in range(M):
    bulb=l[s]
    now=0
    for t in range(len(bulb)-1):
      if onof[bulb[t+1]-1]==True:
        now+=1
    if now%2==p[s]:
      cnt+=1
  if cnt==M:
    ans+=1
  onof=[False for b in range(N)]

print(ans)

Submission status: Accepted

Solution code:
N,M=[int(x) for x in input().rstrip().split()]
l=[]
for i in range(M):
  ks=[int(x) for x in input().rstrip().split()]
  l.append(ks)
p=[int(x) for x in input().rstrip().split()]
now_l=[False for i in range(N)]
ans=0

for i in range(2**N):
  for j in range(N):
    if i>>j & 1:
      now_l[j]=True
  cnt1=0
  for s in range(M):
    now=l[s]
    cnt=0
    for t in range(len(now)-1):
      if now_l[now[t+1]-1]==True:
        cnt+=1
    if cnt%2==p[s]:
      cnt1+=1
  if cnt1==M:
    ans+=1
  now_l=[False for b in range(N)]
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
import fractions
import functools
import copy

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

result = 0
for i in range(2**n):
    count = 0
    for d in range(m):
        on = 0
        for sw in range(n):
            if i >> sw & 1:
                for o in range(k[d]):
                    if s[d][o] == sw+1:
                        on += 1
        if on % 2 == p[d]:
            count += 1
    if count == m:
        result += 1

print(result)

Submission status: Accepted

Solution code:
from itertools import combinations
def main():
    N, M = map(int, input().split())
    want = []
    for _ in range(M):
        tmp = list(map(int, input().split()))
        want.append(tmp[1:])
    cond = list(map(int, input().split()))
    
    swith = [i for i in range(N)]
    choice = 0
    cnt = 0
    while choice <= N:
        for comb in combinations(swith, choice):
            inp = [0 for _ in range(M)]
            
            for c in comb:
                for i, w in enumerate(want):
                    if c+1 in w:
                        inp[i] += 1
            
            flag = True
            for i in range(M):
                if inp[i]%2 != cond[i]:
                    flag = False    
            if flag:
                cnt += 1
        choice += 1
    print(cnt)
main()

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
K = [list(map(int, input().split())) for _ in range(M)]
P = list(map(int, input().split()))
count = 0
for i in range(2 ** N):
    S = [0] * N
    E = [0] * M
    for j in range(N):
        if i >> j & 1:
            S[j] = 1
    for m in range(M):
        SN = [k - 1 for k in K[m][1:]]
        if sum([S[sn] for sn in SN]) % 2 == P[m]:
            E[m] = 1
    if all(E):
        count += 1
print(count)

Submission status: Accepted

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


count=0
pattern=[]
for j in range(2**n):
  for k in range(m):
    switch=0
    for p in range(n):
      if (j>>p)&1 and p+1 in s[k]:
        switch+=1
    if switch%2!=t[k]:
      break
  else:
    count+=1
print(count)

Submission status: Accepted

Solution code:
import math
import copy
from queue import Queue
import heapq
import numpy as np

MOD = 5000000007

#n = int(input())
#b = int(input())
n, m = [int(i) for i in input().split()]
table = [[int(i)  for i in input().split()] for j in range(m)]
#table = [list(input()) for n in range(r)] #table[h][w]
p = [int(i) for i in input().split()]
#s = [int(i) for i in range(n)]
#p = [int(input()) for i in range(m)]
#s = input()

#list = list(s)
#dp = [MOD for _ in range(m)]
#dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
#dp = [[[0 for _ in range(11)] for _ in range(2)] for _ in range(11)]

#a = [[0 for _ in range(n+1)] for _ in range(n+1)]
#b = [[0 for _ in range(n+1)] for _ in range(n+1)]

count = 0
for i in range(2 ** n):
    flag = 1
    for j in range(0,m):
        temp = 0
        for k in range(table[j][0]):
            if((i >> (table[j][k+1] - 1)) & 1 ) :
                temp += 1
        if(temp % 2 != p[j]):
            flag = 0
    if(flag == 1):
        count += 1

print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
switch = [i for i in range(1,N+1)]
light = {}

for i in range(M):
  ks = list(map(int,input().split()))
  light[i+1] = ks[1:] 
p = list(map(int,input().split()))
res = 0
for i in range(2**len(switch)):  # 空集合を除く場合はrange(1, 2**len(list1))
    li = []
    cnt = 0
    for j in range(len(switch)):
        if (i >> j) &1 == 1:
            li.append(switch[j])
    for j in range(1,M+1):
      if len(set(light[j]) & set(li)) % 2 == p[j-1]:
        cnt += 1
    if cnt == M:
      res += 1
print(res)

Submission status: Accepted

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

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

ans = 0
for i in range(2**N):
    on_cnt = [0]*M
    ok = True
    for j in range(N):
        if (i>>j) & 1:
            for s in range(M):
                if (j+1) in S[s]:
                    on_cnt[s] += 1
    for t in range(M):
        if on_cnt[t] % 2 != p[t]:
            ok = False
    
    if ok:
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from itertools import product

n, m = map(int, readline().split())
ks = [list(map(int, readline().split()))[1:] for _ in range(m)]
p = list(map(int, readline().split()))
ans = 0
for bit in product([0, 1], repeat=n):
    for pp, ksi in zip(p, ks):
        cnt = 0
        for j in range(n):
            if bit[j] == 1 and (j + 1) in ksi:
                cnt += 1
        if cnt % 2 != pp:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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


k = []
s = []
ans = 0

for i in range(m):
    k_temp, *s_temp = list(map(int, input().split()))
    k.append(k_temp)
    s.append(s_temp)

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

for bit in range(1 << n):
    light_on = 0
    for i in range(m):
        switch_on = 0
        for j in range(k[i]):
            if (bit >> (s[i][j] - 1)) & 1:
                switch_on += 1

        if switch_on % 2 == p[i]:
            light_on += 1

    if light_on == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ks_mat =  [list(map(int, input().split())) for i in range(M)]
p = list(map(int, input().split()))
import itertools
OnOff_list = itertools.product([True,False],repeat=N)
ans = 0
for OnOff in OnOff_list:
    for i in range(M):#M個の電球のうち，i個目のものがついているか確認
        c = 0
        for k, j in enumerate(OnOff):
            if j and (k+1 in ks_mat[i][1:]):#スイッチがオンかつ，繋がっている場合はonになっているスイッチとしてカウント
                c += 1
        if not c % 2 == p[i]:#1つでもついていない場合は探索を中止
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
K = []
S = []
for m in range(M):
    l = list(map(int, input().split()))
    k = l.pop(0)
    K.append(k)
    S.append(l)
P = list(map(int, input().split()))
ans = 0
for n in range(1<<N):
    res = True
    for m in range(M):
        cnt = 0
        for q in range(K[m]):
            if n & (1<<S[m][q]-1):
                cnt += 1
        if cnt % 2 != P[m]:
            res = False
    if res:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys


input = sys.stdin.readline


def make_switch_set(i, s):
    if i == N:
        return [s]
    else:
        cs = s.copy()
        cs.add(i+1)
        return make_switch_set(i+1, s) + make_switch_set(i+1, cs)


def main():
    ans = 0
    for ss in switch_set:
        count = 0
        for switches, p in zip(S, P):
            match_num = len(ss & switches)
            if match_num % 2 == p:
                count += 1
        if count == M:
            ans += 1
    print(ans)


if __name__ == "__main__":
    N, M = map(int, input().split())
    S = []
    for _ in range(M):
        ipts = [int(ipt) for ipt in input().split()]
        S.append(set(ipts[1:]))
    P = [int(p) for p in input().split()]
    switch_set = make_switch_set(0, set())
    main()

Submission status: Accepted

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

n,m=n1()
ks=n3(m)
p=n1()

import itertools
ite=itertools.product([0,1],repeat=n)
ans=0
for line in ite:
    for i in range(m):
        c=0
        light=ks[i][1:]
        for j in light:
            c+=line[j-1]
        if c%2!=p[i]:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:

from copy import copy

ans = 0

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

  table = [None] * m
  for i in range(m):
    S = map(lambda x: int(x) - 1, input().split())
    next(S)
    table[i] = tuple(S)

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

  def check(switchs):
    global ans
    for i in range(m):
      S = table[i]
      total = 0
      for s in S:
        total += switchs[s]

      if total % 2 != P[i]:
        return False

    ans += 1
    return True

  default = [0 for _ in range(n)]
  dp = [default]
  check(dp[0])

  for i in range(n):
    for j in range(len(dp)):
      switchs = dp[j]
      new_switchs = copy(switchs)
      new_switchs[i] = 1
      check(new_switchs)
      dp.append(new_switchs)

  print(ans)


main()

Submission status: Accepted

Solution code:
def main():
    switch_number = []
    N, M = map(int, input().split())
    for _ in range(M):
        k = tuple(map(int, input().split()))
        switch_number.append(k[1:])
    p = list(map(int, input().split()))

    ans = 0
    for i in range(2 ** N):
        binary = list(map(int, format(i, 'b').zfill(N)))
        a = True
        for k, number in enumerate(switch_number):
            count = 0
            for j in number:
                if binary[j - 1] == 1:
                    count += 1
            if count % 2 != p[k]:
                a = False
                break
        if a:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

ans=0
for i in range(2**n):
    flag=False
    s=[0]*n
    
    for j in range(n):
        if ((i>>j) & 1):
            s[j]=1      
    
    for k in range(m):
        total=0
        judge=switches[k][1:]
        for l in judge:
            total += s[l-1]
            
        if total%2 == p[k]:
            flag=True
        
        if total%2 != p[k]:
            flag=False
            break
        
    if flag:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N, M = map(int, input().split())
S = []
for m in range(M):
    s = list(map(int, input().split()))
    S.append(s[1:])
P = list(map(int, input().split()))

ans = 0
for c in product([0, 1], repeat=N):
    ok = True
    for m in range(M):
        sm = 0
        for s in S[m]:
            sm += c[s - 1]
        if sm % 2 != P[m]:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N, M = map(int,input().split())
S = []
for m in range(M):
    s = list(map(int,input().split()))
    S.append(s[1:])
P = list(map(int,input().split()))

ans = 0
for c in product([0,1],repeat=N):
    ok = True
    for m in range(M):
        sm = 0
        for s in S[m]:
            sm += c[s-1]
        if sm % 2 != P[m]:
            ok = False
            break
    if ok:
        ans += 1
print (ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
light_bulb = [] #light_bulb[[k,s1,s2,,,sk],[k,,,,]]
for _ in range(m):
    x = list(map(int,input().split()))
    light_bulb.append(x)
p = list(map(int,input().split()))

def judge(switch):            
    for i in range(m):
        k = light_bulb[i][0]
        count = 0
        for j in range(1,k+1):
            on = light_bulb[i][j]-1
            if switch[on] == 1:
                count +=1
        if count % 2 != p[i]:
            return False
    return True
counter = 0
for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if (i>>j)&1:
            switch[j] = 1
    if judge(switch):
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
#bit & 演算子は同じ位置のbitが１の時１を返す
def main():
    n, m = map(int, input().split())
    # ｋは何個のスイッチにつながっているか、ｓはスイッチの番号
    s = []; k = [] # s : どのスイッチとつながってるか、インデックスは電球を指す、　k: 電球が何個のスイッチとつながっているか
    for _ in range(m):
        tmp = list(map(int, input().split()))
        s.append(tmp[1:]); k.append(tmp[0])
    p = list(map(int, input().split()))

    res = 0
    # スイッチの状態は２進数表記で表す。スイッチはｎ個あるので
    for bit in range(2**n):
        ok = True
        for i in range(m): # 各電球に対して見ていく
            cnt = 0
            for v in s[i]: # 各電球につながっているスイッチを見てる
                if ( bit & 1 << (v - 1) ): # bitの状態がスイッチvがついてる状態なのかどうか
                    cnt += 1
            if cnt % 2 != p[i]:
                ok = False
        if ok: # okなら全ての電球が付いているということ
            res += 1

    print(res)

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()))
ans=0
for i in range(2**n):
  switch=[0]*n
  cnt_on=0
  for j in range(n):
    if (i>>j)&1:
      switch[j]+=1
  for j in range(m):
    cnt=0
    for k in range(ks[j][0]):
      if switch[ks[j][k+1]-1]==1:
        cnt+=1
    if cnt%2==p[j]:
      cnt_on+=1
  if cnt_on==m:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a,c=[],0
for i in range(m):
    a.append(list(map(int,input().split())))
p=list(map(int,input().split()))
for i in range(2**n):
    i,b='0'*(n-len(bin(i))+2)+bin(i)[2:],0
    for j in range(m):
        f=0
        for k in range(a[j][0]):
            f+=int(i[a[j][k+1]-1])
        if f%2==p[j]:
            b+=1
    if b==m:
        c+=1
print(c)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[list(map(int,input().split()))[1:] for m in range(m)]
p=list(map(int,input().split()))
cnt=0
for i in range(1<<n):
    for j in range(m):
        switch=0
        for k in range(n):
            if (i>>k)&1 and k+1 in s[j]:
                switch+=1
        if switch%2!=p[j]:
            break
    else:
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from itertools import product

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

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

print(cnt)

Submission status: Accepted

Solution code:
import sys
import os
from itertools import combinations

def file_input():
    f = open('ABC128/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    # int(input())
    N,M=map(int, input().split()) #N:switch M:light
    s=[[] for i in range(M)]
    k=[]
    for i in range(M):
        tmp=list(map(int, input().split()))
        k.append(tmp[0])
        s[i]=tmp[1:]
    p=list(map(int, input().split()))

    out=0
    for i in range(N+1):
        for li in combinations(range(N),i):
            # print(li)
            on=0
            for m in range(M):
                tmp=0
                for j in range(k[m]):
                    # print("m:"+str(m)+" k:"+str(j))
                    for c in li:
                        if s[m][j]==c+1:
                            tmp+=1
                if tmp%2==p[m]:
                    on+=1
            if on==M:
                # print(li)
                out+=1

    print(out)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans=0
#全bit
for i in range(1<<n):
    #電球ごと
    every_on=True
    for j in range(m):
        #スイッチごと
        cnt=0
        for u in range(li[j][0]):
            if i>>(li[j][u+1]-1)&1:
                cnt+=1
        if cnt%2!=p[j]:
            every_on=False
    if every_on:
        ans+=1
print(ans)

Submission status: Accepted

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

    kslist.append(list(map(lambda x: int(x)-1, input().split()))[1:])

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


ans = 0

for i in range(1 << N):
    for r in range(M):
        on_sum = 0
        for j in range(N):
            if i >> j & 1 and j in kslist[r]:
                on_sum += 1
        if on_sum % 2 != plist[r]:
            break
    else:
        ans += 1


print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

n,m = map(int,input().split())
s = [[0 for i in range(m)] for i in range(n)]
for i in range(m):
    l = list(map(int,input().split()))
    l.pop(0)
    #print(i)
    for j in l:
        s[j-1][i] = 1
ans = list(map(int,input().split()))
#print(ans)
answer = 0
for i in range(2**n):
    c = [0 for j in range(m)]
    for j in range(n):
        if ((i >> j) & 1):
            for k,l in enumerate(s[j]):
                if l == 1 and c[k] == 1:
                    c[k] = 0
                elif l == 1:
                    c[k] = 1
            #print(c)
            
    if ans == c:
        answer += 1
print(answer)

Submission status: Accepted

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

need = [None] * m
ans = 0

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

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

for i in range(2 ** n):
    zentou = 1
    status = [0] * n

    for j in range(n):
        if ((i >> j) & 1):
            status[j] = 1

    for j in range(m):
        total = 0
        for t in range(1, len(need[j])):
            if status[need[j][t]-1] == 1:
                total += 1
        
        if total%2 != p[j]:
            zentou = 0

    if zentou == 1:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n,m = map(int,(input().split()))
sw =[list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))

ans = 0
for bit in product([0, 1], repeat=n):
    ele = True #全部点灯ならtrue
    for i in range(m): #電球1～mに対するループ
        cnt = 0
        for j in sw[i][1:]: #switch1～nに対するループ
            #print(j)
            cnt += bit[j-1]
        if cnt % 2 != p[i]:
            ele = False
            break
    if ele:
        ans += 1        
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n,m = map(int,(input().split()))
sw =[list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))

ans = 0
for bit in product([0, 1], repeat=n):
    ele = True
    for i in range(m):
        cnt = 0
        for j in sw[i][1:]:
            cnt += bit[j-1]
        if cnt % 2 != p[i]:
            ele = False
            break
    if ele:
        ans += 1        
print(ans)

Submission status: Accepted

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

switch = [[] for i in range(n)]
for i in range(m):
    line = list(map(int, input().split()))
    del line[0]
    for l in line:
        switch[l - 1].append(i)
p = list(map(int, input().split()))

def make_select(m):
    select = []
    i = 0
    def make_bool(m, i):

        if i > m:
            return 0

        for a in itertools.combinations(range(m), i):
            bool = [False] * m
            for b in a:
                bool[b] = True
            select.append(bool)
        
        i += 1
    
        make_bool(m, i)
    
    make_bool(m, i)
    return select
    
select = make_select(n)

ans = 0
for c in select:
    light = [0] * m
    for i in range(n):
        if c[i]:
            for s in switch[i]:
                light[s] ^= 1
    
    if light == p:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

for _ in range(m):
    k, *sss = list(map(int,input().split()))
    swi.append(sss)
ppp = list(map(int,input().split()))

ans = 0
sta = product((0, 1), repeat=n)

for st in sta:
    flg = True
    for i in range(m):
        cnt = 0
        for j in swi[i]:
            if st[j - 1] == 1:
                cnt += 1
        if cnt % 2 != ppp[i]:
            flg = False
    if flg:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(m)]
pm = list(map(int, input().split()))
bit = itertools.product([0, 1], repeat=n)
ans = 0
for b in bit:
    flag = True
    for i in range(m):
        on = 0
        for s in ks[i][1:]:
            if b[s-1] == 1:
                on += 1
        if on % 2 != pm[i]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
A = [list(map(lambda x: int(x)-1, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
for i in range(1<<n):
    for j in range(m):
        cnt = 0
        for k in range(n):
            if ((i>>k) & 1) and k in A[j]: cnt += 1
        if cnt%2!=p[j]: break
    else: ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = []
for _ 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(2**N):
    bi = str(bin(i))[2:]
    bi = bi.zfill(N)
    isAddable = True
    for j in range(M):
        s_sum = 0
        for s in S[j]:
            if bi[s-1] == '1':
                s_sum += 1
        if s_sum % 2 != P[j]:
            isAddable = False
            break
    if isAddable:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

ans = 0
for it in itertools.product([0,1], repeat = n):
    for i, item in enumerate(lst):
        count = 0
        for switch in item:
            if it[switch - 1] == 1:
                count += 1
        if count % 2 != p[i]:
            break
    else:
        ans += 1
print(ans)