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 check(setting, switch, offset):
    output = setting & switch
    count = 0
    while output > 0:
        count += output & 1
        output >>= 1
    return count % 2 == offset


N, M = map(int, input().split())
switch_state_num = 1 << N

lamp_setting = []
lamp_default = []

# ランプの設定の入力もバイナリの配列にしちゃう
for _ in range(M):
    lamp_setting_input = (list(map(int, input().split())))[1:]
    lamp_setting_single = 0
    for i in range(N):
        lamp_setting_single |= (1 if (i + 1) in lamp_setting_input else 0) << i
    lamp_setting.append(lamp_setting_single)

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

ans = 0

# ループの最大は所詮 2**10→1024。桁が2つ3つ増えたってゴリ押し可能。
for switch_state in range(switch_state_num):
    suc = True
    for lamp_index in range(M):
        if not check(lamp_setting[lamp_index], switch_state, lamp_default[lamp_index]):
            suc = False
            break
    if suc:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
kss = []
for i in range(1, M+1):
    ks = list(map(int, input().split()))
    kss.append(ks)
biases = list(map(int, input().split()))

active_switches = set()
for i in range(0, M):
    # でんきゅうiがつくかどうか
    for j in range(1, kss[i][0] + 1):
        active_switches.add(kss[i][j])

import itertools

def is_lit(m, s, sw, b):
    total = b
    for val in s:
        if val in sw:
            total += 1
    return total%2 == 0


def is_all_lit(sw):
    return all([is_lit(ks[0], ks[1:], sw, biases[idx]) for idx, ks in enumerate(kss)])

answer = 0
for i in range(0, len(active_switches)+1):
    c = itertools.combinations(active_switches, i)
    result = map(is_all_lit, c)
    answer += sum(result)

import math
answer *= int(math.floor(math.pow(2, N - len(active_switches))))

print(answer)

Submission status: Accepted

Solution code:
# coding: utf-8

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

switch = [[0] * N for _ in range(2 ** N)]
for i in range(2 ** N):
    for j in range(N):
        switch[i][j] = (i & (1 << j)) >> j
counter = 0
for sw in switch:
    ons = 0
    for i in range(M):
        temp = []
        for si in s[i]:
            temp.append(sw[si - 1])
        if sum(temp) % 2 == p[i]:
            ons += 1
    if ons == M:
        counter += 1

print(counter)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = []
for i in range(m):
    _, *s = [int(x)-1 for x in input().split()]
    l.append(s)
p = [int(x) for x in input().split()]

ans = 0
for i in range(2**n):
    d = 0
    q = i
    r = [0] * m
    while q > 0:
        s = q & 1
        if s == 1:
            for j in range(m):
                if d in l[j]:
                    r[j] += 1
        d += 1
        q >>= 1
    c = 0
    for j in range(m):
        if p[j] == (r[j] % 2):
            c += 1
    if c == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=(int(i) for i in input().split())
denkyu=[]
for i in range(M):
    denkyu.append([int(i) for i in input().split()])
p=[int(i) for i in input().split()]
import copy
swi=[[0],[1]]
for _ in range(N-1):
    swi1=copy.deepcopy(swi)
    swi2=copy.deepcopy(swi)
    for i in range(len(swi)):
        swi1[i].append(0)
        swi2[i].append(1)
    swi=swi1
    swi.extend(swi2)


answer=0
for s in swi:
    allon=1
    for i in range(M):
        on=0
        for j in range(1,denkyu[i][0]+1):
            if s[denkyu[i][j]-1]==1:
                on+=1
        if on%2!=p[i]:
            allon=0
            break
    if allon==1:
        answer+=1      
print(answer)

Submission status: Accepted

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

ans = 0
sw = [0] * N
for i in range(2 ** N):
    state = [0] * M
    S = list(bin(i))
    S = S[2:]
    while len(S) < N:
        S = ['0'] + S
    
    for j in range(N):
        sw[j] = int(S[N-1-j])
    for j in range(M):
        cnt = 0
        for k in ks[j][1:]:
            if sw[k-1] == 1:
                cnt += 1
        if cnt % 2 == p[j]:
            state[j] = 1
            
    if not(0 in state):
        ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def main():
    temp = input().split()
    N = int(temp[0])
    M = int(temp[1])
    k = [] #tukawanai
    s = []
    for m in range(M):
        temp = input().split()
        k.append(int(temp[0]))
        s.append([])
        for x in temp[1:]:
            s[m].append(int(x)-1)
    p = []
    temp = input().split()
    for x in temp:
        p.append(int(x))
    res = 0
    for i in range(2**N):
        suitti = ret_suitti(i,N)
        if(hantei(suitti, s, p)):
            res += 1
    print(res)

def ret_suitti(i,N):
    suitti = []
    shou = i
    for n in range(N):
        amari = shou % 2
        shou = shou // 2
        if(amari == 0):
            suitti.append(0)
        else:
            suitti.append(1)
    return suitti

def hantei(suitti, s, p):
    M = len(p)
    flag = 1
    for m in range(M):
        on_suitti = 0
        for x in s[m]:
            if(suitti[x] == 1):
                on_suitti += 1
        if(on_suitti % 2 != p[m]):
            flag = 0
    if(flag == 1):
        return True
    else:
        return False

if __name__ == "__main__":
    main()

Submission status: Accepted

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

S = [[] for _ in range(N)]
for i in range(M):
    k,*s = [int(j) for j in input().split()]
    for j in s:
        S[j-1].append(i)

p = [int(i) for i in input().split()]
ans = 0
for i in range(2**N):
    tmp = [0]*M
    for j in range(N):
        if (i >> j) & 1:
            for z in S[j]:
                tmp[z] = tmp[z]^1

    if p == tmp:
        ans += 1
print(ans)

Submission status: Accepted

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

patterns = []
for i in range(2**N):
    l = list(map(int,list(format(bin(i)[2:]))))
    l = [0 for _ in range(N-len(l))] + l
    patterns.append(l)

for i in range(M):
    tmp_patterns = []
    for pat in patterns:
        tmp_sum = 0
        for s in s_list[i]:
            tmp_sum += pat[s-1]
        if tmp_sum%2 == p_list[i]:
            tmp_patterns.append(pat)
    patterns = tmp_patterns

print(len(patterns))

Submission status: Accepted

Solution code:

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

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

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

numlist = []
for i in range(2**N):
    numbin = str(bin(i+1024))
    numbin = numbin[-N:]
    numlist.append(numbin)

answer = 0
for j in numlist:
    # スイッチ状態がjのとき
    flag = True
    for i in range(M):
        # i番目のルールについて
        total = 0
        for k in slist[i]:
            total += int(j[-k])
        if(total%2 != plist[i]):
            flag = False
            break
    if(flag==True):
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
N, M = map(int, input().split(" "))
s_table = []
for m in range(M):
    line = list(map(int, input().split(" ")))
    s_table.append(line[1:])

p_list = list(map(int, input().split(" ")))
patterns = 0
for state in range(2 ** N):
    s_bits = [bool(state & (2 ** i)) for i in range(N)]
    ramps = 0
    for p, switches in zip(p_list, s_table):
        n = 0
        for s in switches:
            n += s_bits[s - 1]
        if n % 2 == p:
            ramps += 1

    if ramps == M:
        patterns += 1

print(patterns)

Submission status: Accepted

Solution code:
from itertools import product
n, m = map(int,input().split())
ks = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
cnt = 0
for pr in product([0, 1], repeat=n):
    pr = list(pr)
    for i, a in enumerate(ks):
        k = a[0]
        s = a[1:]

        c = 0
        for j in range(k):
            c += pr[s[j]-1]
        if c % 2 == p[i]:
            continue
        else:
            break
    else:
        cnt += 1
print(cnt)

Submission status: Accepted

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

s = list()

for m in range(M):
    ks = list(map(int, input().split()))
    zz = [0] * 10
    for u in range(1, len(ks)):
        zz[ks[u] - 1] = 1
    s.append(zz)

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

ans = 0
for z in range(2 ** N):
    y = [0] * 10
    for x in range(10):
        y[x] = z >> x & 1
    b = True
    for m in range(M):
        w = 0
        for q in range(10):
            w = w + (s[m][q] & y[q])
        b = b & ((w % 2) == p[m])
    if b == True:
        ans = ans + 1

print(ans)

Submission status: Accepted

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

ans = 0

import itertools
for i in itertools.product([0,1], repeat=N):
  righted = 0
  for iter, j in enumerate(ks):
  #  print(iter, j )
    cnt = 0
    for k in range(1,len(j)):
      cnt += i[j[k]-1]
    if cnt % 2 == p[iter]:
      righted += 1
  if len(ks) == righted:
    ans += 1
    
print(ans)

Submission status: Accepted

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

cnt = 0
for n_i in range(2**n):
    s_now = bin(n_i)[2:].zfill(n)
    #print(s_now)
    next_m = False

    for m_i in range(m):
        sum_tmp = 0
        for s_i in s[m_i]:
            sum_tmp += int(s_now[int(s_i)-1])
        #print(sum_tmp,p[m_i])
        if sum_tmp % 2 != p[m_i]:
            next_m = True
            break
    if next_m:
        continue
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
# 全通り
ary = []
for i in range(2 ** N):
    ary.append((bin(i)[2:].zfill(N)))
# 残り入力
ary2 = []
for i in range(M):
    kS = list(map(int, input().split()))
    ary2.append(kS)
P = list(map(int, input().split()))
# 解く
cnt = 0
for i in range(2 ** N):
    flg = 0
    for j in range(M):
        tot = 0
        for k in range(len(ary2[j])-1):
            tot += int(ary[i][ary2[j][k+1]-1])
        if tot % 2 != P[j]:
            flg = 1
            break
    if flg == 0:
        cnt += 1
print(cnt)

Submission status: Accepted

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

count = 0
onoff = [0 for _ in range(N)]
for switch in range(1<<N):
    res = switch
    for ind in range(N):
        onoff[ind] = res&1
        res = res>>1
    
    on = 0
    for denkyu in range(M):
        su = 0
        for sw in s[denkyu]:
            su = su + onoff[sw-1]
        if p[denkyu] == (su % 2):
            on = on + 1
    
    if on == M:
        count = count + 1

print(count)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
n, m = [int(i) for i in input().split()]
A = np.zeros((m, n), dtype = int)
for i in range(m):
    tmp = [int(i) for i in input().split()]
    for j in range(1, len(tmp)):
        A[i][tmp[j]-1] = 1
p = np.array([int(i) for i in input().split()])
ans = 0

lst = list(itertools.product([0,1], repeat = n))
for i in range(len(lst)):
    tmp = np.remainder(np.dot(A, np.array(lst[i])), 2)
    if np.array_equal(tmp, p):
        ans += 1
print(ans)

Submission status: Accepted

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

count = 0
for l in range(2**N):
    flag = 1
    for t in range(m):
        sigma = 0
        for j in range(k[t]):
            sigma += l // (2**(s[t][j]-1))
        if sigma % 2 !=p[t]:
            flag =0
            break
    count += flag
print(count)

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
Kl = []
for i in range(M):
    Kl.append(list(map(int,input().split())))
P = list(map(int,input().split()))
ans = 0

for i in range(2**N):
    onoff = [False for i in range(M)]
    b = format(i, 'b').zfill(N)
    for k in range(M):
        cnt = 0
        for l in range(Kl[k][0]):
            if b[Kl[k][l+1]-1] == "1":
                cnt += 1

        if int(cnt % 2) == int(P[k]):
            onoff[k] = True
    if False not in onoff:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
def read():
    N, M = list(map(int, input().strip().split()))
    S = [-1] * M
    for i in range(M):
        inputs = list(map(int, input().strip().split()))
        S[i] = sw_to_seq(inputs[0], inputs[1:])
    P = list(map(int, input().strip().split()))
    return N, M, S, P


def sw_to_seq(k, s):
    s_seq = 0
    for i in range(k):
        bit = 1 << (s[i] - 1)
        s_seq += bit
    return s_seq


def count_sw_on(s_seq, i):
    sw_on = s_seq & i
    count = 0
    while sw_on > 0:
        count += (sw_on & 1)
        sw_on >>= 1
    return count


def solve(N, M, S, P):
    count_all_sw_on = 0
    for i in range(1 << N):
        num_sw_on = 0
        for j in range(M):
            if count_sw_on(S[j], i) % 2 == P[j]:
                num_sw_on += 1
        if num_sw_on == M:
            count_all_sw_on += 1
    return count_all_sw_on


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Accepted

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

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

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

t = [False for i in range(n)]


_ = True
counter = 0
while(_):
    flag = True
    hantei = True



    for e,ki in enumerate(k):
        tmp = False
        for i in range(1,ki[0]+1):
            if t[ki[i]-1] == tmp:
                tmp = False
            else:
                tmp = True

        if p[e] != tmp:
            hantei = False
    if hantei:
        counter+=1


    for i in range(n):
        if flag and t[i]:
            t[i] = not t[i]
        elif flag:
            t[i] = not t[i]
            flag = False

    if flag:
        break

print(counter)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
skss = []
for _ in range(M):
    k, *sks = map(int, input().split())
    skss.append(sks)
pMs = list(map(int, input().split()))

count = 0
for i in range(2 ** N):
    pMstmp = pMs[:]
    for j, b in enumerate(format(i, '0' + str(N) + 'b')):
        if b == '0':
            continue
        for k, sks in enumerate(skss):
            if j + 1 in sks:
                pMstmp[k] ^= 1
    if sum(pMstmp) == 0:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
range(M)
switches = [[int(i) for i in input().split()] for _ in range(M)]
P = [int(i) for i in input().split()]
count=0
for i in range(2**N):
    ss = [int(i) for i in list(bin(i))[2:]]
    ss = [0] * (N - len(ss)) + ss
    t = True
    for e, switch in enumerate(switches):
        a = P[e]
        if len([ss[i-1] for i in switch[1:] if ss[i-1]==1]) %2 !=a:
            t = False
            break
    if t:
        count +=1

print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import itertools

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

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

switch_pattern_list = []
for i in itertools.product((0,1), repeat=N):
    switch_pattern_list.append(i)

output = 0

for switch_pattern in switch_pattern_list:
    for i in range(len(switch_list)):
        on = 0
        for switch_number in switch_list[i]:
            if switch_pattern[switch_number - 1] == 1:
                on += 1
        if on % 2 != joken_list[i]:
            break
        if i == len(switch_list) - 1:
            output += 1

print (output)

Submission status: Accepted

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

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

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

res = 0
for i in range(2**n):
    cou = [0 for k in range(m)]
    binary = '0'*(n - len(bin(i)[2:])) + bin(i)[2:]
    for j in range(n):
        if binary[j] == '1':
            for k in range(len(lis)):
                if j + 1 in lis[k]:
                    cou[k] += 1 
    if all((cou[x] - plist[x])%2 == 0 for x in range(m)):
        res += 1
print(res)

Submission status: Accepted

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

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

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


def light_is_on(light_index, case):
    switch_list = switch_list_for_light_index[light_index]
    switch_on_count = 0
    for switch in switch_list:
        switch_on_count += int(case[switch - 1])
    if switch_on_count % 2 == p[light_index]:
        return True
    else:
        return False

answer = 0

for case_num in range(2**n):
    case = bin(case_num)[2:].zfill(n)
    suc_num = 0
    for light_index in range(m):
        if light_is_on(light_index, case) == True:
            suc_num += 1
        else:
            break
    if suc_num == m:
        answer += 1

print(answer)

Submission status: Accepted

Solution code:
from itertools import product

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


ks = [list(map(lambda x: x - 1, list(_)[1:])) for _ in ks]

ans = 0
for state in product(range(2), repeat=n):
    for pi, si in zip(p, ks):
        cum = 0
        for sij in si:
            cum += state[sij]
        if cum % 2 != pi:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
kss = []
for _ in range(M):
    kss.append(list(map(int,input().split())))
p = list(map(int,input().split()))
answer = 0
for i in range(1 << N):
    members = {}
    for j in range(N):
    
        if (i>>j)&1 == 1:
            # 部分集合にメンバーを追加していく
            members[j+1] = 1
        else:
            members[j+1] = 0
    for k in range(M):
        howManySwitchesOn = 0
        for l in range(len(kss[k])):
            if l == 0:
                continue
            if members[kss[k][l]] == 1:
                howManySwitchesOn += 1
        if howManySwitchesOn%2 != p[k]:
            break
    else:
        answer += 1
    
print(answer)

Submission status: Accepted

Solution code:
import numpy as np

def add1(s, i = -1):
    if s[i] == 0:
        s[i] = 1
        return s
    else:
        s[i] = 0
        return add1(s, i-1)
    
n, m = map(int, input().split())

k = []
s = []

for i in range(0, m):
    ki, *si = map(int, input().split())
    k.append(ki)
    s.append(si)

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

sw = np.zeros(n)

ons = 0
ans = 0
sums = 0

for i in range(0, 2**n):
    for j in range(0, m):
        for l in s[j]:
            ons += sw[l-1]
        if ons % 2 == p[j]:
            sums += 1
        ons = 0
    if sums == m:
        ans += 1
    sums = 0
    if i != 2**n - 1:
        sw = add1(sw)


print(ans)

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

def f(T, X, S, k):
    if k == len(T):
        return 1 if S == X else 0

    return f(T, X, S, k+1) + f(T, X, S^T[k], k+1)
        

    

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

    T = [0]*N
    for i in range(M):
        L = list(map(int, input().split()))
        for sw in L[1:]:
            T[sw-1] |= (1 << i)

    X = 0
    P = map(int, input().split())
    for i, p in enumerate(P):
        X |= ((1<<i) if p == 1 else 0)



    print(f(T, X, 0, 0))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ks = [list(map(int, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
c = 0
for i in range(2**n):
  li = []
  flag = False
  for j in range(n):
    if ((i>>j)&1):
      li.append(j+1)
  for j in range(m):
    s = set(li)
    ss = set(ks[j])
    s = s & ss
    if len(s) % 2 == p[j]:
      flag = True
    else:
      flag = False
      break
  if flag:
    c += 1
print(c)

Submission status: Accepted

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

ans = 0
for num in range(2 ** N):
    bit = str(bin(num)[2:]).zfill(N)
    breakFlag = False
    for i_1, sList in enumerate(sLists):
        count = 0
        for i_2, b in enumerate(list(bit), start=1):
            if i_2 in sList and b == "1":
                count += 1
        if count % 2 != pList[i_1]:
            breakFlag = True
            break
    if not breakFlag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())

lights = []

for _ in range(M):
    light = np.zeros(N + 1, dtype='int32')
    line = list(map(int, input().split()))
    k = line[0]
    switches = line[1:]
    for s in switches:
        light[s] = 1
    lights.append(light)

p_list = list(map(int, input().split()))
for i in range(M):
    lights[i][0] = p_list[i]

result = 0
for S in range(2**N):
    switch_state = np.array([1] + list(map(int, list(('0000000000' + bin(S)[2:])[-N:]))))
    success = True
    
    for l in lights:
        if sum(l*switch_state) % 2 != 0:
            success = False
            break

    if success:
        result += 1

print(result)

Submission status: Accepted

Solution code:
import sys
import itertools

def intinput(): return map(int,sys.stdin.readline().split())

n,m=intinput()
l = []
for i in range(m):
    l.append(list(map(lambda e:e-1,list(intinput())[1:])))
p = list(intinput())
x = list(itertools.product((0,1),repeat=n))
cnt=0
for i in x:
    r=0
    f=0
    for j in l:
        if sum(list(map(lambda e:i[e],j)))%2!=p[r]:
            f=1
            break
        r+=1
    if f==0:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import collections
import copy


class Node(object):

  def __init__(self, n, m):
    self.lamps = [[0] * n for _ in range(m)]
    self.status = [[0, 0] for _ in range(m)]
    self.index = 0

  def create_children(self):
    children = []

    child0 = copy.deepcopy(self)
    child1 = copy.deepcopy(self)

    for i in range(len(self.status)):
      child0.status[i][0] -= child0.lamps[i][self.index]
      child1.status[i][0] -= child1.lamps[i][self.index]
      child1.status[i][1] += child1.lamps[i][self.index]

    child0.index += 1
    child1.index += 1

    if child0.is_valid():
      children.append(child0)

    if child1.is_valid():
      children.append(child1)

    return children

  def is_valid(self):
    for r, v in self.status:
      if r == 0 and v % 2 == 1:
        return False

    return True


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

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

    for j in v:
      root.lamps[i][j - 1] = 1

    root.status[i][0] = len(v)

  for i, v in enumerate(map(int, input().split())):
    root.status[i][1] = v

  stack = collections.deque()
  stack.append(root)
  count = 0

  while len(stack) != 0:
    node = stack.pop()

    children = node.create_children()

    for child in children:
      if child.index == n:
        count += 1
      else:
        stack.append(child)

  print(count)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 26 20:56:00 2019

@author: Yamazaki Kenichi
"""

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):
    t = '{:010b}'.format(i)
    flg = True
    for j in range(M):
        tmp = 0
        for k in range(ks[j][0]):
            tmp += int(t[-ks[j][k+1]])
#        print(i,j,t,tmp,ans)
        if tmp%2 == p[j]:
            continue
        else:
            flg = False
            break
#    print(i,j,t,tmp,ans,flg)
    if flg:
        ans += 1

            
print(ans)

Submission status: Accepted

Solution code:
def multy(a,b):
	c = 0
	for i in range(len(a)):
		c += a[i]*b[i]
	return c
N,M = map(int, raw_input().split())
ks = []
for i in range(M):
	ks2 = map(int, raw_input().split())
	ks.append(ks2)
pm = map(int, raw_input().split())
plist = []
for i in ks:
	t = [0]*N
	ini = 1
	for j in i:
		if(ini == 1):
			ini = 0
			continue
		else:
			t[j-1] = 1
	plist.append(t)
slist = []
for i in range(2**N):
	t = []
	for j in range(N):
		t.append(i%2)
		i = i/2
	slist.append(t)
r = 0
for p in plist:
	s2 = []
	for s in slist:
		if(multy(p,s)%2 == pm[r]):
			s2.append(s)
	r = r+1
	slist = s2
print(len(slist))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from collections import defaultdict
N, M = list(map(int, input().split()))
switch = dict()
for i in range(M):
    inputs = list(map(int, input().split()))
    k, list_s = inputs[0], inputs[1:]
    switch[i] = list_s
    
ps = list(map(int, input().split()))

ans = 0
for i in range(2**N):
    ok = True
    # print(i)
    on_s = []
    for idx, s in enumerate(bin(i)[::-1]):
        if s == 'b':
            break
        if s == '1':
            on_s.append(idx+1)
    for k, v in switch.items():
        on_cnt = 0
        for num in v:
            if num in on_s:
                on_cnt += 1
        if on_cnt % 2 == ps[k]:
            continue
        else:
            ok = False
            break
    if ok:
        ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 26 19:03:42 2019
ABC128C
@author: maezawa
"""
import itertools
n, m = list(map(int, input().split()))
lamp = []
for _ in range(m):
    kin = list(map(int, input().split()))
    kin.pop(0)
    lamp.append(kin)
p = list(map(int, input().split()))
cntall = 0
for kbin in itertools.product(range(2), repeat=n):
    for i in range(m):
        cnt = 0
        for j in lamp[i-1]:
            if kbin[j-1] == 1:
                cnt += 1
        if cnt % 2 != p[i-1]:
            #print(j,i-1)
            break
    else:
        cntall += 1
        #print(kbin)

print(cntall)

Submission status: Accepted

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

p=list(map(int,input().split()))
b=0b0000000000
cnt=0
while b < 0b1<<N:
    s = str(bin(b))[2:].zfill(N)
    for i in range(M):
        sum = 0
        for j in k[i]:
            if s[N-j]=="1":
                sum += 1
        if sum%2!=p[i]:
            break
    else:
        cnt+=1
    b+=1
print(cnt)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n, m = map(int, input().split())
switch_comb = itertools.product((0, 1), repeat=n)
switch_arr = np.array(list(switch_comb))
res = 0
light_list = []
for i in range(m):
  s_list = list(map(int, input().split()))[1:]
  s_list = [i - 1 for i in s_list]
  light_list.append(s_list)
print()
flg_list = list(map(int, input().split()))
for j, l in enumerate(light_list):
  ans = flg_list[j]
  switch_arr = switch_arr[(switch_arr[:, l].sum(axis=1) % 2) == ans, :]
  if switch_arr.shape[0] == 0:
    break
print(switch_arr.shape[0])

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
data = [0,1]
state_list = list(itertools.product(data, repeat=N))
l = [[int(x) for x in input().split()] for i in range(M)]
p = list(map(int,input().split()))
ans = 0
for i in range(2**N):
  k_count = 0
  for j in range(M):
    tmp = l[j][0]
    tmp_s = l[j][1:]
    count = 0
    for k in range(tmp):
      if state_list[i][tmp_s[k]-1] == 1:
        count += 1
    if count%2 == p[j]:
      k_count += 1
  if k_count == M:
    ans += 1
print(ans)

Submission status: Accepted

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

pList = list(input().split())
result = 0
was = []
cases = list(itertools.product(['1','0'], repeat=N))
for case in cases:
    light = 0
    for p,x in zip(pList,ks):
        k = x[0]
        s = x[1:]
        oncount = 0
        for c in s:
            if case[int(c)-1] == '1':
                oncount += 1
        if oncount%2 == int(p):
            light += 1
    if light == M:
        result += 1
print(result)

Submission status: Accepted

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

k = []
k_bit = []

for i in range(M):
    arr = list(map(int, input().split()))
    arr.pop(0)
    k.append(arr)
    val = 0
    for e in arr:
        val += 2 ** (e - 1)
    k_bit.append(val)

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

result = 0

for i in range(2 ** N):
    judge = True
    for j in range(M):
        ret = i & k_bit[j]
        on = 0
        for k in range(10):
            on += (ret >> k) % 2
        on = on % 2
        if (on != p[j]):
            judge = False
    if (judge):
        result += 1

print(result)