Problem:


Score : 300 points

Problem Statement

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

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

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

Constraints

1 \leq N, M \leq 10

1 \leq k_i \leq N

1 \leq s_{ij} \leq N

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

p_i is 0 or 1.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 2
2 1 2
1 2
0 1

Sample Output 1

1

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

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

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

Sample Input 2

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

Sample Output 2

0

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

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

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

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

Sample Input 3

5 2
3 1 2 5
2 2 3
1 0

Sample Output 3

8



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


Sample output:
1

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
k=[]
for i in range(m):
    k.append(list(map(int,input().split()))[1:])
p=list(map(int,input().split()))
a=0
for i in range(2**n):
    i=list(map(int,list(bin(i)[2:].zfill(n))))
    for j in range(m):
        x=p[j]
        for l in k[j]:
            x^=i[l-1]
        if x==1:break
    else:a+=1
print(a)

Submission status: Accepted

Solution code:
#c
n,m = map(int,input().split())
res = 0

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

#sのX桁目が1ならX個目のスイッチがON
for s in range(2**n):
    judge = True
    for i in range(m):
        cnt = 0
        for j in range(1,len(q[i])):
            w = q[i][j]
            if s>>(w-1) &1 == 1:
                cnt += 1
        if cnt % 2 != p[i]:
            judge = False
    if judge:
        res += 1
print(res)

Submission status: Accepted

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

ks = np.array([list(map(int,input().split()[1:])) for _ in range(m)])

ss = np.array(list(map(int,input().split())))

def ans(n):
    return(b1(n,np.zeros(m))+b0(n,np.zeros(m)))

def b0(n,t):
    global ss
    if n == 0:
        return 0
    return b0(n-1,t)+b1(n-1,t)

def b1(n,t):
    global ks
    global ss
    t = t + np.array([int(n in k) for k in ks])
    if n == 0:
        return all([i%2==s for i,s in zip(t,ss)])
    return b0(n-1,t)+b1(n-1,t)

print(ans(n))

Submission status: Accepted

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

def is_on(n, idx):
    bin_string = str(bin(n)[2:]).zfill(N)
    return bin_string[idx - 1]

num = 0
for n in range(2 ** N):
    all_flag = True
    for p, lis in zip(p_list, lists):
        flag = (sum([is_on(n, l) == '1' for l in lis]) % 2) == p
        all_flag = all_flag & flag
    num += all_flag
print(num)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
x = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2 ** n):
    bag = []
    cnt = 0
    for j in range(n):  
        if ((i >> j) & 1):  
            bag.append(True)
        else:
            bag.append(False)
    for l in range(m):
        res = 0
        for h in x[l][1:]:
            if bag[h-1]:
                res += 1
        if res%2!=p[l]:
            break
        else:
            cnt += 1
    if cnt==m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#   ABC128 D


def make_switch_pattern(N, M):
    for i in range(2**N):
        tmp_lst = [0]*N
        for j in range(N):
            tmp_lst[j] = i % 2
            i = int(i/2)
        tmp_lst.reverse()
        switch_pattern = tuple(tmp_lst)
        yield switch_pattern


def all_light_41_pi(switch_pattern, light_lst, pi_lst):
    for i in range(len(light_lst)):
        switches = light_lst[i]
        pi = pi_lst[i]
        on_count = 0
        for k in switches:
            if switch_pattern[k-1] == 1:
                on_count += 1
        on_count %= 2
        if on_count != pi:   #   条件を満たさない時
            return False
    return True


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

light_lst = []  #   ライトについているスイッチのタプル のリスト
for i in range(M):
    tmp_lst = list(map(int, input().split()))
    tmp_tple = tuple(tmp_lst[1:])
    light_lst.append(tmp_tple)

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

count = 0
for switch_pattern in make_switch_pattern(N, M):
    if all_light_41_pi(switch_pattern, light_lst, pi_lst):
        count += 1

print(count)

Submission status: Accepted

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

ps = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    f = True
    for k, p in zip(ks,ps):
        o =  0
        for j in k:
            if (i >> j-1)&1:
                o += 1
        if o%2 != p:
            f = False
#        print(o)
    if f :
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N, M = map( int, input().split())
K = [ list( map( int, input().split())) for _ in range(M)]
P = list( map( int, input().split()))
ans = 0
for p in product( range(2), repeat = N):
    t = 1
    for i in range(M):
        cnt = 0
        for j in range(1, K[i][0]+1):
            if p[K[i][j]-1] == 1:
                cnt += 1
        if cnt%2 != P[i]:
            t = 0
            break
    if t == 1:
        ans += 1
print( ans)

Submission status: Accepted

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

ans = 0

for i in range(2 ** n):
  pat = []
  t = 0
  for j in range(n):
    if (i >> j) & 1:
      pat.append(True)
    else:
      pat.append(False)
  for k in range(m):
    cnt = 0
    for l in s[k][1:]:
      if pat[l-1]:
        cnt += 1
    if cnt % 2 == p[k]:
      t += 1
  if t == m:
    ans += 1
    
print(ans)

Submission status: Accepted

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

ans=0

for i in range(2**n):
    pat=[]
    t=0
    for j in range(n):
        if (i>>j)&1:
            pat.append(True)
        else:
            pat.append(False)
    for k in range(m):
        cnt=0
        for l in s[k][1:]:
            if pat[l-1]:
                cnt+=1
        if cnt%2==p[k]:
            t+=1
    if t==m:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
lists = []
for _ in range(M):
    lists.append(list(map(int, input().split()))[1:])
p_list = list(map(int, input().split()))
num = 0
len_m = N
for n in range(2 ** N):
    flag = True
    for p, lis in zip(p_list, lists):
        flag = int(flag) * int((sum([str(bin(n)[2:]).zfill(len_m)[l - 1] == '1' for l in lis]) % 2) == p)
    num += flag
print(num)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
s = []
p = []
for i in range(M):
    _, *si = map(lambda x:int(x)-1, input().split())
    s.append(si)
c = list(map(int, input().split()))
# print(s)
ans = 0
for pattern in range(2**N):
    p = []
    for keta in range(N):
        if pattern & (1<<keta) > 0:
            p.append(1)
        else:
            p.append(0)
    # print("p:",p)

    for m in range(M):
        cnt = 0
        for si in s[m]:
            cnt += p[si]
        # print(m,cnt)
        if cnt%2 != c[m]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product


def count(ss, ns, ps):
    for i, s in enumerate(ss):
        sum_s = sum([ns[_s - 1] for _s in s])
        if sum_s % 2 != ps[i]:
            return 0
    return 1


n, m = list(map(int, input().split(" ")))
ks = []
ss = []
for _ in range(m):
    k, *s = list(map(int, input().split(" ")))
    ks.append(k)
    ss.append(s)
ps = list(map(int, input().split(" ")))

ns_list = list(product([0, 1], repeat=n))
ans = 0
for ns in ns_list:
    ans += count(ss, ns, ps)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

ans = 0
for i in range(2**n):
    i = list(reversed("{:010b}".format(i)))
    f = True
    for k,s in zip(ks,ss):
        o = 0
        for j in k:
            if i[j-1] == "1":
                o+=1
        if o%2 != s:
            f = False
    if f:
        ans+=1
print(ans)

Submission status: Accepted

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

ans=0
for t in range(2**N):
    tmp=[(t>>s)&1 for s in range(N)]
    light=True
    for i in range(M):
        cnt=0
        for j in range(len(l[i])):
            if tmp[l[i][j]-1]==1:
                cnt+=1
        if cnt%2 != p[i]%2:
            light=False
    if light:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def switch_on_off(n, keta):
    bin_str = format(n, '0{}b'.format(keta))
    return list(bin_str)

def check_light(n, N, s, index, P):
    switch = switch_on_off(n, N)
    sum = 0
    for v in s:
        sum += int(switch[int(v) - 1])
    if sum % 2 == P[index]:
        return 1
    return 0

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


ans = 0
for n in range(2 ** N):
    sum = 0
    for index, s in enumerate(S):
        sum += check_light(n, N, s, index, P)
    if sum == M:
        ans += 1

print(ans)

Submission status: Accepted

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

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

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

ans = 0

for bit in range(1 << N) :
    A = []
    for k in range(N) :
        if bit & (1 << k) :
            A.append(k)
    for i in range(len(S)) :
        cnt = 0
        for s in S[i] :
            if s in A :
                cnt += 1
        if (cnt % 2) != P[i] :
            break
    else :
        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.pop(0))
        s.append(tmp)
p = list(map(int, input().split()))
ans = 0

for bn in range(2**n):
        bn = str(bin(bn))[2:].zfill(n)
        bright = 0
        for i in range(m):
                p_exp = 0
                for j in range(n):
                        #print("switch num",j, "bn", bn) 
                        if (j+1 in s[i]) and (bn[j] == '1'): p_exp += 1
                if p_exp%2 == p[i]: bright += 1
                #print("on botton", p_exp)
        #print("bright light", bright)
        if bright == m: ans += 1
print(ans)

Submission status: Accepted

Solution code:
#スイッチ、電球
n,m=list(map(int,input().split()))
con=[]
for i in range(m):
    tmp=list(map(int,input().split()))
    con.append(tmp[1:])
p=list(map(int,input().split()))

#2進に変換
def convert(x):
    li=[]
    for i in range(1,n+1):
        li.append(x%2)
        x=x//2
    return li
ans=0
for i in range(2**n):
    sw=convert(i)
    flg=True
    for j in range(m):
        lit=p[j]
        for k in con[j]:
            if sw[k-1]==1:
                if lit==1:
                    lit=0
                else:
                    lit=1
        if lit==1:
            flg=False
            break
    if flg:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import bisect
from operator import itemgetter
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()
K = [IL()[1:] for i in range(M)]
p = np.array(IL())

switch = np.array([[0]*M for i in range(N)])
for i in range(M):
    while K[i]:
        num = K[i].pop()
        switch[num-1][i] = 1

ans = 0
for i in range(1 << N):
    cnt = np.array([0]*M)
    for j in range(N):
        if ((i >> j) & 1) == 1:
            cnt += switch[j]
    else:
        if (p == (cnt%2)).all():
            ans += 1
print(ans)

Submission status: Accepted

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

from sys import stdin


def bit_count(x):
    return bin(x).count("1")

def bit_exchange(x):
    return 2 ** (x-1)

all_switch_list=[]
clear_list=[]


N, M = [int(x) for x in stdin.readline().rstrip().split()]

for i in range(M):
    switch_list = [int(x) for x in stdin.readline().rstrip().split()]
    bin_s_list = 0
    for j in range(switch_list[0]):
        # j+1 
        bin_s_list = bin_s_list | bit_exchange(switch_list[j+1])

    
    all_switch_list.append(bin_s_list)
remainder = [int(x) for x in stdin.readline().rstrip().split()]

#for i in range(bit_exchange(N+1)):

clear_list = list(range(bit_exchange(N+1)))
for i in range(M):
    for j in range(bit_exchange(N+1)):
        count = j & all_switch_list[i]
        if bit_count(count) % 2 != remainder[i]:
            try:
                clear_list.remove(j)
            except:
                pass

print(len(clear_list))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
switches = []
for i in range(M):
    _, *switch = map(int, input().split())
    switches.append(switch)
condition = [int(x) for x in input().split()]
cnt = 0
for status in range(2 ** N):
    satisfied = False
    for i, switch in enumerate(switches):
        total_status = sum([1 & (status >> (s - 1)) for s in switch])
        if condition[i] != total_status % 2: break
        elif i == len(switches) - 1: satisfied = True
    if satisfied: cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
#C問題
N, M=map(int, input().split())

s_list=[]
for i in range(M):
    s_list.append(list(map(int, input().split())))
    
bit_list =[]
for i in range(2**N):
    bit_list.append(bin(i)[2:].zfill(N))
p_list = list(map(int, input().split()))

delete_list = []
for i in range(M):
    count = 0
    for j in range(2**N):
        count = 0
        for k in range(s_list[i][0]):
            if int(bit_list[j][s_list[i][k+1]-1]) == 1:
                count +=1
        if count % 2 != p_list[i]:
            delete_list.append(bit_list[j])
bit_list =[i for i in bit_list if i not in delete_list]
print(len(bit_list))

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
ks=[]
for m in range(M):
    k,*s=list(map(int,input().split()))
    ks.append(s)
pm=list(map(int,input().split()))
ct=0
for i in range(2**N):
    bf="{:010b}".format(i)[::-1]
    allok=True
    for m in range(M):
        if not allok:break
        sm=0
        for s in ks[m]:
            sm+=int(bf[s-1])
        if sm%2!=pm[m]:
            allok=False
            break
    if allok:
        ct+=1
print(ct)

Submission status: Accepted

Solution code:
n,m=(int(i) for i in input().split())
b=[]
v=[]
for i in range(m):
  a=[]
  for j in input().split():
    a.append(int(j))
  b.append(a[1:])
for j in input().split():
  v.append(int(j))
r=0
for i in range(2**n):
  c=i
  t=[0 for l in range(m)]
  for j in range(n):
    if c-(c//2)*2==1:
      for k in range(m):
        if j+1 in b[k]:
          t[k]=(t[k]-1)**2
    c=c//2
  if t==v:
    r=r+1
print(r)

Submission status: Accepted

Solution code:
import itertools

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


def main():
	k = []
	s = []
	answers = []

	for i in range(M + 1):
		inputs = list(map(int,input().split()))
		if i == M:
			answers = inputs.copy()
		else:
			k.append(inputs[0])
			s.append(inputs[1:])

	allCandidates = (list(itertools.product(range(2), repeat=N)))

	result = []
	for c in allCandidates:
		ok = True
		for i, ss in enumerate(s):
			sumBulk = 0
			for sNumber in ss:
				sumBulk += c[sNumber - 1]
			if sumBulk % 2 != answers[i]:
				ok = False
		if ok:
			result.append(c)

	print(len(list(set(result))))

if __name__ == '__main__':
	main()

Submission status: Accepted

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


on_num_dict = {} # それぞれの電球に対して、いくつのスイッチが押されていたらonになるかの辞書
for m in range(M):
    num_list = [i for i in range(k_list[m]+1) if i%2==p_list[m]]
    on_num_dict[m] = num_list

ans = 0
for i in range(2**N): # on off のパターン
    flag = 1
    bin_list = list(format(i, '0'+str(N)+'b'))
    for m in range(M): #電球ひとつひとつに対して
        on_switch = [int(bin_list[s-1]) for s in s_list[m]] # switch の on off
        on_switch_num = sum(on_switch)
        if on_switch_num in on_num_dict[m]:
            flag = 1
        else:
            flag = 0
            break
    if flag == 1:
        ans+=1
print(ans)

Submission status: Accepted

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

for i in range(2**n):
  ans += 1
  for j in range(len(s)):
    on = 0
    for k in range(s[j][0]):
      on += ((i>>(s[j][k+1]-1))%2)
    if(on%2 != p[j]):
      ans -= 1
      break
      
print(ans)

Submission status: Accepted

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

for i in range(1<<n):
    for j in range(m):
        cnt = 0
        for num in s[j]:  
            if i&(1<<(num-1)) != 0:
                cnt += 1
        if cnt%2 != p[j]: #j番目の電球でアウト
            break
    else: #すべての電球でパス
        ans += 1

print(ans)

Submission status: Accepted

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

switch = []

for _ in range(M):
    k, *sss = list(map(int,input().split()))
    t = 0
    for s in sss:
        t += 1 << (s-1)
    switch.append(t)
    
p = list(map(int,input().split()))


cnt = 0
for i in range(1 << N):
    for sw, pp in zip(switch, p):
        t = i&sw
        c = bin(t).count("1")
        if c % 2 != pp:
            break
    else:
      cnt += 1
print(cnt)

Submission status: Accepted

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

# 繋がってるスイッチの情報
S = [list(map(int, input().split()))[1:] for _ in range(M)]
P = list(map(int, input().split()))

# print(S)
# print(P)

ans = 0

for i in range(1 << N):
    # print(i)
    for m in range(M):
        cnt = 0
        for s in S[m]:  # Sは繋がっているスイッチの情報
            if i & (1 << (s-1)) != 0:
                cnt += 1
        if cnt % 2 != P[m]:
            break
    else:  # このelseはどういうこと
        ans += 1

print(ans)

Submission status: Accepted

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

# 繋がってるスイッチの情報
S = [list(map(int, input().split()))[1:] for _ in range(M)]
P = list(map(int, input().split()))

# print(S)
# print(P)

ans = 0

for i in range(1 << N):
    # print(i)
    for m in range(M):
        cnt = 0
        for s in S[m]:  # Sは繋がっているスイッチの情報
            if i & (1 << (s-1)) != 0:
                cnt += 1
        if cnt % 2 != P[m]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def switches(N: int, M: int, sw: list, P: list)->int:
    count = 1 << N
    sw_state = [0] * N
    li_state = [0] * M
    for i in range(1 << N):
        for j in range(N):
            sw_state[j] = 1 if (i & 1) != 0 else 0
            i >>= 1

        for m in range(M):
            li_state[m] = 0
            for si in sw[m][1:]:
                li_state[m] += sw_state[si-1]

            if li_state[m] % 2 != P[m]:
                break
        else:
            continue

        count -= 1

    return count


if __name__ == "__main__":
    M = 0

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

    ans = switches(N, M, sw, P)
    print(ans)

Submission status: Accepted

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

p = list(map(int, input().split()))
ans = 0
for i in range(1<<n):
    p_ = p[:]
    for j in range(n):
        if not (i & (1<<j)):
            continue
        for k in range(m):
            if j+1 in a[k]:
                p_[k] ^= 1
    ans += (max(p_) == 0)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def hantei(n,m,s,k,p):
  b = 0
  for l in range(m):
    a = 0
    for x in range(k[l][0]):
      a += s[k[l][x+1]-1]
    if a%2 != p[l]:
      b = 1
  if b == 0:
    return True
  else:
    return False

n,m = map(int,input().split())
k = []
for _ in range(m):
  k.append(list(map(int,input().split())))
p = list(map(int,input().split()))
c = 0
for _ in range(2**n):
  s = [0] * n
  ll = len(bin(_))
  for i in range(ll):
    if i >= 2:
      s[n-ll+i] = int(bin(_)[i])
  if hantei(n,m,s,k,p):
    c += 1
print(c)

Submission status: Accepted

Solution code:
# Ref : https://qiita.com/ct158603292321/items/11122ba8a5be3c97912b
import numpy as np
N, M = map(int, input().split())
L = []
for i in range(M):
    #a = list(map(int, input().split()))
    *a, = map(int, input().split())
    L.append(a[1:])
*P, = map(int, input().split())

ans = 0
for n in range(2 ** N):
    tmp = np.array([n >> s & 1 for s in range(N)])
    S = []
    for i in L :
        s = sum(tmp[np.array(i) - 1]) % 2
        S.append(s)
    if P == S :
        ans += 1
print(ans)

Submission status: Accepted

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

all_on = 0
for sp in itertools.product([0, 1], repeat=n):
    on = 0
    # 電球固定
    for i in range(m):
        cnt = 0
        # スイッチ固定
        for j in range(len(s[i])):
            if sp[s[i][j]-1] == 1:
                cnt += 1
        # 電球iにつながるスイッチのうちON数がpなら対象の電球はON
        if cnt % 2 == p[i]:
            on += 1
    # すべての電球がONなら
    if on == m:
        all_on += 1

print(all_on)

Submission status: Accepted

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

ans = 0

for bit in range((1 << N)) :
    A = []
    for k in range(N) :
        if bit & (1 << k) :
            A.append(k)
    #print(A)
    for i in range(M) :
        cnt = 0
        for j in range(len(S[i])) :
            if S[i][j] in A :
                cnt += 1
        if (cnt % 2) != P[i] :
            break
    else :
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#スイッチと電球の番号はすべて1下げる
import numpy as np

N, M = map(int, input().split())
T = [[0 for i in range(M)] for j in range(N)]
for i in range(M):
        S = list(map(int, input().split()))
        for k in range(S[0]):
                T[S[k+1]-1][i] = 1


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

ans = 0
for k in range(2**N):
        Q = np.array([0 for val in range(M)])
        for j in range(N):
                if bin(k >> j)[-1] == '1':
                        Q += np.array(T[j])
                        Q = Q % 2

        if list(Q) == P:
                ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product


def state_brute_force(state, count):
    state_list = [state for _ in range(count)]
    for s in product(*state_list):
        yield s


num_switch, num_lamp = map(int, input().split())
switches = [[0] * num_switch for _ in range(num_lamp)]

for n in range(num_lamp):
    i, *s = map(int, input().split())
    for si in s:
        switches[n][si - 1] = 1
condition = list(map(int, input().split()))

ans = 0
for on_off in state_brute_force([0, 1], num_switch):
    lamp_on = 0
    for i, lamp_switch in enumerate(switches):
        on_s = [si & state == 1 for si, state in zip(lamp_switch, on_off)]
        if on_s.count(True) % 2 == condition[i]:
            lamp_on += 1
    if lamp_on == num_lamp:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
switch = []
for i in range(m):
    switch.append([i for i in map(int,input().split())])
amari = [i for i in map(int,input().split())]
a = 0
for i in range(2**n) :
    cnt = []
    for j in range(n):
        if ((i >> j)& 1) :
            p = j + 1
            cnt.append(p)

    ans = 0
    for h in range(m):
        count = 0
        for p in range(switch[h][0]) :
            if switch[h][p+1] in cnt :
                count += 1
        if count % 2 == amari[h] : ans += 1
    if ans == m:
        a += 1
print(a)

Submission status: Accepted

Solution code:
import itertools

N, M = map(int, input().split())
switches = []
for i in range(M):
    swi = input().split()
    swi = [int(x)-1 for x in swi][1:]
    switches.append(swi)
    
needs = [int(x) for x in input().split()]

ans = 0
def checkLightsUp(swi_ptn):
    for i in range(M):
        need = needs[i]
        cnt = 0
        for s in switches[i]:
            if swi_ptn[s] == 1:
                cnt  += 1
        if cnt % 2 != need:
            return False
    return True

for swi_ptn in itertools.product([0, 1], repeat=N):
    if checkLightsUp(list(swi_ptn)):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    A = [0] * N
    for i in range(M):
        for s in list(map(int, input().split()))[1:]:
            A[s - 1] |= 1 << i
    p = 0
    for i, j in enumerate(list(map(int, input().split()))):
        p |= j << i
    ans = 0
    for s in range(1 << N):
        t = 0
        for i in range(N):
            if s >> i & 1:
                t ^= A[i]
        if t == p:
            ans += 1
    print(ans)


main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    A = [0] * N
    for i in range(M):
        ks = list(map(int, input().split()))
        for s in ks[1:]:
            A[s - 1] |= 1 << i
    p = 0
    for i, j in enumerate(list(map(int, input().split()))):
        p |= j << i
    ans = 0
    for s in range(1 << N):
        t = 0
        for i in range(N):
            if s >> i & 1:
                t ^= A[i]
        if t == p:
            ans += 1
    print(ans)


main()

Submission status: Accepted

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

for i in range(m):
    t.append(list(map(int,input().split())))
p = list(map(int,input().split()))

x = 0
import copy


for switch_cond in range(2**n):
    s = []

    for i in range(n):
        if switch_cond%2 == 0:
            s.append("off")
            switch_cond = switch_cond//2
        else:
            s.append("on")
            switch_cond = (switch_cond-1)//2
    for j in range(m):
        ss = copy.deepcopy(s)
        for r in range(n):
            if r+1 not in t[j][1:]:
                ss[r]="off"           
        if (ss.count("on"))%2 != p[j]:
            break
    else:
        x += 1
print(x)

Submission status: Accepted

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

for i in range(m):
    t.append(list(map(int,input().split())))
p = list(map(int,input().split()))

x = 0
import copy


for switch_cond in range(2**n):
    s = []

    for i in range(n):
        if switch_cond%2 == 0:
            s.append("off")
            switch_cond = switch_cond//2
        else:
            s.append("on")
            switch_cond = (switch_cond-1)//2
    #print("s",s)
    for j in range(m):
        ss = copy.deepcopy(s)
        for r in range(n):
            if r+1 not in t[j][1:]:
                ss[r]="off"
        #print("t[",j,"]",t[j][1:])
        #print("ss*",ss)
        #print(ss.count("on"),p[j])
              
        if (ss.count("on"))%2 != p[j]:
            #print("break!")
            break
    else:
        #print("all on!")
        x += 1
print(x)

Submission status: Accepted

Solution code:
import itertools
 
N, M = map(int, input().split())
 
S = []
for i in range(M):
    k, *s = map(int, input().split())
    S.append(s)
    
P = [int(i) for i in input().split()]
 
A = [0, 1]
ans = 0
for i in itertools.product(A, repeat = N):
    flag = 0
    for j in range(M):
        cnt = 0
        for s in S[j]:
            if i[s - 1] == 1:
                cnt += 1
        if cnt % 2 != P[j]:
            flag = 1
    if flag == 0:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# coding: UTF-8

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

s = []
for i in range(m):
    s += [tuple(map(int,input().split())),]

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

ret = 0
all = [(str(bin(i)))[2:].zfill(n) for i in range(2 ** n)]
all = [[int(i) for i in case] for case in all]
for case in all:
    flag = 0
    for num,i in enumerate(s):
        if flag == 1:
            continue

        sw = [0 for z in range(n)]
        for k in i[1:]:
            sw[k-1] = 1

        if (sum(i*j for i,j in zip(sw,case)) % 2) != p[num]:
            flag = 1
           
    if flag == 0:
        ret += 1

print(ret)

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
for i in range(2**n):
	flag = True
	for j in range(m):
		res = 0
		for k in ks[j][1:]:
			res += (i//(2**(k-1)))&1
		if res%2 != p[j]:
			flag = False
	if flag == True:
		ans += 1
print(ans)