Problem:


Score : 300 points

Problem Statement

We have N switches with "on" and "off" state, and M bulbs. The switches are numbered 1 to N, and the bulbs are numbered 1 to M.

Bulb i is connected to k_i switches: Switch s_{i1}, s_{i2}, ..., and s_{ik_i}. It is lighted when the number of switches that are "on" among these switches is congruent to p_i modulo 2.

How many combinations of "on" and "off" states of the switches light all the bulbs?

Constraints

1 \leq N, M \leq 10

1 \leq k_i \leq N

1 \leq s_{ij} \leq N

s_{ia} \neq s_{ib} (a \neq b)

p_i is 0 or 1.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
k_1 s_{11} s_{12} ... s_{1k_1}
:
k_M s_{M1} s_{M2} ... s_{Mk_M}
p_1 p_2 ... p_M

Output

Print the number of combinations of "on" and "off" states of the switches that light all the bulbs.

Sample Input 1

2 2
2 1 2
1 2
0 1

Sample Output 1

1

Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.

Bulb 2 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

There are four possible combinations of states of (Switch 1, Switch 2): (on, on), (on, off), (off, on) and (off, off). Among them, only (on, on) lights all the bulbs, so we should print 1.

Sample Input 2

2 3
2 1 2
1 1
1 2
0 0 1

Sample Output 2

0

Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2.

Bulb 2 is lighted when there is an even number of switches that are "on" among the following: Switch 1.

Bulb 3 is lighted when there is an odd number of switches that are "on" among the following: Switch 2.

Switch 1 has to be "off" to light Bulb 2 and Switch 2 has to be "on" to light Bulb 3, but then Bulb 1 will not be lighted. Thus, there are no combinations of states of the switches that light all the bulbs, so we should print 0.

Sample Input 3

5 2
3 1 2 5
2 2 3
1 0

Sample Output 3

8



Sample input:
2 2
2 1 2
1 2
0 1


Sample output:
1

Submission status: Accepted

Solution code:
import copy

num_of_switch, num_of_lights = [int(_) for _ in input().split()]

S = [[int(s) - 1 for s in input().split()[1:]] for i in range(num_of_lights)]
P = [_ == "1" for _ in input().split()]

# i は switch の添字


def rec(switch_idx, lights):
    if switch_idx == num_of_switch:
        if lights == P:
            return 1
        else:
            return 0

    switch_off_result = rec(switch_idx + 1, lights)

    _lights = copy.deepcopy(lights)

    for light_idx in range(num_of_lights):
        # print(f"switch_idx = {switch_idx}, light_idx = {light_idx}")
        is_connect = switch_idx in S[light_idx]
        if is_connect:
            _lights[light_idx] = not _lights[light_idx]

    # print(f"switch_idx = {switch_idx}: not choose = {lights}, choose = {_lights} ")

    switch_on_result = rec(switch_idx + 1, _lights)

    return switch_off_result + switch_on_result


ans = rec(0, [False] * num_of_lights)
print(ans)

Submission status: Accepted

Solution code:
import copy

num_of_switch, num_of_lights = [int(_) for _ in input().split()]


def toSwitch(xs):
    xs[1:]


S = [[int(s) - 1 for s in input().split()[1:]] for i in range(num_of_lights)]
P = [_ == "1" for _ in input().split()]

# i は switch の添字


def rec(switch_idx, lights):
    if switch_idx == num_of_switch:
        if lights == P:
            return 1
        else:
            return 0

    switch_off_result = rec(switch_idx + 1, lights)

    _lights = copy.deepcopy(lights)

    for light_idx in range(num_of_lights):
        # print(f"switch_idx = {switch_idx}, light_idx = {light_idx}")
        is_connect = switch_idx in S[light_idx]
        if is_connect:
            _lights[light_idx] = not _lights[light_idx]

    # print(f"switch_idx = {switch_idx}: not choose = {lights}, choose = {_lights} ")

    switch_on_result = rec(switch_idx + 1, _lights)

    return switch_off_result + switch_on_result


ans = rec(0, [False] * num_of_lights)
print(ans)

Submission status: Accepted

Solution code:
def switch_combination_of_light_on():
    # 入力
    N, M = map(int, input().split())
    K = list()
    S = list()
    for _ in range(M):
        dummy = list(map(int, input().split()))
        K = dummy.pop(0)
        S.append(dummy)
    P = list(map(int, input().split()))
    # 組み合わせ処理
    result = 0
    for bit in range(1 << N):
        right_on = False
        for i in range(M):
            count = 0
            for j in S[i]:
                if bit & (1 << j - 1):
                    count += 1
            if count % 2 == P[i]:
                right_on = True
            else:
                right_on = False
                break
        if right_on:
            result += 1
    # 出力
    print(result)

switch_combination_of_light_on()

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()))
ans = 0
for i in range(2**N):
  count = 0
  on_or_off = [0]*M
  for j in range(N):
    if (i>>j)&1:
      for k in range(M):
        if j+1 in S[k][1:]:
          on_or_off[k] += 1
  for l in range(M):
    if on_or_off[l]%2 == P[l]:
      count += 1
  if count == M:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = [0]*M
for i in range(M):
    s = list(map(int, input().split()))
    for j in s[1:]:
        S[i] += 2**(j-1)
p = list(map(int, input().split()))
ans = 0
for b in range(2**N):
    tmp = True
    for i, s in enumerate(S):
        tmp &= bin(b&s).count('1')%2==p[i]
    if tmp:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

#a = int(input())
#b = list(map(int, input().split()))
n, m = map(int, input().split())
#s = input()
#s,t = input().split()
#a = [int(input()) for _ in range(n)]
#
readline = sys.stdin.readline
#n,m = [int(i) for i in readline().split()]
KS = [[int(i) for i in readline().split()] for _ in range(m)]
P = [int(i) for i in readline().split()]

import itertools

L = list(itertools.product([0,1], repeat=n))

ans = 0

for l in L:
    for ks, p in zip(KS, P):
        tmp = sum([l[i-1] for i in ks[1:]])
        if tmp%2 == p:
            pass
        else:
            break
    else:
        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()))

ans = 0
for i in range(2**N):
    switches = bin(i)[2:].zfill(N)
    for j in range(M):
        _, *S = KS[j]
        on = 0
        for k, s in enumerate(switches, 1):
            if s == '1' and k in S:
                on += 1
        if on % 2 != P[j]:
            all_light_on = False
            break
    else:
        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()))

ans = 0
for i in range(2**N):
    switches = bin(i)[2:].zfill(N)
    all_light_on = True
    for j in range(M):
        _, *S = KS[j]
        on = 0
        for k, s in enumerate(switches, 1):
            if s == '1' and k in S:
                on += 1
        if on % 2 == P[j]:
            continue
        else:
            all_light_on = False
            break
    if all_light_on:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
K = [list(map(int,input().split())) for i in range(M)]
P = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    count = 0#幾つの電球がonになっているか
    on_or_off = [0]*M #M個の電球それぞれに対し、割り当てられたスイッチのうち、幾つがonになっているか
    for j in range(N):
        if(i>>j)&1:#スイッチjがonになっているとき
            for k in range(M):
                if j+1 in K[k][1:]:#スイッチjが電球kにつながっているなら、電球kのスイッチカウントをプラス
                    on_or_off[k] += 1
    for l in range(M):#幾つの電球が点灯しているか
        if on_or_off[l]%2==P[l]:
            count += 1
    if(count == M):#全ての電球が点灯していたら+1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n, m = map(int,input().split())
S = []
for i in range(m):
    s = list(map(int,input().split()))
    S.append(s[1:])
p = list(map(int,input().split()))
ans = 0
for c in product([0, 1], repeat = n):
    ok = True
    for j in range(m):
        sm = 0
        for k in S[j]:
            sm += c[k-1]
        if sm % 2 != p[j]:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
KS = [list(map(int,input().split())) for _ in range(M)]
P = list(map(int,input().split()))
ans = 0
for bit in range(1<<N):
    for i,ks in enumerate(KS):
        SUM = 0
        for s in ks[1:]:
            if bit & (1<<(s-1)):
                SUM += 1
        if SUM%2 != P[i]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

config = np.zeros((M, N)).astype(int)

for i in range(M):
    switches = [int(n) for n in input().split()]
    for switch in switches[1:]:
        config[i][switch - 1] = 1

P = np.asarray([int(n) for n in input().split()], dtype=int).reshape((M, 1))

bits = itertools.product((0,1), repeat=N)

count = 0

for bit in bits:
    bit_vect = np.asarray(bit, dtype=int).reshape((N, 1))
    if np.array_equal(np.dot(config, bit_vect) % 2, P):
        count += 1

print(count)

Submission status: Accepted

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

for _ in range(m):
    s = list(map(int, input().split()))[1:]
    l.append(s)

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

for i in range(2 ** n):
    tmp = [0] * n
    flg = False
    for j in range(n):
        if i >> j & 1:
            tmp[j] = 1
    for i, s in enumerate(l):
        cnt = sum([tmp[e-1] for e in s])
        if cnt % 2 != p[i]:
            flg = True
            break
    if not flg:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ans=0
S=[]
for i in range(M):
    s=list(map(int,input().split()))
    K=s.pop(0)
    S.append(s)
P = list(map(int, input().split()))
for i in range(1<<N):
    ok=True
    for j in range(M):
        cnt=0
        for s in S[j]:
            if ((i>>s-1)&1):
                cnt+=1
        if cnt%2!=P[j]:
            ok=False
    if ok:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = list(list(map(int, input().split())) for _ in range(m))
p = list(map(int, input().split()))
check = 0

def rec(A, c):
  if len(A) == n:
    count_m = 0
    for l in range(m):
      list_k = k[l]
      count = 0
      for j in range(1, list_k[0] + 1):
        if A[list_k[j] - 1] == 1:
          count += 1
      if p[l] == (count%2):
        count_m += 1
    if(count_m == m):
      c += 1
    return c
  
  for i in range(2):
    A.append(i)
    c = rec(A, c)
    A.pop()

  return c

print(rec([], check))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
S = []
for _ in range(m):
  t = list(map(int,input().split()))[1:]
  t = [v-1 for v in t]
  S.append(t)
p = list(map(int,input().split()))

cnt = 0
for i in range(2**n):
  ok = True
  for j,s in enumerate(S):
    l = 0
    for v in s:
      if (i>>v) & 1: l+=1
    if l%2 != p[j]:
      ok = False
      break
  if ok:
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import numpy as np

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

cnt = 0
for i in range(2**N):
  cnt += np.prod([
    sum([int(bin(i)[2:].zfill(N)[s-1]) for s in S[j][1:]])%2 == P[j]
    for j in range(M)
  ])
print(cnt)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

ans = 0
for bit in range(2 ** N):
    ons = 0
    for i in range(M):
        total = K[i]
        for j in S[i]:
            if bit >> (j - 1) & 1 == 0:
                total -= 1
        if total % 2 == P[i]:
            ons += 1
    if ons == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
li=[]
for i in range(m):
  dk,*d=list(map(int,input().split()))
  li.append(d)
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
  sw=bin(i)[2:].zfill(n)
  for j in range(m):
    cnt=0
    for k in li[j]:
      if sw[k-1]=='1':
        cnt+=1
    if cnt%2!=p[j]:
      break
  else:ans+=1
print(ans)

Submission status: Accepted

Solution code:
ans = 0
def solve(balb, p, S, N, M):
    if len(S) == N:
        global ans

        up = 0
        for i in range(M):
            on = 0
            for j in balb[i]:
                if S[j] == "1":
                    on += 1

            if (on % 2 == p[i]):
                up += 1

        if up == M:
            ans += 1
        
    else:
        solve(balb, p, S + "1", N, M)
        solve(balb, p, S + "0", N, M)

def main():
    N, M = map(int, input().split())
    balb = list()

    for i in range(M):
        sw = [int(a) - 1 for a in input().split()]
        balb.append(sw[1:])

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

    solve(balb, p, "", N, M)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(m)]
di = list(map(int,input().split()))
q = 0
for i in range(2**n):
    a = [0]*n
    for j in range(n):
        if (i>>j)&1:
            a[j] = 1
    p = 0
    for k in range(m):
        s = 0
        for l in ls[k][1:ls[k][0]+1]:
            s += a[l-1]
        if s%2 != di[k]:
            p = 1
    if p == 0:
        q += 1
print(q)

Submission status: Accepted

Solution code:
import itertools
count =0
ans=0
n,m = map(int,input().split())
num=[0,1]
pattern = list(itertools.product(num, repeat=n))
lists =[]
switches = [1]*n
onoff = [0]*m
for i in range(m):
    lists.append(list(map(int,input().split())))
key_value = list(map(int,input().split()))
for l in pattern:
    switches = list(l)
    onoff = [0]*m
    for j in range(m):
        count=0
        for k in lists[j][1:]:
            if switches[k-1] == 1:
                count += 1
        if count %2 == key_value[j]:
            onoff[j] = 1
        else:
            break
    if not 0 in onoff:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    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):
        state = [0] * N
        flag = True
        for j in range(N):
            if (i >> j) & 1:
                state[j] = 1
        for k in range(M):
            cnt = 0
            for l in s[k]:
                cnt += state[l-1]
            if cnt%2 == p[k]:
                continue
            else:
                flag = False
                break
        if flag:
            ans += 1
    print(ans)
                
if __name__  == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    # k = []
    s = []
    for i in range(m):
        x = list(map(int, input().split()))
        # k.append(x[0])
        y = 0
        for j in x[1:]:
            y |= 1 << (j - 1)  # 0bit目を1にする
        s.append(y)
    p = list(map(int, input().split()))

    res = 0
    for bit in range(1 << n):
        all_on = True
        for i in range(m):
            n_on = bin(s[i] & bit).count('1')
            if n_on % 2 != p[i]:
                all_on = False
                break
        if all_on:
            res += 1

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, M = map(int, readline().split())
    S = [0] * M
    for i in range(M):
        k, *S[i] = [int(s) - 1 for s in readline().split()]
    P = list(map(int, readline().split()))

    ans = 0
    for bit in range(1 << N):
        ok = True
        for j in range(M):
            lit = sum(1 for s in S[j] if bit & (1 << s))
            if lit % 2 != P[j]:
                ok = False
                break
        if ok:
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 初期入力
from itertools import product
import sys
input = sys.stdin.readline
N,M = (int(i) for i in input().split())
num_suitch =[-1]*M
switch =[[]for i in range(M)]
for i in range(M):
    k,*s = (int(i) for i in input().split())
    num_suitch[i] =k
    switch[i] =s
p = list(map(int, input().split()))

#スイッチのON、OFFを全探索。スイッチの組み合わせで全ての電球がつけばカウント
count =0
for on in product([0,1],repeat=N): #N個の スイッチ
    light =[0]*M
    index_on =[i+1 for i, x in enumerate(on) if x == 1] 
    for j in range(M):                      # M 個の電球       
        l =set(index_on) & set(switch[j])
        if len(l) %2 ==p[j]:
            light[j] =1
    if sum(light) ==M:
        count +=1
print(count)

Submission status: Accepted

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

for i in range(1 << n):
    switch = set()
    for j in range(n):
        if (i >> j)&1:
            switch.add(j+1)
    for k in range(m):
        point = 0
        for l in li[k]:
            if l in switch:
                point += 1
        if point%2 != p[k]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

def main():
    n,m=map(int,input().split())
    k = []
    for _ in range(m):
        k.append(list(map(int, input().split())))
    p = list(map(int, input().split()))
    count = 0
    for s in itertools.product([0,1], repeat=n):
        for i,kk in enumerate(k):
            if not is_on(s, kk[1:], p[i]):
                break
        else:
            #print(s)
            count += 1
    print(count)

def is_on(s, cond, p):
    count = 0
    for c in cond:
        count += s[c-1]
    return count % 2 == p
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M = (int(x) for x in input().split())
a = [0]*N  
k = []
ans = 0
for i in range(M):
  k = [int(x) for x in input().split()]
  for j in range(k[0]): #kよりつながっている電球を一個ずつ見てる
    s = k[j+1]-1
#    print(i,j,s,a[s],a)
    a[s] = a[s] | (1<<i) #aは各スイッチがつながっている電球の情報を保持
#   左端はMとつながっているかどうかを表す。
    #a[0]＝10100はスイッチ０が電球4と電球2とつながっていることを表している。
p = [int(x) for x in input().split()]
P = 0
for i in range(M):
  P |= p[i] << i
#Pはpの情報を全て持っている二進数。例えば、P＝10011は電球４、１、０が
# on になっているスイッチの個数を2で割った余りが１の時点灯するを表す
#左端がMは統一されている

#1<<N は2**nと同じ
for s in range(1<<N):
  t = 0
  for i in range(N):
    if ((s>>i) & 1):#スイッチオンだったら
      t ^= a[i]		
      #これはXORを使って、スイッチがonになっているスイッチの個数を２で割ったあまりを表している
  if (t == P):	#もし、t＝＝Pなら、当てはまっているので、ans++する。
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = (int(x) for x in input().split())
a = [0]*N  
k = []
ans = 0
for i in range(M):
  k = [int(x) for x in input().split()]
  for j in range(k[0]): #kよりつながっている電球を一個ずつ見てる
    s = k[j+1]-1
#    print(i,j,s,a[s],a)
    a[s] = a[s] | (1<<i)
#   print(i,j,s,a[s],a)
    #二進数でi桁目が１のとき、スイッチsとi番目の電球がつながっている?
p = [int(x) for x in input().split()]
P = 0
for i in range(M):
  P |= p[i] << i
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)

Submission status: Accepted

Solution code:
n,m=[int(x) for x in input().rstrip().split()]
temp=[0 for i in range(m)]
# ans=[0 for i in range(n)]
ans=0
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()]

for i in range(2**n):
  flag=1
  for j in range(n):
    if i>>j & 1:
      for s in range(m):
        for k in range(1,l[s][0]+1):
          if (j+1)==l[s][k]:
            temp[s]+=1

  for t in range(m):
    if temp[t]%2!=p[t]:
      flag=0
      break
  
  if flag==1:
    ans+=1
  temp=[0 for ini in range(m)]

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N, M = map(int, input().split())
denkyu = []
for i in range(M):
    denkyu.append([int(j) for j in input().split()])
p = [int(i) for i in input().split()]
ls = [0, 1]
ans = 0
for x in product(ls, repeat=N):
    num = 0
    for j, denkyu_ in enumerate(denkyu):
        num_light_on = 0
        for i, s in enumerate(denkyu_):
            if i != 0 and x[s-1] == 1:
                num_light_on += 1
        if num_light_on%2 == p[j]:
            num += 1
    if num == M:
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
switches = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    all_on_flag = 1
    for j in range(m):
        switch = switches[j]
        cnt = 0
        for s in switch[1:]:
            if i & (1 << (s-1)):
                cnt += 1
        if cnt % 2 != p[j]:
            all_on_flag = 0
            break
    if all_on_flag:
        ans += 1
print(ans)

Submission status: Accepted

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

on_off_patterns = []
for i in range(2 ** N):
    on_off = [0] * N
    for j in range(N):
        if ((i >> j) & 1):
            on_off[N-1-j] = 1
    on_off_patterns.append(on_off)
    
bulbs = []
for i in range(M):
    bulb_data = [int(i) for i in input().split()]
    k = bulb_data[0]
    switches = bulb_data[1:]
    bulbs.append([n -1 for n in switches])
    
p = [int(i) for i in input().split()]

cnt = 0
for pattern in on_off_patterns:
    bulb_on_off = [0] * M
    for b in range(len(bulbs)):
        value = 0
        for s in range(len(bulbs[b])):
            value += pattern[bulbs[b][s]]
            
        if value % 2 == p[b]:
            bulb_on_off[b] = 1
        else :
            bulb_on_off[b] = 0
    if sum(bulb_on_off) == M:
        cnt += 1
print(cnt)

Submission status: Accepted

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

def all_on(i: int):
  for j in range(M):
    count = 0
    for sw in s[j]:
      if i & (1<<(sw-1)):
        count += 1
    if count%2 != p[j]:
      return False
  return True

ans = 0
for i in range(1<<N):
  if all_on(i):
    ans += 1
print(ans)

Submission status: Accepted

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

count=0
for i in range(2**n):
  on=[]
  lamp=[False]*m
  for j in range(n):
    if ((i >> j) & 1):
      on.append(j)
  
  for la in range(m):
    judge=0
    for x in on:
      for y in s[la]:
        if x==y:
          judge+=1
    if judge%2==p[la]:
      lamp[la]=True
  if all(lamp):
    count+=1

print(count)

Submission status: Accepted

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

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

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

ans = 0
for status in range(1<<N):#スイッチのon/offの状態
    on = []#onになってるスイッチの番号
    for mask in range(N):
        if (1<<mask)&status:
            on.append(mask)
    for i,s in enumerate(related_switch):
        if len(set(s)&set(on))%2 != p[i]:
            break
    else:
        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()))
count = 0

for i in range(2**n):
  SUMLIST = []
  SUM = 0
  check = 0
  l = [0]*n
  for j in range(n):
    if ((i >> j)&1):
      l[n-j-1] = 1
  
  for switch in ks:
    for each in switch[1:]:
      SUM += (l[each-1])
    SUMLIST.append(SUM)
    SUM = 0
  
  for i in range(m):
    if SUMLIST[i]%2 == p[i]:
      check += 1
 
  if check == m:
    count += 1

print(count)

Submission status: Accepted

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

def bit_all():
    ret = 0
    for x in range(2 ** N):
        b = str(format(x, '010b'))
        add = 1
        for i in range(M):
            count = 0
            for j in s[i]:
                j -= 1
                if b[-(j + 1)] == "1": 
                    count += 1
            if count % 2 != p[i]:
                add = 0
        ret += add
    return ret

ans = bit_all()
print(ans)

Submission status: Accepted

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

k = []
s = []
ans = 0

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

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

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

print(ans)

Submission status: Accepted

Solution code:
def readinput():
    n,m=list(map(int,input().split()))
    lmpSw=[]
    for _ in range(m):
        l=list(map(int,input().split()))
        lmpSw.append(l[1:])
    p=list(map(int,input().split()))
    return n,m,lmpSw,p

def main(n,m,lmpSw,p):
    lmpSwBit=[0]*m
    for i in range(m):
        swBit=0
        for sw in lmpSw[i]:
            swBit+=2**(sw-1)
        lmpSwBit[i]=swBit

    lmpStat=[]
    for i in range(m):
        stat=[0 for x in range(2**n)]
        lmpStat.append(stat)
    # lmpStat[m][swStat]

    allon=0
    for swStat in range(2**n):
        # スイッチの全状態をスキャン
        count=0
        for lmp in range(m):
            # 全電球についてループ
            swBit=lmpSwBit[lmp]
            b=1
            for sw in range(n):            
                if(swBit&b==b) and (swStat & b)==b:
                    lmpStat[lmp][swStat]+=1
                b=b*2
            lmpStat[lmp][swStat]+=p[lmp]
            if(lmpStat[lmp][swStat]%2==0):
                count+=1
        if(count==m):
            allon+=1
    return allon


if __name__=='__main__':
    n,m,lmpSw,p=readinput()
    ans=main(n,m,lmpSw,p)
    print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = []
for i in range(m):
    line = list(map(int, input().split()))
    s.append(line[1:])
p = list(map(int, input().split()))
ans = 0
for pat in range(2**n):
    light_flag = True
    for i in range(m):
        tot = 0
        for sw in s[i]:
            if pat & (2 ** (sw - 1)):
                tot += 1
        if tot % 2 != p[i]:
            light_flag = False
    if light_flag:
        ans += 1
print(ans)

Submission status: Accepted

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

S = [[]for i in range(M)]

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

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

D=[0]*M

#print(S)
#print(P)

count=0

even=0
odd=0
#Nをビットで羅列
for i in range(2 **N):
    D=[0]*M
    ON_SW=[0]*M
    #ビットシフト
    for j in range(N):
        if ((i >> j) & 1):
            #print(i,j)
            for k in range(M):
                for l in range(len(S[k])):
                    if j+1==S[k][l]:
                        ON_SW[k]+=1
                        #print(ON_SW)
    
    #print("ONSW="+str(ON_SW)+"PK="+str(P[k]))
            
    flag=True
    for j in range(M):
        
        if ON_SW[j]%2==P[j]:
            pass
        else:
            flag=False
        
    if flag==True:
        #print(i)
        count+=1
    #print(ON_SW)
    #print(ON_SW,ON_SW[0]%2,ON_SW[1]%2,P)
print(count)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
lists = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    pattern = []
    flag = True
    for j in range(n):
        if ((i >> j) & 1):
            pattern.append(1)
        else:
            pattern.append(0)
    for k in range(m):
        k_kosu = 0
        for l in range(1,len(lists[k])):
            if pattern[lists[k][l]-1] == 1:
                k_kosu += 1
        if k_kosu % 2 != p[k]:
            flag = False
            break
    if flag:
        ans += 1 
print(ans)

Submission status: Accepted

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

s = []
for i in range(M):
    _, *tmp_s = map(int, input().split())
    s.append(tmp_s)
    
p = list(map(int, input().split()))

import numpy as np

s_matrix = []

for i in range(M):
    s_matrix.append([1 if x+1 in s[i] else 0 for x in range(N)])
    
s_matrix = np.array(s_matrix)

ans = 0

for i in range(2**N):
    on_off_pattern = list(format(i, '0%db' %N))
    on_nums = np.dot(s_matrix, np.array(list(map(int, on_off_pattern))))
    on_nums_mod2 = on_nums % 2

    if not False in (on_nums_mod2 == p):
        ans += 1
        
print(ans)

Submission status: Accepted

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

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

  t_cnt=0
  for j in range(m):
    on_l=0
    for x in k[j][1:]:
      x-=1
      if l[x]==1:
        on_l+=1
    if on_l%2==p[j]:
      t_cnt+=1

  if t_cnt==m:
    cnt+=1

print(cnt)