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:
def solve(Switch, K, P):
    count = 0
    for l_1 in K:
        total = 0
        for i_1 in l_1:
            total += Switch[i_1-1]
        if total % 2 != P[count]:
            return False
        count += 1
    return True

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

ans = 0

for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if ((i >> j) &1):
            switch[j] = 1
    if solve(switch, k, p):
        ans+=1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import combinations
n,m = map(int,input().split())
l = []
for i in range(m):
    u = list(map(int,input().split()))
    u = u[1:]
    l.append(u)

p = list(map(int,input().split()))
v = []
for i in range(1,n+1):
    v.append(i)

c = []
for i in range(n+1):
    a = combinations(v,i)
    for k in a:
        c.append(k)

ans = 0
for ele in c:
    s = set(ele)
    f = 0
    for i in range(len(l)):
        x = l[i]
        cnt = 0
        for j in x:
            if j in s:
                cnt = cnt+1

        if cnt%2 != p[i]:
            f = 1
            break

    if f == 0:
        ans = ans+1

print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
V = [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(1 << N):
    B = format(i, f'0{N}b')[::-1]
    flg = True
    for j in range(M):
        cnt = 0
        for s in V[j]:
            if B[s] == '1':
                cnt += 1
        if cnt % 2 != P[j]:
            flg = False
    res += int(flg)
print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C
# CreatedDate:  2020-07-30 02:44:47 +0900
# LastModified: 2020-07-30 13:58:47 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n, m = map(int, input().split())
    switch_list = []
    for _ in range(m):
        command = list(map(int, input().split()))
        _ = command[0]
        switch_list.append(command[1:])
    p = list(map(int, input().split()))
    ans = 0
    for i in range(1 << n):
        flag = 1
        for j, switch in enumerate(switch_list):
            cnt = 0
            for s in switch:
                if 1 & i >> (s-1):
                    cnt += 1
            if cnt % 2 != p[j]:
                flag = 0
                break
        if flag == 1:
            ans += 1

    print(ans)






if __name__ == "__main__":
    main()

Submission status: Accepted

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

swich = [0] * n

for i in range(m):
    _, *s = map(int, input().split())
    for j in range(len(s)):
        # swich[s[j] - 1] += 1 << (i)
        swich[s[j] - 1] ^= 1 << (i)
        # swich[s[j] - 1] |= 1 << (i)
    


p_list = list(map(int, input().split()))
p = 0
for i in range(m):
    if p_list[i] == 1: 
        p += 1 << i
    # p |= p_list[i] << i #上の処理と同じ

# print("++++++++++++++++++++++++")
# print(swich)
ans = 0
for i in range(1 << n):
    state_on_off = 0
    for index in range(n):
        if i >> index & 1 == 1:
            state_on_off ^= swich[index]
    if state_on_off == p:
        ans += 1
    # print(p, state_on_off,bin(i))
print(ans)

Submission status: Accepted

Solution code:

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

swich = [0] * n

for i in range(m):
    _, *s = map(int, input().split())
    for j in range(len(s)):
        swich[s[j] - 1] += 1 << (i)
        # swich[s[j] - 1] ^= 1 << (i)
        # swich[s[j] - 1] |= 1 << (i)
    


p_list = list(map(int, input().split()))
p = 0
for i in range(m):
    if p_list[i] == 1: 
        p += 1 << i
    # p |= p_list[i] << i #上の処理と同じ

# print("++++++++++++++++++++++++")
# print(swich)
ans = 0
for i in range(1 << n):
    state_on_off = 0
    for index in range(n):
        if i >> index & 1 == 1:
            state_on_off ^= swich[index]
    if state_on_off == p:
        ans += 1
    # print(p, state_on_off,bin(i))
print(ans)

Submission status: Accepted

Solution code:

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

swich = [0] * n

for i in range(m):
    _, *s = map(int, input().split())
    for j in range(len(s)):
        # swich[s[j] - 1] += 1 << (i)
        # swich[s[j] - 1] ^= 1 << (i)
        swich[s[j] - 1] |= 1 << (i)
    


p_list = list(map(int, input().split()))
p = 0
for i in range(m):
    # if p_list[i] == 1: 
    #     p += 1 << i
    p |= p_list[i] << i #上の処理と同じ

# print("++++++++++++++++++++++++")
# print(swich)
ans = 0
for i in range(1 << n):
    state_on_off = 0
    for index in range(n):
        if i >> index & 1 == 1:
            state_on_off ^= swich[index]
    if state_on_off == p:
        ans += 1
    # print(p, state_on_off,bin(i))
print(ans)

Submission status: Accepted

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

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

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

# print("######################################")
res = 0
for i in range(1 << n):
    on_off_state = []
    for index in range(n):
        if i >> index & 1 == 1:
            on_off_state.append("on")
        else:
            on_off_state.append("off")
    for ki in range(m):
        on_off_counter = 0
        for i_switch in switch[ki]:
            if on_off_state[i_switch - 1] == "on":
                on_off_counter += 1
        if on_off_counter % 2 != is_on_off[ki]:
            break
    else:
        res += 1
    # print(res, i)

print(res)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = [[int(x) for x in input().split()[1:]] for i in range(m)]
odd_even = [int(x) for x in input().split()]


num = 0
limit = 2**n
ans = 0
while(num < limit):
    
    isOK = True
    for i in range(m):
        cnt = 0
        for x in l[i]:
            if((num >> (x-1)) & 1):
                cnt += 1
        
        if(cnt%2!=odd_even[i]):
            isOK = False
            break        
        
    if(isOK):
        ans += 1    
    
    num += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
K = [0]*m
S = [[] for _ in range(m)]
for i in range(m):
    K[i], *S[i] = map(lambda x:int(x)-1, input().split())
    K[i] += 1
P = list(map(int, input().split()))

ans = 0
for i in range(pow(2,n)):
    B = bin(i)[2:].zfill(n)
    D = {j:True if b=='1' else False for j,b in enumerate(B)}
    _P = []
    for j,s in enumerate(S):
        _P.append(sum(D[_s] for _s in s)%2 == P[j])
    if all(_P):
        ans += 1
print(ans)

Submission status: Accepted

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

def get_bits_pattern(n):
    bits_pattern = []
    for i in range(2**n):
        bits = [False]*n

        for j in range(n):
            if i >> j & 1:
                bits[j] = True
        bits_pattern.append(bits)
    return bits_pattern

bits_pattern = get_bits_pattern(n)

pattern_counter = 0
for bits in bits_pattern:
    is_on = True
    for _s, _p in zip(s, p):
        counter = 0
        for __s in _s:
            if bits[__s-1]:
                counter += 1
        if _p != counter % 2:
            is_on = False
    if is_on:
        pattern_counter += 1

print(pattern_counter)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
bulbs = []
for _ in range(m):
    b = tuple(map(int, input().split()))
    bulbs.append(b[1:])

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

ans = 0

for switch in range(2**n):
    check = [0] * m
    for i, bulb in enumerate(bulbs):
        cnt = 0
        for b in bulb:
            if switch >> (b-1) & 1:
                cnt += 1
            
        if cnt % 2 == p[i]:
            check[i] = True
        else:
            check[i] = False
    
    if  all(check):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
K=[]
S=[]
for i in range(m):
  tmp=list(map(int,input().split()))
  K.append(tmp[0])
  S.append(tmp[1:])
P=list(map(int,input().split()))
ans=0
for i in range(2**n):
  bit=format(i,'0'+str(n)+'b')
  bit=list(map(int,bit))
  on_den=0
  for den in range(m):
    on_swi=0
    for s in S[den]:
      on_swi+=bit[s-1]
    if on_swi%2==P[den]:
      on_den+=1
  if on_den==m:
    ans+=1
print(ans)

Submission status: Accepted

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

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

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

ans = 0
for bits in range(1<<N):
    flag = True

    for i in range(M):
        cnt = 0
        for s in switch[i]:
            if(bits>>(s-1) & 1):
                cnt += 1

        if cnt % 2 != P[i]:
            flag = False
    
    if flag: ans += 1

print(ans)

Submission status: Accepted

Solution code:

N, M = map(int, input().split())
K = []
X = []
for _ in range(M):
    k, *x = list(map(int, input().split()))
    K.append(k)
    X.append(x)
P = list(map(int, input().split()))

ans = 0
for bit in range(2 ** N):
    light_on = [False] * M
    for i in range(M):
        tmp = 0
        for s in X[i]:
            tmp += bit >> (s - 1) & 1
        light_on[i] = tmp % 2 == P[i]

    ans += all(light_on)

print(ans)

Submission status: Accepted

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

ans = 0
for bit in range(2**N):
    on_list = []
    for i in range(N):
        if bit & (1 << i):
            on_list.append(i+1)
    flag = True
    for s, p_ in zip(ks, p):
        on_sum = len(list(set(on_list) & set(s[1:])))
        if on_sum % 2 != p_:
            flag = False
            break
    
    if flag:
        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)]
p = list(map(int, input().split()))

ans = 0
for i in range(1 << n):
    tmp = 0
    for j in range(m):
        on = 0
        for k in range(1, s[j][0]+1):
            if i & (1 << s[j][k]-1):
                on += 1
        if p[j] % 2 == on % 2:
            tmp += 1
    if tmp == m:
        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 = list(map(int, input().split()))

ans = 0
# pow(2,N)のbit全探索
for num in range(1 << N):
    # 全ての電灯を確認
    # print(num)
    flag = True
    for m in range(M):
        count_m = 0
        for j in K[m][1:]:
            if num & (1 << (j - 1)):
                count_m += 1
        # print(m, count_m, K[m], P[m])
        if count_m % 2 != P[m]:
            flag = False
            break
    # print(num, flag)
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

k=[]
s=[]

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


count = 0
for i in range(2**N):
    lighton_num = 0
    for m in range(M):
        switchon_num = 0
        for j in range(k[m]):
            
            if (i>>(s[m][j]-1)) &1== 1:
                switchon_num+=1
            
        
        if switchon_num%2 == p[m]:
            lighton_num += 1
        # print(bin(i), m, j,switchon_num,p[m], lighton_num, count)
        
    if lighton_num == M:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
List = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
num = 0
for i in range(2**N): 
  B = [0 for _ in range(M)] 
  for j in range(N):
    if ((i>>j)&1):
      for k in range(M):
        if j+1 in List[k][1:]:
          B[k] += 1
  for l in range(M):
    if B[l] % 2 != p[l]:
      break
  else:
    num += 1
print(num)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
denq = []
for _ in range(m):
    ks = tuple(map(lambda x: int(x)-1, input().split()))
    denq.append(ks[1:])
P = tuple(map(int, input().split()))

ans = 0
for i in range(2**n):
    switch_states = [(i>>j)&1 for j in range(n)]
    for idq, dq in enumerate(denq):
        counts = 0
        for s in dq:
            counts += switch_states[s]
        if counts%2 != P[idq]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
denq = []
for _ in range(m):
    ks = tuple(map(lambda x: int(x)-1, input().split()))
    denq.append(ks[1:])
P = tuple(map(int, input().split()))

ans = 0
for i in range(2**n):
    # switch_states = [(i>>j)&1 for j in range(n)]
    for idq, dq in enumerate(denq):
        counts = 0
        for s in dq:
            counts += (i>>s)&1
        if counts%2 != P[idq]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
denq = []
for _ in range(m):
    ks = tuple(map(lambda x: int(x)-1, input().split()))
    denq.append(ks[1:])
P = tuple(map(int, input().split()))

ans = 0
for i in range(2**n):
    kk = [0] * m
    for idq, dq in enumerate(denq):
        counts = 0
        for s in dq:
            counts += (i>>s)&1
        if counts%2 != P[idq]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
denq = []
for _ in range(m):
    ks = tuple(map(lambda x: int(x)-1, input().split()))
    denq.append(ks[1:])
P = tuple(map(int, input().split()))

ans = 0
for i in range(2**n):
    kk = [0] * m
    # switch_states = [(i>>j)&1 for j in range(n)]
    for idq, dq in enumerate(denq):
        counts = 0
        for s in dq:
            counts += (i>>s)&1
        if counts%2 != P[idq]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
denq = []
for _ in range(m):
    ks = tuple(map(lambda x: int(x)-1, input().split()))
    denq.append(ks[1:])
P = tuple(map(int, input().split()))

ans = 0
for i in range(2**n):
    kk = [0] * m
    switch_states = [(i>>j)&1 for j in range(n)]
    for idq, dq in enumerate(denq):
        counts = 0
        for s in dq:
            counts += switch_states[s]
        if counts%2 != P[idq]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
denq = []
for _ in range(m):
    ks = tuple(map(lambda x: int(x)-1, input().split()))
    denq.append(set(ks[1:]))
P = tuple(map(int, input().split()))

ans = 0
for i in range(2**n):
    kk = [0] * m
    for j in range(n):
        # スイッチjがonの場合
        if (i>>j)&1:
            for idq, dq in enumerate(denq):
                # すべての電球に対して
                # スイッチjが電球に紐付けられていれば、onをカウント
                if j in dq:
                    kk[idq] += 1

    for idq in range(m):
        if P[idq] != kk[idq]%2:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
ビット全探索
"""
n, m = map(int, input().split())
lamps = [list(map(lambda x:int(x)-1, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
#ビット全探索
for i in range(2**n) :
    for r in range(m) :
        on = 0
        for j in range(n) :
            #j桁目が1であるかどうかを調べる
            #jがsに含まれているかどうか調べる
            if (i>>j) & 1 == 1 and j in lamps[r] :
                on += 1
        if on % 2 != p[r] :
            break
    else :
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools

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

switch = [0, 1]
lists = list(itertools.product(switch, repeat=n))
count = 0
for l in lists:
  for i in range(m):
    on = 0
    switches_list = list(map(int, switches[i].split()))
    switch_num = lights[i]
    repeat_num = switches_list[0] + 1
    for j in range(1, repeat_num):
      switch_pos = switches_list[j] - 1
      on += l[switch_pos]
    if on % 2 != switch_num:
      break
    if i == m - 1:
      count += 1
print(count)

Submission status: Accepted

Solution code:
# abc128_c.py
# https://atcoder.jp/contests/abc128/tasks/abc128_c

# C - Switches /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# on と off の状態を持つ N個の スイッチと、M 個の電球があります。
# スイッチには 1 から N の、電球には 1 から Mの番号がついています。
# 電球 iは ki 個のスイッチに繋がっており、スイッチ si1,si2,...,siki のうち on になっているスイッチの個数を 2 で割った余りが piに等しい時に点灯します。
# 全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは何通りあるでしょうか。

# 制約
#     1≤N,M≤10
#     1≤ki≤N
#     1≤sij≤N
#     sia≠sib(a≠b)
#     piは 0 または 1入力は全て整数である

# 入力
# 入力は以下の形式で標準入力から与えられる。
# N M
# k1 s11 s12 ... s1k1
# :
# kM sM1 sM2 ... sMkM
# p1 p2 ... pM

# 出力
# 全ての電球が点灯するようなスイッチの on/off の状態の組み合わせの個数を出力せよ。

# 入力例 1
# 2 2
# 2 1 2
# 1 2
# 0 1

# 出力例 1
# 1

#     電球 1は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ 1,2
#     電球 2は、次のスイッチのうち奇数個が on の時に点灯します: スイッチ 2

# (スイッチ 1、スイッチ 2) の状態としては (on,on),(on,off),(off,on),(off,off) が考えられますが、
# このうち (on,on) のみが条件を満たすので、1を出力してください。

# 入力例 2
# 2 3
# 2 1 2
# 1 1
# 1 2
# 0 0 1

# 出力例 2
# 0

#     電球 1は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ 1,2
#     電球 2は、次のスイッチのうち偶数個が on の時に点灯します: スイッチ 1
#     電球 3は、次のスイッチのうち奇数個が on の時に点灯します: スイッチ 2

# 電球 2を点灯させるためには スイッチ 1 が off, 
# 電球 3 を点灯させるためにはスイッチ 2 が on である必要がありますが、この時電球 1は点灯しません。
# よって、全ての電球が点灯するようなスイッチの on/off の状態の組み合わせは存在しないので、0を出力してください。

# 入力例 3
# 5 2
# 3 1 2 5
# 2 2 3
# 1 0

# 出力例 3
# 8


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    # N = int(lines[0])
    N, M = list(map(int, lines[0].split()))
    # values = list(map(int, lines[1].split()))
    values_p = list(map(int, lines[M+1].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    valueses = list()
    for i in range(M):
        valueses.append(list(map(int, lines[i+1].split())))

    # 指定ビットのパターンを繰り返す
    result = 0
    # for i in range(2, 3):
    for i in range(2**N):
        # 評価するパターン
        pattern = format(int(format(i, 'b')), '0=' + str(N))
        log(f'pattern=[{pattern}]')
        on_cnt1 = 0
        # ランプの数分繰り返す
        for m in range(M):
            on_cnt2 = 0
            log(f'm=[{m}]')
            ss = valueses[m][1:]
            log(f'ss=[{ss}]')
            for s in ss:
                if pattern[s-1] == '1':
                    on_cnt2 += 1
                    log(f'on_cnt2=[{on_cnt2}]')
                else:
                    log(f'pattern[s-1]=[{pattern[s-1]}]')
            log(f'on_cnt2=[{on_cnt2}]')
            if on_cnt2 % 2 == values_p[m]:
                on_cnt1 += 1
                log(f'result++, on_cnt2=[{on_cnt2}]')
        if on_cnt1 == M:
            result += 1

    return [result]


# 引数を取得
def get_input_lines():
    line = input()
    N, M = list(map(int, line.split()))
    lines = list()
    lines.append(line)
    for _ in range(M+1):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['2 2', '2 1 2', '1 2', '0 1']
        lines_export = [1]
    if pattern == 2:
        lines_input = ['2 3', '2 1 2', '1 1', '1 2', '0 0 1']
        lines_export = [0]
    if pattern == 3:
        lines_input = ['5 2', '3 1 2 5', '2 2 3', '1 0']
        lines_export = [8]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines()
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

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

ans=0
for p in product(range(2),repeat=N):
  cnt1 = 0
  for i in range(M):
    cnt2 = 0
    for j in range(len(S[i])):
      if p[S[i][j]-1]==1:
        cnt2 += 1
    if cnt2 % 2== P[i]:
      cnt1 += 1
  if cnt1 == M:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
light = [list(map(int,input().split()))[1:] for _ in range(m)]
check = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    for j in range(m):
        cnt = 0
        ok = 1
        for k in light[j]:
            if i >> (k-1) & 1 == 1:cnt += 1
        if cnt%2 == check[j]:
            continue
        else:
            ok=0
            break
    ans += ok 
print(ans)

Submission status: Accepted

Solution code:
NN, MM = list(map(int,input().split()))
ARR = [list(map(int,input().split())) for l in range(MM)]
PMAP = list(map(int,input().split()))
#print(NN,MM,ARR)
switch = [[0 for j in range(NN)] for i in range(MM)]
for i in range(MM):
    for j in range(ARR[i][0]):
        switch[i][ARR[i][j+1]-1] = 1
#print(switch)

number_of_switch_on = 0
for j in range(2**NN):
#   print("bit-full-search step ", j)
    switch_on = 1
    for l in range(MM):
        checksum = 0
#        print("Checking Bulb", l+1)
        for k in range(NN):
            if (j>>k) & 1:
#               print("Switch ", k+1, " is on!")
                checksum += switch[l][k]
#        print("Checksum of switch ",l," is", checksum)
        if (checksum % 2) != PMAP[l]:
            switch_on = 0
    number_of_switch_on = number_of_switch_on + switch_on
#    print(" ")
#    print()
print(number_of_switch_on)

Submission status: Accepted

Solution code:
n = list(map(int, input().split()))
sw = []
for x in range(n[1]):
    sw.append(list(map(int, input().split())))
p = list(map(int, input().split()))
kumi = 0

for a in range(2 **n[0]):
    akari = 0
    kai = []
    for b in range(n[0]):
        if ((a >> b)& 1):
            kai.append(b+1)
    #print(kai)
    for c in range(n[1]):
        hantei = 0
        for d in range(1,sw[c][0]+1):
            if kai.count(sw[c][d]) >= 1:
                hantei +=1
        if p[c] == 0 and hantei %2 ==0:
            akari += 1
        elif p[c] == 1 and hantei %2 !=0:
            akari += 1
    if akari == n[1]:
        kumi += 1

print(kumi)

Submission status: Accepted

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

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

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

ans = 0
# i=0,1,2,...,2**N-1
# 全てのスイッチの場合の数
for i in range(2**N):
    flag = True

    # 各条件について
    for j in range(len(s)):
        # sのうち、ONになっているスイッチの数
        cnt = 0
        # 各スイッチについて
        for k in range(N):
            # そのスイッチがsに含まれる　かつ　ONになっている場合
            if (k + 1) in s[j] and ((i >> k) & 1):
                cnt += 1
        # 一つでも条件を満たさなかった時点でそのiで全点灯は不可能
        if cnt % 2 != p[j]:
            flag = False
            break

    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,m = inpm()
s = [[0] * n for i in range(m)]
for i in range(m):
    tmp = inpl()
    for j in range(len(tmp) - 1):
        s[i][tmp[j+1]-1] = 1
p = inpl()

ans = 0
for i in range(2**n):
    for j in range(m):
        cnt = 0
        for k in range(n):
            if s[j][k] == 1 and (i >> k) & 1 == 1:
                cnt += 1
        if p[j] != (cnt % 2):
            break
    else:
        ans += 1
        continue
print(ans)

Submission status: Accepted

Solution code:
#N = int(input())
n, m = map(int, input().split())
#hl = list(map(int, input().split()))
l = [list(map(int, input().split())) for i in range(m)]
pl = list(map(int, input().split()))
count=0
for i in range(2**n):
    b = bin(i)
    switch = [False for i in range(n)]
    boollist=[]
    for j in range(n):
        if ((i >> j) & 1):
            switch[j] = True
    for j in range(m):
        k = l[j][0]
        sl = l[j][1:]
        total=0
        for sij in sl:
            if switch[sij-1]:
                total+=1
        if total % 2 == pl[j]:
            boollist.append(True)
        else:
            boollist.append(False)
    if all(boollist):
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
from itertools import product
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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

    for switch in product((0,1),repeat=N):
        for i, s in enumerate(S):
            tmp = 0
            for k in s:
                tmp ^= switch[k-1]
            if tmp==P[i]:
                continue
            else:
                break
        else:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    N, M = [int(item) for item in input().split()]
    tube_to_s = [[int(item) for item in input().split()] for _ in range(M)]
    mods = [int(item) for item in input().split()]

    to_list = [[] for _ in range(M)]

    for i in range(M):
        k, *arg = tube_to_s[i]
        to_list[i] += arg
    
    res = 0
    for i in range(2**N):
        temp_s = format(i, '0{}b'.format(N))
        for j in range(M):
            temp_on_num = 0
            for item in to_list[j]:
                temp_on_num += int(temp_s[item-1])
            
            if temp_on_num % 2 == mods[j]:
                pass
            else:
                break
        else:
            res += 1

    print(res)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

ans = 0
for i in range(2**N):
  tmp = i
  flag = True
  cnt = 0
  for j in range(len(K)):
    for k in range(N):
      if ((i>>k) & 1):
        if k+1 in K[j]:
          cnt += 1
    if cnt % 2 != p[j]:
      flag = False
      break
    else:
      cnt = 0
      i = tmp
  if flag:
    ans += 1
print(ans)