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())
s = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
  bit = [i>>j & 1 for j in range(n)]
  for k,x in enumerate(s):
    if p[k] != sum([bit[y-1] for y in x[1:]])%2:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
s = []
for i in range(M):
    dp = [0]*(N)
    k,*tmp = list(map(int,input().split()))
    for j in tmp:dp[j-1]=1
    s.append(dp)
p = list(map(int,input().split()))
ans = 0
for i in range(1<<N):
    tmp = 0
    dp = [0]*M
    for I in range(M):
        for j in range(N):
            t = i>>j&1
            dp[I] += s[I][j] * t
    for e,i in enumerate(dp):
        dp[e] = i%2
    if dp == p:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
#c
n,m = map(int,input().split())
res = 0
q = []
for i in range(m):
    q.append(list(map(int,input().split())))
p = list(map(int,input().split()))

#s(あるm桁のビット列)のX桁目が1ならX個目のスイッチがON
for s in range(2**n):#ビット輩出
    judge = True
    for i in range(m):#各ビット桁を見る
        cnt = 0
        for j in range(1,len(q[i])):#スイッチの状態についてそれぞれ見る
            w = q[i][j]#あるスイッチの状態
            if s>>(w-1) &1 == 1:#スイッチの場所がついていたらカウントする
                cnt += 1
        if cnt % 2 != p[i]:#カウントのあまりがOKかどうか
            judge = False
    if judge:#各ビット桁でfalseが一度も出なかったら
        res += 1
print(res)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
s = []
for i in range(M):
    dp = [0]*(N)
    tmp = list(map(int,input().split()))
    for j in tmp[1:]:dp[j-1]=1
    s.append(dp)
p = list(map(int,input().split()))
ans = 0
for i in range(1<<N):
    tmp = 0
    dp = [0]*M
    for I in range(M):
        for j in range(N):
            t = i>>j&1
            dp[I] += s[I][j] * t
    for e,i in enumerate(dp):
        dp[e] = i%2
    if dp == p:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np


def main():
    N, M = list(map(int, input().split(' ')))
    con = np.zeros((M, N))
    for i in range(M):
        row = np.array(list(map(int, input().split(' '))))
        switch_indices = row[1:] - 1
        con[i, switch_indices] = 1
    p = np.array(list(map(int, input().split(' '))))
    switches = itertools.product([0, 1], repeat=N)
    answer = 0
    for s in switches:
        lamp = np.dot(con, np.array(s)) % 2
        all_on = np.count_nonzero(lamp - p) == 0
        if all_on:
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
n,m=map(int,input().split())
swichList = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
ans = 0

for bit in range(1<<n):#スイッチの付き方を全探索する
    onswichlist = deque()
    for i in range(n):#こちらはnこの要素に対して参照していくため0~nで動いていく
        if bit & (1<<i):#bit(eg 011001)のi桁目が1ならばリストのi番目を処理する
            onswichlist.append(i+1)#onスイッチの番号をリスト化
    for j in range(m):
        cnt = 0
        for k in onswichlist:
            if k in swichList[j][1:m+1]:#onスイッチがj番目のライトにつながっているか
                cnt += 1
        if cnt%2 != p[j]:#onスイッチがj番目のライトを点灯させる条件がそろっていなければbreak
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
comb = ["0"*(N-len(format(i,"b")))+format(i,"b") for i in range(2**N)]
result = 0
setting = list()
for i in range(M):
    temp = (list(map(int,input().split())))
    setting.append(temp[1:len(temp)])
p = list(map(int,input().split()))
for i in comb:
    light = [0]*M
    for j in range(len(setting)):
        on_count = 0
        for k in setting[j]:
            if i[k-1] =="1":
                on_count +=1
        if on_count %2 == p[j]:
            light[j] = 1   
    if sum(light) == M:
        result +=1
        
    
print(result)

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
bit=[]
for i in range(2**n):
    h=[0]*n
    for j in range(n):
        if (i>>j & 1):
            h[j]=1
    bit.append(h)

check=[list(map(int,input().split(" "))) for i in range(m)] 
p=list(map(int,input().split()))

ans=0
sum=0
amari=[]
for k in range(len(bit)):
    for i in range(m):
        for j in range(1,len(check[i])):
            sum=sum+bit[k][check[i][j]-1]
        amari.append(sum%2)
        sum=0
    if p==amari:
      ans=ans+1
    amari=[]
    
        

print(ans)

Submission status: Accepted

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

for i in range(1<<n):
  flag = 0
  for j,L in enumerate(Line):
    count=0
    for l in L:
      if i&(1<<(l-1)):
        count+=1
    if count % 2 == P[j]:
      flag += 1
  if flag == m:
    ans += 1
print(ans)

Submission status: Accepted

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


ans=0
for i in range(2**n):
    bi = bin(i)[2:].zfill(n)
    if all( sum(int(bi[sss-1]) for sss in ss )%2 == p[j] for j,ss in enumerate(s) ):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0
for t in product([0, 1], repeat=N):
    flag = 0
    j = 0
    for ks_j in ks:
        trial = 0
        for s_i in ks_j[1:]:
            trial += t[s_i-1]
        trial += p[j]
        if trial % 2 != 0:
            flag = 1
            break
        j += 1
    if flag == 0:
        ans += 1
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()))
lng = 0
for i in range(2**n):
  oz = [0]*n
  for j in range(n):
    if (i>>j)&1:
      oz[j]=1
  for t in range(m):
    count = 0
    for j in range(len(ks[t])):
      if j != 0:
        count += oz[ks[t][j]-1]
    if count % 2 != p[t]:
      break
  else:
    lng += 1
print(lng)

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)

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

count = 0
for i in range(2**N):
    switch = []
    for j in range(N):
        if ((i >> j) & 1):
            switch.append(j+1)
    #print(switch)
    c = 0
    for m in range(M):
        S_ = S[m]
        c_ = 0
        for s_ in range(1, S_[0]+1):
            if S_[s_] in switch:
                c_ += 1
        if c_ % 2 == P[m]:
            c += 1
    if c == M:
        count += 1

print(count)

Submission status: Accepted

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

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

Ans = 0

for i in range(2**N):
    switchs = []
    su = 0
    for j in range(N):
        if ((i >> j) & 1):
            switchs.append(j+1)
    for k in range(M):
        count = len(set(switchs)&set(ks[k][1:]))
        if count % 2 == p[k]:
            su += 1
    if su == M:
        Ans += 1
print(Ans)

Submission status: Accepted

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

ans = 0
for bits in product(range(2), repeat=n):
    match = 0 # How many matches with the condition p?
    for num, tmp in enumerate(ks):
        k = tmp[0]
        switch = tmp[1:]
        total = sum(map(lambda x: bits[x-1], switch))
        if total % 2 == p[num]:
            match += 1
    if match == len(p):
        ans += 1
    match = 0

print(ans)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split(' ')))
ksm = [None] * m
for i in range(m):
    ksm[i] = list(map(int, input().split(' ')))[1:]


pm = list(map(int, input().split(' ')))

count = 0
for i in range(2 ** n):
    ok = True
    for j in range(m):
        val = 0
        for k in range(n):
            if (i >> k) & 1 and (k + 1) in ksm[j]:
                val += 1
        if val % 2 != pm[j]:
            ok = False
            break
    if ok:
        count += 1
        
print(count)

Submission status: Accepted

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

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


def is_light_on(values):
    for i in range(M):
        count = 0
        for s in Ks[i]:
            if values[s-1] == 'on':
                count += 1
        if count % 2 != Ps[i]:
            return 0

    return 1


def search(depth, values):
    global ans
    if depth == N:
        ans += is_light_on(values)
    else:
        search(depth=depth+1, values=values+['on'])
        search(depth=depth+1, values=values+['off'])


ans = 0
search(depth=0, values=[])
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
k = [0 for _ in range(m)]
s = [[] for _ in range(m)]

for i in range(m):
    x = list(map(int,input().split()))
    k[i] = x[0]
    s[i] = x[1:]
p = list(map(int,input().split()))
t = 0
for i in range(2**n):
    for j in range(m):
        x = 0
        for y in s[j]:
            if(i & 2**(y-1)):x += 1
        if(x%2 != p[j]):break
    else:
        t += 1
print(t)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
cnt = 0
K = list()
L = list()
for m in range(M):
    l = list(map(int, input().split()))
    k = l.pop(0)
    K.append(k)
    L.append(l)
P = list(map(int, input().split()))

for i in range(2**N):
    flag = True
    for j in range(M):
        c = 0
        for l in range(K[j]):
            if (i >> L[j][l]-1) & 1:
                c += 1
        if c % 2 != P[j]:
            flag = False
    if flag:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# C - Switches

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

ans = 0
for i in range(2**N):
    # flg:一つでも電球が点灯しない場合はFalse
    flg = True
    for j in range(M):
        # cnt:電球ごとのスイッチONの数
        cnt = 0
        for k in range(ks[j][0]):
            if i>>(ks[j][k+1]-1)&1:
                cnt += 1
        if p[j]!=(cnt%2):
            flg = False
    if flg == True:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    cs = []
    for _ in range(m):
        tmpl = list(map(int, input().split()))
        tmpl.pop(0)
        cs.append(set(tmpl))
    p = list(map(int, input().split()))

    r = 0
    for bit in range(1 << n):
        each_p = set()
        for i in range(n):
            mask = 1 << i
            if bit & mask:
                each_p.add(i+1)
        check = []
        for i2 in range(m):
            check.append(len(each_p.intersection(cs[i2])) % 2 == p[i2])
        r += all(check)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
k = []
s_list = []
for _ in range(M):
  tmp = list(map(int, input().split()))
  k.append(tmp[0])
  s_list.append(tmp[1:])
p = list(map(int, input().split()))
ans = 0
for i in range(2**N):
  flag = True
  for j in range(M):
    tmp = 0
    for l in range(k[j]):
      if (i >> s_list[j][l]-1) & 1:
        tmp += 1
    if tmp%2 != p[j]:
      flag = False
      break
  if flag:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,M = list(map(int,input().split()))
K = []
for i in range(M):
    A = list(map(int,input().split()))
    K.append(A)
p = list(map(int,input().split()))
ans = 0
for i in range(1 << N):
    f = True
    for j in range(M):
        s = 0
        for k in K[j][1:]:
            s += (i >> (k - 1)) & 1
        if s % 2 != p[j]:
            f = False
    if f:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
k = []
s_list = []
for _ in range(M):
  tmp = list(map(int, input().split()))
  k.append(tmp[0])
  s_list.append(tmp[1:])
p = list(map(int, input().split()))
ans = 0
for bit in itertools.product([0, 1], repeat=N):
  flag = True
  for i in range(M):
    tmp = 0
    for j in range(k[i]):
      if bit[s_list[i][j]-1] == 1:
        tmp += 1
    if tmp%2 != p[i]:
      flag = False
      break
  if flag:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
B = [None] * M
for i in range(M):
    ks = list(map(int, input().split()))
    B[i] = [s - 1 for s in ks[1:]]
p = list(map(int, input().split()))

ans = 0
bit = 0
for bit in range(1 << N):
    for i, b in enumerate(B):
        if p[i] != (len([1 for s in b if bit & (1 << s)]) % 2):
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

cnt = 0
for i in range(2 ** N):  # bit全探索
    for idx, s in enumerate(S_LIST):  # ライト
        n_on = 0
        for k in s:  # スイッチonの個数数える
            if ((i >> (N - k)) & 1):
                n_on += 1
        if (n_on % 2 != P_LIST[idx]):  # 点灯しているかどうか
            break
        if (idx == M - 1):
            cnt += 1  # 全点灯
print(cnt)

Submission status: Accepted

Solution code:

def main():
  # N: スイッチの数
  # M: 電球の数
  N,M = list(map(int, input().split()))

  ans = 0

  # 電球i番目と関連するスイッチ番号を対応させるための配列を作る
  s = [[] for i in range(M)]

  # 電球とスイッチの対応を行う処理
  for i in range(M):
    row = list(map(int, input().split()))
    k = row[0]

    for j in range(1, k+1):
      # i 番目の電球にツナっがっている、スイッチ番号を配列に突っ込んでいく
      s[i].append(row[j] - 1)

  # 電球が光る条件
  # 電球に対応するスイッチがON担っている数を2で割ってあまりがpiと同じなら電球はついている
  p = list(map(int, input().split()))

  # スイッチのON/OFFパターン全探索
  for i in range(1 << N):
    ok = True

    for j in range(M):
      count = 0

      #j番目のスイッチがついているかどうかを確認する
      for value in s[j]:
        if(i >> value & 1):
          count += 1

      if(count % 2 != p[j]):
        ok = False

    if(ok):
      ans += 1

  print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

l = [[int(i) for i in input().split()][1:] for _ in range(m)]

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

ans = 0
for i in range(1<<n):
    check = [0 for _ in range(m)]
    for idx,j in enumerate(l):
        ct = 0
        for k in j:
            if (i >> k-1) & 1:
                ct += 1
        
        if ct % 2 == p[idx]:check[idx] = 1
        
    if all(check):
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
# n = int(input())
# b = list(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(1<<n):
    lcnt=0
    for j in range(m):
        # k = l[j][0]

        s = l[j][1:]
        scnt=0
        for x in s:
            x -= 1
            if(i>>x)&1 == 1:
                scnt+=1

        if scnt%2 == p[j]:
            lcnt+=1
            continue
        elif scnt%2 >0 and p[j] ==1:
            lcnt+=1
            continue

    if lcnt== m:
        ans+=1
        
print(ans)

Submission status: Accepted

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


def check(bits, i):
    on = 0
    for x in S[i]:
        if (bits >> x) & 1:
            on += 1
    return on & 1 == P[i]


ans = 0
for bits in range(1 << N):
    flag = True
    for i in range(M):
        # 電球iが点灯するか
        # print(bits, i, check(bits, i))
        if not check(bits, i):
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

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

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

ans = 0
# bit全探索
for i in range(2 ** n):
    flg = True
    # 全パターンの電球について
    for p in range(m):
        switched = 0
        # bit全探索　各スイッチを調べる
        for j in range(n):
            if (i >> j) & 1:
                if (j + 1) in patterns[p][1:]:
                    switched += 1
        if not (switched % 2) == correct[p]:
            flg = False
            break
    if flg is True:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# import itertools
# import pprint

sw,lb  = map(int,input().split())
swbit  = [0]*sw
ans,p  = 0,0

for i in range(lb):
  li  = list(map(int,input().split()))
  num = li.pop(0)

  for j in li:
    swbit[j-1] |= 0b1 << i

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

for i in range(lb):
  p |= plist[i] << i

for i in range(0b1<<sw):
  
  status = 0

  for j in range(sw):
    if (i >> j) & 1 :
      status ^= swbit[j]
  
  if p == status:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product


N, M = map(int, input().split())
km = []
sm = []
pm = []
for m in range(M):
  tmp = list(map(int, input().split()))
  km.append(tmp[0])
  sm.append(tmp[1:])
pm = list(map(int, input().split()))
prod = list(product([1,0], repeat=N))

ans = 0

for p in prod:
  on = [0] * M
  for m in range(M):
    sw_num = 0
    for es in sm[m]:
      sw_num += p[es-1]
    if sw_num%2 == pm[m]:
      on[m] = 1
  if sum(on) == M:
    ans += 1
print(ans)

Submission status: Accepted

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

# 各行のスイッチ
switches_list = []
for i in range(M):
    line = input().split()
    switch_count = int(line[0])
    switches = [0] * N
    for j in range(switch_count):
        switches[int(line[j + 1]) - 1] = 1
    switches_list.append(switches)
# print(switches_list)

# 余り
surpluses = input().split()

count = 0
for k in range(2 ** N):
    for i in range(len(switches_list)):
        switches = switches_list[i]
        surplus = int(surpluses[i])
        on_count = 0
        for j in range(len(switches)):
            if switches[j] == 1 and ((k >> j) & 1):
                on_count += 1
        if on_count % 2 != surplus:
            break
        # 全電球分のチェックを通ったらOKとする
        if i == len(switches_list) - 1:
            count += 1
print(count)

Submission status: Accepted

Solution code:
def test(array: list, array_list: list, N: int):
    if len(array) == N:
        array_list.append(array)
        return
    new_array = array[:]
    new_array.append(0)
    array.append(1)
    test(new_array, array_list, N)
    test(array, array_list, N)


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

# 組み合わせ作成
array_list = []
array = []
test(array, array_list, N)

# 各行のスイッチ
switches_list = []
for i in range(M):
    line = input().split()
    switch_count = int(line[0])
    switches = [0] * N
    for j in range(switch_count):
        switches[int(line[j + 1]) - 1] = 1
    switches_list.append(switches)
# print(switches_list)

# 余り
surpluses = input().split()

count = 0
for array in array_list:
    for i in range(len(switches_list)):
        switches = switches_list[i]
        surplus = int(surpluses[i])
        on_count = 0
        for j in range(len(switches)):
            if switches[j] == 1 and array[j] == 1:
                on_count += 1
        if on_count % 2 != surplus:
            break
        # 全電球分のチェックを通ったらOKとする
        if i == len(switches_list) - 1:
            count += 1
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, m = map(int, input().split())
s = [list(map(int, input().split()[1:])) for _ in range(m)]
p = list(map(int, input().split()))
c = 0

from itertools import product
for i in product([0,1], repeat=n):
    if all(
        len([None for t in t if i[t-1]]) % 2 == p[j] for j, t in enumerate(s)
    ):
        c += 1
print(c)

Submission status: Accepted

Solution code:
from sys import stdin

if __name__ == "__main__":
  N, M = [int(i) for i in input().split()]
  K = []
  S = []
  for i in range(M):
    line = input().split()
    K.append(int(line[0]))
    S.append(set(int(item) for item in line[1:]))
    
  P = [int(i) for i in input().split()]
  
  cnt = 0
  for i in range(2**N):
    on_switches = set()
    for j in range(N):
      if i >> j & 1:
        on_switches.add(j+1)
    
    is_light_on = []
    for m, light_switches in enumerate(S):
      total_switch = len(light_switches & on_switches)
      is_light_on.append(total_switch % 2 == P[m])
    if all(is_light_on):
      cnt += 1
  
  print(cnt)

Submission status: Accepted

Solution code:

import itertools

n,m=map(int,input().split())
ks=[]
for i in range(m):
    ksi=list(map(int,input().split()))
    ks.append(ksi)
p=list(map(int,input().split()))
    
icnt=0
for i in itertools.product([0,1], repeat=n):
    yn=""
    mcnt=0
    for j in range(m):
        ksum=0
        for k in range(ks[j][0]):
            if i[ks[j][k+1]-1]==1:
                ksum+=1
        if ksum%2==p[j]:
            mcnt+=1
    if mcnt==m:
        icnt+=1
#    print(icnt,mcnt,i)
print(icnt)

Submission status: Accepted

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

ans = 0
for bit in range(1 << n):

    S = []
    for i in range(n):
        if bit & (1 << i):
            S.append(i)

    on = 0
    for i in range(m):
        c = 0
        for j in S:
            if ((j + 1) in s[i]):
                c += 1
        if c % 2 == p[i]:
            on += 1

    if on == m:
        ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
for bit in range(1 << n):

    S = []
    for i in range(n):
        if bit & (1 << i):
            S.append(i)

    on = 0
    for j in range(m):
        c = 0
        for l in S:
            if ((l + 1) in s[j]):
                c += 1
        if c % 2 == p[j]:
            on += 1

    if on == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

def main():
    N, M = map(int, readline().split())
    s = []
    for _ in range(M):
        k, *stmp = map(int, readline().split())
        s.append(set(stmp))
    p = list(map(int, readline().split()))

    ans = 0
    for i in range(2**N):
        flag = True
        onset = []
        for j in range(N):
            if (i>>j) & 1:
                onset.append(j+1)
        onset = set(onset)
        for m in range(M):
            union = onset & s[m]
            if len(union) % 2 != p[m]:
                flag = False
                break

        if flag:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

candidate = [[0], [1]]
while True:
    temp = []
    for c in candidate:
        for v in [0, 1]:
            temp.append(c + [v])
    candidate = temp
    if len(temp[0]) == N:
        break

ans = 0
for c in candidate:
    flag = True
    for i, switch in enumerate(k):
        hoge = 0
        for s in switch[1:]:
            hoge += c[s-1]
        flag = flag and (hoge % 2 == p[i])
    if flag:
        ans += 1


print(ans)

Submission status: Accepted

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

s_list = list()

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

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

s_mask = list()
for ss in s_list:
    s_bits = 0
    for s in ss:
        s_bits = (s_bits | (1 << (s-1)))
    s_mask.append(s_bits)
        
#print(s_list)
#for m in s_mask:
#    print(bin(m))
find_cnt = 0
for i in range(2 ** N):
    ng_flg = 0
    for k in range(M):
        sum_bits = i & s_mask[k]
        bit_cnt=0
        for kk in range(N):
            bit_cnt = bit_cnt + (sum_bits >> kk)

        #print(k, bin(sum_bits), bit_cnt)
        if bit_cnt % 2 != p_list[k]:
            ng_flg = ng_flg + 1
    
    if ng_flg == 0:
        find_cnt = find_cnt + 1
    #print(s_sum)

print(find_cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]
t = list(map(int,input().split()))
ans = 0
for i in range(2**n):
  bit = [i>>j & 1 for j in range(n)]
  for k,x in enumerate(s):
    if t[k] != sum([bit[y-1] for y in x[1:]])%2:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n,m = map(int,input().split())
on_list = [[0 for i in range(m)]for i in range(n)]
off_list = [[0 for i in range(m)]for i in range(n)]
for i in range(m):
    tmp = list(map(int,input().split()))
    for j in range(1,len(tmp)):
        on_list[tmp[j]-1][i] = 1
        

p_list = list(map(int,input().split()))
on_list = np.array(on_list)
off_list = np.array(off_list)


cnt = 0
for i in range(2**n):
    tmp = np.zeros((m),dtype  =int)
    for j in range(n):
        if ((i >> j)& 1):
            tmp += on_list[j]
        else:
            tmp += off_list[j]
    flag = True
    for i in range(len(tmp)):
        if p_list[i] == tmp[i]%2:
            continue
        else:
            flag = False
    if flag:
        cnt += 1
print(cnt)

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()))
ct = 0
for i in range(2 ** n):
    sw = [0] * n
    on = [False] * m
    for j in range(n):
        if((i >> j) & 1):
            sw[j] = 1
    for k in range(m):
        tmp = 0
        for l in range(1, len(S[k])):
            if sw[S[k][l] - 1] == 1:
                tmp += 1
        if tmp % 2 == P[k]:
            on[k] = True
    if False not in on:
        ct += 1
print(ct)

Submission status: Accepted

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

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

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


cnt=0

for i in range(2**N):
    Ans=[0]*M
    i = format(i,'0{}b'.format(N))

    for k in range(M):
        light_num=0
        for n in SwitchCond[k]:
            if i[n-1]=='1':
                light_num+=1
        
        if light_num%2==Lights[k]:
            Ans[k]=1
    
    if sum(Ans)==M:
        cnt+=1

print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
switch = [(i+1) for i in range(n)]
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):
    on = []
    light = 0
    for j in range(n):
        if ((i >> j) & 1) == 1:
            on.append(switch[j])
    for k in range(m):
        count = 0
        for l in range(1,ks[k][0]+1):
            if ks[k][l] in on:
                count += 1
        if count % 2 == p[k]:
            light += 1
    if light == m:
        ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

for i in itertools.product([0,1],repeat=N):
    ok=True
    for j in range(M):
        j_on_cnt=0
        for k in sw[j][1:]:
            j_on_cnt+=i[k-1]
        if j_on_cnt%2!=p[j]:
            ok=False
            break
    if ok:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

for i in itertools.product([0,1],repeat=N):#i...スイッチの状態一覧
    onof=True

    for j in range(M):#j...電球の番号
        j_on_cnt=0#電球jに対するonスイッチの個数
    
        for k in sw[j][1:]:
            j_on_cnt+=i[k-1]
            
        if j_on_cnt%2!=p[j]:#電球jがonかoffなのかを調べる
            onof=False
            break
    if onof:
        ans+=1
        
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

for i in itertools.product([0,1],repeat=N):
    onof=True
    #print(i)
    for j in range(M):
        counter=0
        #print(j)
        #print()
        for k in sw[j][1:]:
            counter+=i[k-1]
            #print(k)
        #print()
        
        if counter%2!=p[j]:
            onof=False
            break
    if onof:
        ans+=1
print(ans)