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:
# スイッチONとOFFで、電球と繋がっている繋がっていないも、0or1なので、ビット演算を使用するのが吉

# スイッチと電球の繋がりをビット列で表す
# スイッチ(行）と電球(列)のマトリクスを作って、繋がっているところに1、繋がっていないところに0
# 行方向に見るとスイッチがどの電球に繋がっているかのビット列ができる
# intで持ってもよいので、100 は　4　

# 電球が点いているか点いていないかをビット列で表す
# スイッチを押すたびに、1つ前のスイッチが繋がっている電球にそのスイッチも繋がっていれば、偶奇が変化してスイッチの点滅が変化する
# スイッチを押すたびにxorをとる
# 電球の点滅とpが一致していればok


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

# kはスイッチ、sはスイッチが繋がっている電球を表す
k = []
s = []

for _ in range(m):
    tmp = tuple(map(int, input().split()))
    k.append(tmp[0])
    s.append(set(tmp[1:tmp[0] + 1]))
 
p = tuple(map(int, input().split()))
 
# print(k, s, p, sep="\n")

ans = 0

# スイッチの押し方を全部試す
for i in range(2 ** n):
    # 各iでonになっている電球の数
    light_on = 0
 
    # 電球jについて
    for j in range(m):
        switch_on = 0
 
        for k in range(n):
            # onになっているスイッチ（kビット目が立っているか）
            if (i >> k) & 1:
                # 電球jとつながっているものならカウント
                # sはスイッチkが繋がっている電球jのリスト
                # スイッチは1からなので、k+1
                if k + 1 in s[j]:
                    switch_on += 1
 
        # onになっているスイッチの個数がp[j]に等しいなら電球jは点灯している
        if switch_on % 2 == p[j]:
            light_on += 1
 
    # 全ての電球が点灯しているならカウント
    if light_on == m:
        # print(bin(i))
        ans += 1
 
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
bulbs = []
for _ in range(M):
  bulbs.append(list(map(int,input().split())))
P = list(map(int,input().split()))
res = 0
for i in range(1<<N):
  on = []
  for j in range(N):
    if (i>>j)&1:
      on.append(j)

  ok = True
  for i,b in enumerate(bulbs):
    b = [ k-1 for k in b[1:] ]
    p = P[i]
    o = 0
    for s in on:
      if s in b: o += 1
    if o%2 != p:
      ok = False
      break

  if ok:
    res += 1

print(res)

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
# 2択
for i in range(0,1<<n):
    cnt = [0]*m
    for j in range(n):
        if (i>>j)&1:
            for k in range(m):
                if j + 1 in ks[k][1:]:
                    cnt[k] += 1

    temp = 0
    for i in range(m):
        if cnt[i] % 2 == p[i]:
            temp += 1
    if temp == m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
input = lambda: sys.stdin.readline().rstrip()


def solve():
    N, M = map(int, input().split())
    ks = [[] for _ in range(M)]
    for i in range(M):
        k, *s = map(int, input().split())
        ks[i] = list(s)
    p = list(map(int, input().split()))
    comb = itertools.product([0, 1], repeat=N)

    ans = 0
    for c in comb:
        f = True
        for i in range(M):
            count = 0
            for j in ks[i]:
                count += c[j - 1]
            if count % 2 != p[i]:
                f = False
                break
        if f:
            ans += 1

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import itertools
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

ans = 0
for t in itertools.product([0, 1], repeat=n):
    t = list(t)
    bl = True
    for i in range(m):
        cnt = 0
        for j in k[i][1::]:
            cnt += t[j - 1]
        if cnt % 2 != p[i]:
            bl = False
    if bl:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    q = [list(map(int, input().split())) for _ in range(m)]
    p = list(map(int, input().split()))

    ans = 0
    for i in range(1 << n):
        check = True
        for j in range(m):
            ki = q[j][0]
            tmp_c = 0
            for k in range(1, ki + 1):
                if i & (1 << (q[j][k] - 1)):
                    tmp_c += 1
            if tmp_c % 2 != p[j]:
                check = False
                break
        if check:
            ans += 1
    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

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

ans = 0

for i in range(2**N):
    count = [0]*M
    for j in range(N) :
        if (i>>j)&1 == 1 :
            for k in range(M) :
                if j+1 in s[k][1:] :
                    count[k] += 1
    count = [i%2 for i in count]
    if count == p :
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for i in product([0,1],repeat=n):
    ac = True
    for k,b in enumerate(lamp):
        tmp = 0
        for a in b[1:]:
            tmp += i[a-1]
        if p[k] != tmp%2:
            ac = False
            break
    if ac:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m =map(int,input().split())
s = [list(map(int, input().split())) for _ in range(m)]
#s[i][0]はkです
p = list(map(int, input().split()))
ans = 0
for _ in range(m):
  del s[_][0]

for i in range(2 ** n): #すいっち全探索
  on = [0]*m
  for j in range(n):
    if ((i>>j)&1): #もしj桁めが1なら
      for __ in range(m):
        if (j+1) in s[__]:
          on[__] += 1
  for _ in range(m):
    on[_] %= 2
  if p == on:
    ans += 1
print(ans)

Submission status: Accepted

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

k = []
p = []
swt = []
result = 0

for num in range(N):
    swt.append(0)

for num in range(M):
    k.append(list(map(int,input().split())))

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

#print(k)
#print(p)

for i in range(2**N):
    for j in range(N):
        if(i&(1<<j)):
            swt[j] = 1

    #print(i,swt)
    for l1 in range(M):
        count = 0
        for l2 in range(k[l1][0]):
            count += swt[k[l1][l2+1]-1]

        if count%2 != p[l1]:
            for num in range(N):
                swt[num]=0
            break
        if l1==M-1:
            result +=1
            for num in range(N):
                swt[num]=0
print(result)

Submission status: Accepted

Solution code:
n, m = list(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()))

count = 0

for i in range(1<<n):
  tmp = [0] * m
  for j in range(n):
    if i & (1<<j):
      for k in range(m):
        if j+1 in s[k]:
          tmp[k] += 1
  c = 0
  for i in range(m):
    if tmp[i] % 2 == p[i]:
      c += 1
  if c == m:
    count += 1

print(count)

Submission status: Accepted

Solution code:


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

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

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

#print(s)

count = 0
for i in range(2**N):
    b = bin(i)[2:][::-1]
    switch = []
    for j in range(len(b)):
        if b[j] == "1":
            switch.append(j+1)
    #print(switch)
    
    f = 0
    for j in range(M):
        AND = len(list(set(switch) & set(s[j])))
        #print(AND, s[j])
        if (AND % 2 == p[j]):
            f += 1
    #print(f)
    if f == M:
        count += 1
    
                
    
    

print(count)

Submission status: Accepted

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

button=[0]*N
lit=[0]*M
x=pow(2,N)
total=0
for i in range(x):
    for j in range(N):
        if (i>>j)&1:
            button[j]=1
        else:
            button[j]=0
    for j in range(M):
        for k in range(1,ks[j][0]+1):
            if button[ks[j][k]-1]:
                lit[j]+=1
    count=0
    for j in range(M):
        if lit[j]&1==p[j]:
            count+=1
    if count==M:
        total+=1
    for j in range(M):
        lit[j]=0
print(total)

Submission status: Accepted

Solution code:
def main():
    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):
        a = []
        flag = True
        for j in range(n):
            a .append(i>>j & 1)
        ok = 0
        for j in range(m):
            switch = 0
            for s in ks[j][1:]:
                switch += a[s - 1]
            if switch % 2 != p[j]:
                flag = False
        if flag:
            ans +=1
            
    print(ans)
                
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#ABC128C
def main():
    import sys, itertools as ite
    N, M = map(int, sys.stdin.readline().split())
    KS = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
    P = tuple(map(int, sys.stdin.readline().split()))
    
    #print(KS)
    #bit全探索
    SWS = tuple(ite.product([0,1], repeat=N)) 
    
    def judge(on_off):
        for i in range(M):
            on_cnt = 0
            for s in KS[i][1:]:
                on_cnt += on_off[s-1]
            if on_cnt %2 !=P[i]:
                return 0
        else:
            return 1
    ans = 0
    for on_off in SWS:
        ans +=judge(on_off)
    print(ans)






if __name__=='__main__':
    main()

Submission status: Accepted

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

ans = 0
for ptn in range(2**N):
    lamp = [False]*M
    for i in range(M):
        cnt = 0
        for j in range(k[i]):
            if (ptn>>(s[i][j]-1))&1:
                cnt += 1
        if cnt % 2 == p[i]:
            lamp[i] = True
    if all(lamp):
        ans += 1

print(ans)

Submission status: Accepted

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

res=0
for bit in range(2**n):
  for i in range(m):
    cnt=0
    for sw in s[i]:
      if (bit >> (sw-1) & 1):
        cnt += 1
    if cnt % 2 != p[i]:
      break
  else:
    res+=1
print(res)

Submission status: Accepted

Solution code:
def main():
    N,M = map(int, input().split())
    s = [[int(x) for x in input().split()][1:] for _ in range(M)]
    p = [int(x) for x in input().split()]
    count=0
    for i in range(2**N):
        switch=[0]*N
        sw = bin(i)[2:]
        sw = "0"*(N-len(sw))+sw
        #print(sw)
        #for j in range(N):
            #switch[j] = int(sw[j])
        All=0   
        for j in range(M):
            Sum=0
            for k in s[j]:
                #if switch[k-1]==1:
                if int(sw[k-1])==1:
                    Sum+=1
            if Sum%2 == p[j]:
                All+=1
        if All==M:
            count+=1
    print(count)

main()

Submission status: Accepted

Solution code:
def main():
    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()))
    res = 0
    for i in range(2**n):
        # a = [0] * n
        # ランプごとにスイッチとつながっているか l：ランプindex
        for l in range(m):
            s_on = 0
            for j in range(n): # j;スイッチリスト
                # スイッチ入ってる かつ ランプがつながっているかlampsはつながっているスイッチリスト
                if(i >> j) & 1 and j in lamps[l]:
                    s_on += 1
            if s_on % 2 != p[l]:
                break
        # ランプ全てにおいて、ifの条件以外だったら
        else:
            res += 1
    print(res)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m =map(int, input().split())
from itertools import product
s = [0,1]
ptns = sorted(list(product(s, repeat=n)), reverse=1)
#print(ptns)
lis=[]
for _ in range(m):
  tmp=list(map(int, input().split()))
  lis.append(tmp[1:])
#print(lis)
cnt=0
check=0
rem=list(map(int, input().split()))
for i in ptns:# パターンを全部チェックするループ
  for s in range(m): #s-1番目の電球 をチェックしています
    check=0
    for t in lis[s]: #電球のつながっているスイッチを一個ずつチェック
      if i[t-1]==1:
        check+=1
    if check%2!=rem[s]:
      break
    else:
      continue
    break
  else:
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, M = map(int, readline().split())
k = []
for i in range(M):
  swich = list(map(int,readline().split()))
  swich.pop(0)
  k.append(swich)
p = list(map(int,readline().split()))
count = 0
for bit in range(1 << N):
  ans = []
  for i in range(N):
    if (bit >> i) & 1:
      ans.append(i+1)
  for j in range(M):
    check = sum(1 for s in k[j] if s in ans)
    if check % 2 != p[j]:
      break
    if j == M-1:
      count+=1
print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s = []
for _ in range(M):
    _, *si = map(int, input().split())
    s += [si]
p = list(map(int, input().split()))

ans = 0
for b in range(1 << N):
    for i in range(M):
        on = 0
        for j in range(N):
            if j + 1 not in s[i]:
                continue
            if b & (1 << j):
                on += 1
        if on % 2 != p[i]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

ans=0
for i in range(2**N):
    ls = [1]*N
    for j in range(len(ls)):
        if (i >> j) & 1:
            ls[j] = 0
    count2=0
    count3=0
    for line in K:
        i=1
        count1=0
        while i<len(line):
            if ls[line[i]-1]==1:
                count1+=1
            i+=1
        if count1%2==P[count3]:
            count2+=1
        count3+=1
    ans+=1*(count2==M)


print(ans)

Submission status: Accepted

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

def solve():
    n, m = map(int,input().split())
    #print(n,m)
    swi = []
    for i in range(m):
        li = list(map(int,input().split()))
        a = 0
        for j in range(1,li[0]+1):
            a += 1 << li[j]-1
        swi.append(a)
    p = list(map(int,input().split()))
    ans = 0
    for i in range(1 << n):
        for j in range(m):
            a = i & swi[j]
            if p[j] != bin(a).count("1")%2:
                break
        else:
            ans += 1
    print(ans)
        
"""
    print(swi)
    print(p)
"""
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = [0]*m
for i in range(m):
    s[i] = list(map(int,input().split()))
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    sw = [0]*m
    for j in range(m):
        num = 0
        for k in range(n):
            if (i>>k)&1:
                if k+1 in s[j][1:]:
                    num += 1
        if num%2 == p[j]:
            sw[j] = 1
    if 0 in sw:
        pass
    else:
        ans += 1
print(ans)

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()))
count=0
for i in range(1<<N):
    for m in range(M):
        switch=0
        for j in range(N):
            if (i>>j)&1 and j+1 in s[m]:
                switch+=1
        if switch%2!=p[m]:
            break
    else:
        count+=1
print(count)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
X = []
for _ in range(m):
  k, *A = list(map(int,input().split()))
  b = 0
  for a in A:
    b += 1 << (a-1)
  X.append(b)
P = list(map(int,input().split()))

ans = 0
for i in range(1<<n):
  for x, p in zip(X,P):
    y = i & x
    c = bin(y).count("1") % 2
    if c != p:
      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()))

ans = 0
for i in range(2**N):
    lamp=0
    for j in range(M):
        switch = 0
        for k in s[j]:
            k-=1
            if i&(1<<k):
                switch^=1
        if switch == p[j]:
            lamp+=1
    if lamp==M:
        ans+=1
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import numpy as np

n, m = map(int, input().split())
x = np.array([[0]*(n+1) for i in range(m)])
for i in range(m):
    a = list(map(int, input().split()))
    x[i, 0:(a[0]+1)] = a
    
p = list(map(int, input().split()))
ans = 0

for i in range(2**n):
    switch = []
    counter = 1
    for j in range(n):
        if (i>>j & 1):
            switch.append(j+1)


    for l in range(m):
        set_switch = set(switch) & set(x[l,1:])
        if len(set_switch) % 2 == p[l]:
            counter *= 1
        else:
            counter *= 0
    ans += counter
print(ans)

Submission status: Accepted

Solution code:
def solve(N, M, K, S, P):
    ret = 0
    for i in range(pow(2, N)):
        turned_on_switches = []
        for j in range(N):
            if i >> j & 1:
                turned_on_switches.append(j)
        for k in range(M):
            kth_turned_on_lights_num = 0
            for s in S[k]:
                kth_turned_on_lights_num += 1 if s - 1 in turned_on_switches else 0
            if kth_turned_on_lights_num % 2 != P[k]:
                break
        else:
            ret += 1
    print(ret)

if __name__ == "__main__":
    N, M = map(int, input().split())
    K = []
    S = []
    for _ in range(M):
        tmp = list(map(int, input().split()))
        K.append(tmp[0])
        S.append(tmp[1:])
    P = list(map(int, input().split()))
    solve(N, M, K, S, P)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
switch = [[]for i in range(0,N+1,1)]
for i in range(0,M,1):
    lamp = list(map(int,input().split()))#[0]は要素数であることに注意
    for j in range(1,len(lamp),1):
        switch[lamp[j]].append(i+1)
p = [0] + list(map(int,input().split()))

count = 0
for i in range(0,pow(2,N),1):
    lamps = [0]*(M+1)
    for j in range(1,N+1,1):#swich
        if((i>>(j-1))&1):
            for k in range(0,len(switch[j]),1):
                lamps[switch[j][k]]+=1
    is_OK = True
    for j in range(1,M+1,1):#lamps
        if lamps[j]%2 != p[j]:
            is_OK=False
            break
        
    if is_OK:
        count+=1
print(count)

Submission status: Accepted

Solution code:
from itertools import combinations

N, M = map(int, input().split())
S = []

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

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

for i in range(N+1):
    for c in combinations(range(N), i):
        flag = True
        state = [0] * N
        for n in c:
            state[n] = 1
        for p, s in zip(P,S):
            a = 0
            for k in s:
                a += state[k-1]
            if a % 2 != p:
                flag = False
                break
        
        if flag:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
  n, m = map(int,input().split())
  light = [[0]*n for _ in range(m)]
  for i in range(m):
    kk = list(map(int, input().split()))
    k = kk.pop(0)
    for j in range(k):
      light[i][kk[j]-1] = 1
  p = list(map(int, input().split()))

  ans = 0
  for i in range(2**n): # switchのbit
    sw = [0]*n
    for j in range(n):
      if ((i >> j) & 1):
        sw[j] = 1

    flag = True
    for j in range(m):
      cnt = 0
      for k in range(n):
        if sw[k] == 1 and light[j][k] == 1:
          cnt += 1
      if cnt % 2 != p[j]:
        flag = False
        break
    if flag:
      ans += 1
    
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    tmp = 0 #オンになっているライトを数える
    for idx, light in enumerate(lights):
        on_switch = 0
        for j in range(N):
            if i >> j & 1:
                if j+1 in light:
                    on_switch += 1
        if on_switch % 2 == P[idx]:
            tmp += 1
    if tmp == M:
        ans += 1
print(ans)

Submission status: Accepted

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

for i in range(2 ** n):
    all = 1
    switch = [0] * n
    st = bin(i)[2:]
    st = "0" * (n - len(st))+st
    #print(i,st)
    for j in range(n):
        if st[j] == "1":
            switch[j] = 1
    for j in range(m):
        tmp = 0
        for check in s[j]:
            if switch[check-1] == 1:
                tmp += 1
        if tmp % 2 != p[j]:
            all *= 0
    if all:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def m():
    N, M = map(int, input().split())
    K = [list(map(int, input().split())) for _ in range(M)]
    P = list(map(int, input().split()))
    ans = 0
    for b in range(1 << N):
        mask = bin(b)[2:].zfill(N)
        light = [False] * M
        for j in range(M):
            on = 0
            for k in range(1, K[j][0] + 1):
                if mask[K[j][k] - 1] == '1':
                    on += 1
            if (on % 2) == P[j]:
                light[j] = True
        if all(light):
            ans += 1
    return ans


print(m())

Submission status: Accepted

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

s = bin(0)[2:].zfill(n)
ans = 0

for i in range(2 ** n):
    cnt = 0
    for j in range(m):
        on = 0
        for k in range(1, k_s[j][0] + 1):
            if s[k_s[j][k] - 1] == '1':
                on += 1
            if k == k_s[j][0]:
                if on % 2 == p[j]:
                    cnt += 1
    if cnt == m:
        ans += 1
    s = bin(int(s, 2) + 1)[2:].zfill(n)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
switch=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    cnt=[0]*m
    for j in range(n):
        if (i>>j)&1==1:
            for k in range(m):
                if j+1 in switch[k][1:]:
                    cnt[k]+=1
    l=[i%2 for i in cnt]
    if l==p:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
swi = []
for _ in range(M):
    _, *s = map(int, input().split())
    swi.append(s)
swi =[list(map(lambda x: x-1, ss)) for ss in swi]
# print(swi)
*P, = map(int, input().split())
ans = 0
for i in range(2 ** N):
    # print(bin(i))
    chk = True
    for m in range(M):
        on_off_cnt = 0
        for s in swi[m]:
            if i >> s & 1:
                on_off_cnt += 1
        if on_off_cnt % 2 != P[m]:
            chk = False
    if chk == True:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
swich = [set() for i in range(N)]
ans = 0
b = 0
for i in range(M):
  S = list(map(int, input().split()))
  for j in range(1, len(S)):
    swich[S[j] - 1].add(i)
P = list(map(int, input().split()))
for i in range(2**N):
  light = [0 for i in range(M)]
  for j in range(N):
    if i >> j & 1 == 1:
      for x in swich[j]:
        light[x] += 1
  if all(light[i] % 2 == P[i] for i in range(M)):
    ans += 1
print(ans)

Submission status: Accepted

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

for i in range(M):
    k, *s = map(int, input().split())
    # sの中身は-1して使用する
    memo[i] = s

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

ans = 0
for i in range(2**N):
    tmp = 0
    for idx, light in enumerate(memo):
        on_switches = 0
        for j in range(N):
            if i >> j & 1:
                if j+1 in light:
                    on_switches += 1
        if on_switches % 2 == P[idx]:
            tmp += 1
    if tmp == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# abc128 C
import itertools
n,m = map(int, input().split()) # n個のスイッチとm個の電球

# index i のスイッチとつながる電球がconnect[i]に格納される
connect = []

for i in range(m):
    condi = list(map(int, input().split()))[1:]
    connect.append(condi)
        
    
state = list(itertools.product([0,1], repeat = n))

ans = input().split()

def abc128c(n, m, state, condi, ans):
    pika = [0 for i in range(m)]
    for i in range(m):
        
        on_off = 0
        for j in condi[i]:
            on_off += state[j-1]
        if on_off % 2 == ans[i]:
            pika[i] = 1
    output = 0
    
    if pika == [1 for i in range(m)]:
        output =1
    
    
    return output

# print(abc128c(2, 2, (1,1), [[1,2], [2]], [0,1]))
# abc128c(n, m, a, connect, list(map(int, ans)))
count = 0
for a in state:
    count += abc128c(n, m, a, connect, list(map(int, ans)))
    
print(count)

Submission status: Accepted

Solution code:
from itertools import product
from operator import itemgetter

N, M = map(int, input().split())
lights = list(tuple(map(int, input().split())) for _ in range(M))
cons = list(map(int, input().split()))

ans = 0
for switch in product(range(2), repeat=N):
    reminders = []
    for idx, light in enumerate(lights):
        f = itemgetter(*map(lambda x: x - 1, light[1:]))
        if isinstance(f(switch), int):
            s = f(switch)
        else:
            s = sum(f(switch))
        reminders.append(s % 2)
    if cons == reminders:
        ans += 1
print(ans)

Submission status: Accepted

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

switch_state_list=[]
ans = 0

for _ in range(M):
    temp = list(map(lambda x:int(x)-1, input().split()))
    k.append(temp[0]+1)
    s.append(temp[1:])

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


def check_denqu(switch_state):
    denqu_state=[0]*M

    for i in range(M):
        on_num = 0
        for index in s[i]:
            on_num += switch_state[index]
        if on_num % 2 == p[i]:
            denqu_state[i]=1
        else:
            denqu_state[i]=0
    
    if all(denqu_state):
        return 1
    else:
        return 0


def dfs(i, m):
    global ans

    switch_state_list.append(m)
    if i == N-1:
        ans += check_denqu(switch_state_list)
        switch_state_list.pop()
        return 
   
    dfs(i+1, 0)
    dfs(i+1, 1)

    switch_state_list.pop()


dfs(0,0)
dfs(0,1)

print(ans)

Submission status: Accepted

Solution code:
def main():
  n, m = map(int, input().split())
  g = [[-1]*n for _ in range(m)]
  for i in range(m):
    s = list(map(int, input().split()))
    for j in s[1:]:
      g[i][j-1] = 1
  p = list(map(int, input().split()))

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

if __name__ == '__main__':
  main()

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()))
count=0
for i in range(1<<N):
    for m in range(M):
        switch=0
        for j in range(N):
            if (i>>j)&1 and j+1 in s[m]:
                switch+=1
        if switch%2!=p[m]:
            break
    else:
        count+=1
print(count)

Submission status: Accepted

Solution code:
n,m = (int(x) for x in input().split())
swi = []
for i in range(m):
  l = [int(x) for x in input().split()]
  t = 0
  for i in range(1,len(l)):
    t += 1 << (l[i]-1)
  swi.append(t)
ppp = [int(x) for x in input().split()]

ans = 0
for i in range(1 << n):
  for s, p in zip(swi,ppp):
    t = i & s
    c = bin(t).count("1") % 2
    if c != p:
      break
  else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = [0] * n

for i in range(m):
    k, *s = list(map(int, input().split()))
    for j in range(k):
        a[s[j] - 1] |= 1 << i

p = 0
_p = list(map(int, input().split()))
for i in range(m):
    p |= _p[i] << i

ans = 0
for s in range(1 << n):
    t = 0
    for i in range(n):
        if s >> i & 1:
            t ^= a[i]
    if t == p:
        ans += 1
print(ans)