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:
# -*- coding:utf-8 -*-
import itertools

def solve():
    N, M = list(map(int, input().split()))
    Ks, Ss = [], []
    for i in range(M):
        _in = list(map(int, input().split()))
        Ks.append(_in[0])
        Ss.append(_in[1:])
    Ps = list(map(int, input().split()))

    # 全探索でいける
    switches = itertools.product([0,1], repeat=N)
    ans = 0
    for switch in switches:
        is_ok = True
        for i in range(M):
            on_num = 0
            for s in Ss[i]:
                if switch[s-1] == 1:
                    on_num += 1
            if on_num%2 != Ps[i]:
                is_ok = False
                break
        
        if is_ok:
            ans += 1

    print(ans)
    



if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
K, S = [], []
for _ in range(M):
	k, *s = map(int, input().split())
	K.append(k)
	S.append(list(map(lambda x: x-1, s)))
p = list(map(int, input().split()))
res = 0
for i in range(1<<N):
	flag = True
	for j in range(M):
		cnt = 0
		for k in S[j]:
			if (i >> k) & 1:
				cnt += 1
		if cnt%2 != p[j]:
			flag = False
			
	if flag: res += 1
print(res)

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(int, input().split())
ks = {}
for i in range(m):
    tmp = list(map(int, input().split()[1:]))
    ks[i] = [t-1 for t in tmp]
p = list(map(int, input().split()))

onoffs = []
for onoff in product('01', repeat=n):
    _ = [int(bin) for bin in onoff]
    onoffs.append(_)

res = 0
for i in range(len(onoffs)):
    tmp = 0
    for j in range(m):
        obj = []
        for k in ks[j]:
            obj.append(onoffs[i][k])
        if sum(obj) % 2 == p[j]:
            tmp += 1
    if tmp == m:
        res += 1

print(res)

Submission status: Accepted

Solution code:
import itertools

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

k = []
s = []


for i in range(m):
    items = [int(item) for item in input().split()]
    k.append(items[0])
    s.append(items[1:])

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

count = 0

for switch in range(2 ** n):
    for l in range(m):
        ons = 0
        for j in s[l]:
            if switch >> (j - 1) & 1:
                ons += 1
        if ons % 2 != p[l]:
            break
    else:
        count += 1
print(count)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
ks = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
ans = 0
for switch in range(1 << n):
    target = str(bin(switch))[2:]
    if len(target) < n:
        target = "0"*(n-len(target)) + target
    flag = True
    for i in range(m):
        count = 0
        for j in ks[i][1:]:
            if target[j-1] == "1":
                count += 1

        if count % 2 != p[i]:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def slove():
    import sys
    import itertools
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    s = [list(map(int, input().rstrip('\n').split())) for _ in range(m)]
    p = list(map(int, input().rstrip('\n').split()))
    ls = [True, False]
    a_cnt = 0
    for it in itertools.product(ls, repeat=n):
        b = True
        for i, v in enumerate(s):
            cnt = 0
            for j, vv in enumerate(v):
                if j != 0:
                    if it[vv-1]:
                        cnt += 1
            if p[i] != cnt % 2:
                b = False
                break
        if b:
            a_cnt += 1
    print(a_cnt)


if __name__ == '__main__':
    slove()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
K_S = [[int(i) for i in input().split()] for _ in range(M)]
P = [int(i) for i in input().split()]
tot_cnt = 0

def check(combo):
    '''combo is list of string and returns boolean'''
    cnt = 0
    for i in range(M):
        tot = 0
        for j in K_S[i][1:]:
            tot += int(combo[j - 1])
        cnt += 1 if tot % 2 == P[i] else 0
    return cnt == M

for i in range(2**N):
    combo = list("{:010b}".format(i))[::-1]
    if check(combo):
        tot_cnt += 1

print(tot_cnt)

Submission status: Accepted

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

ans = 0
for i in range(2 ** n):
    state = "{:010b}".format(i)[::-1]
    for j in range(m):
        count = 0
        for si in s[j]:
            count += int(state[si-1])
        if count % 2 != p[j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]
bulbs=[]
ans=0
for i in range(m):
    a=[int(i) for i in input().split()]
    bulbs.append(a[1:])
p=[int(i) for i in input().split()]
config=[]

for i in range(2**n):
    state=[]
    for j in range(n):
        if(((i)&(1<<j))):
            state.append(1)
        else:
            state.append(0)
    config.append(state)
for i in range(len(config)):
    tot=0
    for j in range(len(bulbs)):
        ct=0
        for k in range(len(bulbs[j])):
            if(config[i][bulbs[j][k]-1]==1):
                ct+=1
        if(ct%2==p[j]):
            tot+=1
    if(tot==m):
        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])
  tmp=[]
  for k_ in range(k[i]):
    tmp.append(ks[k_+1])
  s.append(tmp)
p=list(map(int, input().split()))

def judge(M,s,p,li_state):
  for i in range(M):
    sum_light=0
    for j in s[i]:
      if li_state[j-1]:sum_light+=1
    if sum_light%2!=p[i]:
      return False
  return True

def excute_numofLighton(i,M,N,s,p,li_state,num):
  if i>=N:
    if judge(M,s,p,li_state):
      num+=1
    return num
  li_state[i]=1
  num=excute_numofLighton(i+1,M,N,s,p,li_state,num)
  li_state[i]=0
  num=excute_numofLighton(i+1,M,N,s,p,li_state,num)
  return num

li_state =[0]*N
ans = 0
ans = excute_numofLighton(0,M,N,s,p,li_state,ans)
print(ans)

Submission status: Accepted

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

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

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

ans = 0
for bit in range(2 ** n):
    on_light_cnt = 0
    for i in range(m):
        on_switch_cnt = 0
        for j in s[i]:
            if (bit >> (j - 1)) & 1 == 1:
                on_switch_cnt += 1

        if on_switch_cnt % 2 == p[i]: 
            on_light_cnt += 1
    if on_light_cnt == m: ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
kLst = [list(map(int, input().split())) for i in range(M)]
pLst = list(map(int, input().split()))
ans = 0
dLst = [0] * N

def dfs(n, v, ans):
    dLst[n - 1] = v
    if N == n:
        tLst = [0] * M
        for i in range(M):
            cnt = 0
            for j in range(kLst[i][0]):
                if dLst[kLst[i][j + 1] - 1] == 1:
                    cnt += 1
            tLst[i] = cnt % 2
        s = True
        for i in range(M):
            if tLst[i] != pLst[i]:
                s = False
                break
        if s:
            ans += 1
        return ans
    ans = dfs(n + 1, 0, ans)
    ans = dfs(n + 1, 1, ans)
    return ans

print(dfs(0, 0, ans))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
bulbs = []
for _ in range(m):
    _, *s = list(map(int, input().split()))
    bulbs.append(s)
ps = list(map(int, input().split()))

count = 0
for i in range(2**n):
    switches = []
    for _ in range(n):
        switches.append(i % 2)
        i //= 2
    ok = True
    for s, p in zip(bulbs, ps):
        res = p
        for b in s:
            res += switches[b - 1]
        if res % 2 == 1:
            ok = False
    if ok:
        count += 1
print(count)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    i_bin = "{:010b}".format(i)[::-1]
    for m_i in range(m):
        bulb_sum = 0
        for x in s[m_i]:
            bulb_sum += int(i_bin[x-1])
        if bulb_sum % 2 != p[m_i]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

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

sl = [0] * n

count = 0

for t in range(2**n):
		
	# print(sl)
	
	test = True
	for o in range(m):
		on = 0
		for q in kl[o]:
			on += sl[q-1]
		
		if pl[o] != on % 2:
			test = False
		
	if test:
		count += 1
	
	for i in range(n):
		if sl[i] == 0:
			sl[i] = 1
			for j in range(i):
				sl[j] = 0
			break
	

print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split(" "))
light = []
for i in range(M):
    tmp = list(map(int,input().split(" ")))
    light.append(tmp)

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


switch = [0 for i in range(N)] 


def search(N,M,light,p,l,switch):#全探索
    if l<N:
        l += 1
        a=search(N,M,light,p,l,switch)
        switch[l-1]+=1 
        b = search(N,M,light,p,l,switch)
        return a+b
    else:#それぞれの場合について判定
        flag = 0
        for i in range(M):
            a = 0
            for j in range(light[i][0]):
                a +=switch[light[i][j+1]-1]
            if a%2 == p[i]:
                continue
            else:
                flag = 1
                break
        if flag == 0:
            return 1
        else:
            return 0
  

ans = search(N,M,light,p,0,switch)
print(ans)

Submission status: Accepted

Solution code:
import collections 
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n,m = inpl()
s = [0] * m
for i in range(m):
    s[i] = inpl()
p = inpl()
ans = 0

for flag in itertools.product([0,1], repeat=n):
    cnt = 0
    bb = [False] * n
    for i,j in enumerate(flag):
        if j :
            bb[i] = True
    for i in range(m):
        tmp = 0
        for j in range(1,len(s[i])):
            if bb[s[i][j]-1] == True:
                tmp += 1
        if tmp % 2 == p[i]:
            cnt += 1
    if cnt == m:
        ans += 1
print(ans)

Submission status: Accepted

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

swi = []
for _ in range(M):
    k, *s_list = list(map(int, input().split()))
    temp_num = 0
    for s in s_list:
        temp_num += 1 << (s-1)
    swi.append(temp_num)

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

ans = 0
for i in range(1 << N):
    for s, p in zip(swi, p_list):
        swi_on = i & s
        if bin(swi_on).count('1') % 2 != p:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
 
binary = 2**(n)
 
lamps={i:[] for i in range(m)}
 
 
for i in range(m):
    temp=list(map(int,input().split()))
    lamps[i]=[temp[1:]]
ps=list(map(int,input().split()))
 
for i,p in enumerate(ps):
    lamps[i].append(p)
 
 
pattern=0
for i in range(binary,binary*2):
    check_flg=True
    i_binary = bin(i)
    switch = list(map(int, list(i_binary[2:])))
    for sws, on_flg in lamps.values():
        sums=0
        for s_index in sws:
            if switch[s_index] == 1:
                sums+=1
        if sums%2!=on_flg:
            check_flg=False
            break
    if check_flg:
        pattern+=1
print(pattern)

Submission status: Accepted

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

binary = 2**(n)

lamps={i:[] for i in range(m)}


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

for i,p in enumerate(ps):
    lamps[i].append(p)


pattern=0
for i in range(binary,binary*2):
    check_flg=True
    i_binary = bin(i)
    switch = list(map(int, list(i_binary[2:])))
    for sws, on_flg in lamps.values():
        sums=0
        for s_index in sws:
            if switch[s_index] == 1:
                sums+=1
        if sums%2!=on_flg:
            check_flg=False
            break
    if check_flg:
        pattern+=1
print(pattern)

Submission status: Accepted

Solution code:
N,M = map(int,input().split(" "))
light = []
for i in range(M):
    tmp = list(map(int,input().split(" ")))
    light.append(tmp)

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


switch = [0 for i in range(N)] 


def search(N,M,light,p,l,switch):
    if l<N:
        l += 1
        a=search(N,M,light,p,l,switch)
        switch[l-1]+=1 
        b = search(N,M,light,p,l,switch)
        return a+b
    else:
        flag = 0
        for i in range(M):
            a = 0
            for j in range(light[i][0]):
                a +=switch[light[i][j+1]-1]
            if a%2 == p[i]:
                continue
            else:
                flag = 1
                break
        if flag == 0:
            return 1
        else:
            return 0
  

ans = search(N,M,light,p,0,switch)
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split(" "))
switch = []
for i in range(M):
    tmp = list(map(int,input().split(" ")))
    switch.append(tmp)

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


light = [0 for i in range(N)] 



def search(N,M,switch,p,l,light):
    if l<N:
        l += 1
        a=search(N,M,switch,p,l,light)
        light[l-1]+=1 
        b = search(N,M,switch,p,l,light)
        return a+b
    else:
        flag = 0
        for i in range(M):
            a = 0
            for j in range(switch[i][0]):
                a +=light[switch[i][j+1]-1]
            if a%2 == p[i]:
                continue
            else:
                flag = 1
                break
        if flag == 0:
            return 1
        else:
            return 0
  

ans = search(N,M,switch,p,0,light)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
MOD = 2  # type: int

def solve(S, k, p, M, N):
    count = 0
    for sw in range(2**N):
        sw_str = bin(sw)[2:].zfill(N)
        sw_list = list(map(int, list(sw_str)))
        isGood = True
        for i in range(M):
            bsum = 0
            for j in range(k[i]):
                bsum += sw_list[S[i][j]]
            if bsum % 2 != p[i]:
                isGood = False
                break
        if isGood:
            count += 1

    print(count)
    return 

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    k = [0] * M
    p = [0] * M
    S = []
    for i in range(M):
        k[i] = int(next(tokens))
        S += [ [int(next(tokens))-1 for j in range(k[i]) ] ]
    for i in range(M):
        p[i] = int(next(tokens))

    solve(S, k, p, M, N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import copy
n,m=map(int,input().split())
k=[[] for _ in range(n)]

for i in range(m):
    for j in [int(_) for _ in input().split()][1:]:
        k[j-1].append(i)
#偶数回はFalse、奇数回はTrue
p=[bool(int(i)) for i in input().split()]

#print(k)
#print(p)
p2=[False]*m
c=0
for i in range(2**n):
    l=format(i,"0>10b")[-n:]
    #print(l)
    t=copy.deepcopy(p)
    #print(t)
    #print(n)
    for j in range(n):
        if l[j]=="1":
            for h in k[j]:
                t[h]= not t[h]
    #print(t)
    if t==p2:
        c+=1
print(c)

Submission status: Accepted

Solution code:
def slove():
    import sys, itertools
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    ks = []
    for i in range(m):
        ks.append(list(map(int, input().rstrip('\n').split())))
    p = list(map(int, input().rstrip('\n').split()))
    ls = [True, False]
    all_cnt = 0
    for i in itertools.product(ls, repeat=n):
        b = True
        for j, v in enumerate(ks):
            cnt = 0
            for k, s in enumerate(v):
                if k != 0:
                    if i[s-1]:
                        cnt += 1
            if p[j] != cnt % 2:
                b = False
                break
        if b:
            all_cnt += 1
    print(all_cnt)


if __name__ == '__main__':
    slove()

Submission status: Accepted

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

p = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    for j in range(M):
        bitmask = 0b0
        for sw in lst[j][1::]:
            bitmask += 2**(sw-1)
        on_count = bin(bitmask & i).count("1")
        
        if p[j] != on_count % 2:
            break

    else:
        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()))
c = 0
a = 0
for a in range(2**n):
  a2 = format(a, 'b').zfill(n)
  d = 0
  for i in range(m):
    o = 0
    for j in range(S[i][0]):
      o += int(a2[S[i][j+1]-1])
    if o % 2 == P[i]:
      d += 1
  if d == m:
    c += 1
print(c)

Submission status: Accepted

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

S = []
for m in range(M):
    l = list(map(int, input().split()))
    S.append(np.array(l[1:], dtype = int) - 1)
P = list(map(int, input().split()))

cnt = 0
for n in range(2 ** N):
    tmp = np.array(list(map(int, list(format(n, 'b').zfill(N)))), dtype = int)
    f = True
    for m in range(M):
        # print (S[m])
        if tmp[S[m]].sum() % 2 != P[m]:
            f = False
            break

    if f: cnt += 1

print (cnt)

Submission status: Accepted

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

switch = [['0'], ['1']]

for i in range(N-1):
    tmp = []
    for j in switch:
        tmp.append(j+['0'])
        tmp.append(j+['1'])
    switch = tmp #スイッチのonoffのマップ化

ans = 0

for i in switch:
    false = 0
    for j in range(M):
        cnt = 0 #onの個数
        for k in range(s[j][0]):
            if i[s[j][1+k]-1] == '1':
                cnt += 1
        if cnt%2 != p[j]:
            false += 1 #条件に合っていなかったらfalseに加算する
    if false == 0:
        ans += 1 #全て条件を満たしていたらansに加算する
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

bit = itertools.product(range(2), repeat=N)
cnt = 0
for b in bit:
    np_b = np.array(b)
    on = 1
    for bulb in range(M):
        on *= sum(np_b[switch[bulb]]) % 2 == p[bulb]
    cnt += on
print(cnt)

Submission status: Accepted

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

ks = []
ss = []
for i in range(m):
    s = list(map(int, input().split()))
    k = s.pop(0)
    ks.append(k)
    ss.append(s)

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

import itertools
combs = itertools.product([1, 0], repeat=n)

res = 0
for comb in combs:
    valid = True
    for i in range(m):
        p = ps[i]
        k = ks[i]
        s = ss[i]
        cnt = 0
        for j in range(k):
            cnt += comb[s[j] - 1]
        if cnt % 2 != p:
            valid = False
            break
    if valid:
        res += 1

print(res)

Submission status: Accepted

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

#create 0/1 matrix for all lamps and switches 
s=np.zeros((M,N))
for i in range(M):
    ks = list(map(int, input().split()))  
    for j in range(ks[0]):
        s[i, ks[j+1]-1]=1
P = list(map(int, input().split()))      
    
counter=0
# 2^N possible combinations of switches
for k in range(2**N):
    k_bit = list(map(int, list(np.binary_repr(k, N))))
    #calculate how many switches are on for each lamp
    b_status = np.dot(s, k_bit)%2
    #print(k_bit, b_status)
    if all(b_status==P)==True:
        counter +=1

print(counter)

Submission status: Accepted

Solution code:
import numpy as np

N, M=map(int, input().split())
matrix=np.zeros((M, N))

for i in range(M):
  temp=np.array(list(map(int, input().split())))
  temp-=1
  matrix[i, temp[1:]]=1
  
p=np.array(list(map(int, input().split())))

counter=0
for i in range(pow(2, N)):
  s=np.array(list(map(int, list(format(i, '0'+str(N)+'b')))))
  if all(np.dot(matrix, s)%2==p)==True:
    counter+=1
    
print(counter)

Submission status: Accepted

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

onoff=[["0"],["1"]]

for i in range(n-1):
    tmp=[]
    for j in onoff:
        tmp.append(j+["0"])
        tmp.append(j+["1"])
    onoff=tmp

ans=0
for i in onoff:
    f=0
    for j in range(m):
        c=0
        for k in range(s[j][0]):
            if i[s[j][1+k]-1]=='1':
                c+=1
        if c%2!=p[j]:
            f+=1
    if f==0:
        ans+=1
print(ans)

Submission status: Accepted

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

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
lst = [LI() for _ in range(m)]
p = LI()
ans = 0
for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if (i>>j) & 1:
            switch[j] = 1
    for j in range(m):
        k = lst[j][0]
        tmp = 0
        for l in range(k):
            if switch[lst[j][l+1]-1] == 1:
                tmp += 1
        if tmp % 2 != p[j]:
            break
    else:
        ans += 1
print(ans)

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:
#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: #スイッチの番号の位置を知りたいので、スイッチの番号-1で位置を配列的に求める
                cnt += 1
        if cnt % 2 != p[i]:
            judge = False
    if judge:
        res += 1
print(res)

Submission status: Accepted

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

for _ in range(n-1):
  tmp = []
  for j in on_off:
    tmp.append(j+[0])
    tmp.append(j+[1])
  on_off = tmp

for x in on_off:
  cnt = 0
  for y in range(m):
    z = 0
    for c in l[y-1]:
      z += x[c-1]
    if z%2 == p[y-1]%2:
      cnt += 1
  if cnt == m:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
#逆転させなきゃ
n,m = map(int, input().split())
cond = []
for i in range(m):
  temp = input().split()
  cond.append([int(i) for i in temp])
p = [int(i) for i in input().split()]

ans = 0
for i in range(2**n): #全状態を調べる
  flag = True
  temp = bin(i)
  sw = [str(l) for l in temp]
  sw.reverse()
  flag = True
  for j in range(m): #電球を１つずつ調べる
    if flag:
      c = 0 #スイッチのonの数
      for k in range(1,len(temp)-1): #指定のスイッチか
        if cond[j][1:].count(k)==1:
          c += int(sw[k-1])
      if c%2 != p[j]: #もし条件を満たさない電球があったら」
        flag = False
      elif c%2 == p[j] and j==m-1: #最後まで条件を満たしたら
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
# original_author prd_xxx

N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
P = list(map(int,input().split()))

ans = 0
# bin N 左シフトを1からNまで行う。
for b in range(1<<N):
    for i in range(M):
        c = 0
        for s in src[i][1:]:
            # 解答bitflagとand計算でスイッチのonoffを定義
            if b&(1<<(s-1)):
                c += 1
        # 最後に条件スイッチの条件と合致しているか検証
        # 合わなければelseに飛ばずbの次を検証しに行く
        if c%2 != P[i]: break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
temp1 = 0
temp2 = 0

for i in range(2 ** n):
    num = bin(i)
    num2 = num.lstrip('0b')
    num3 = num2.zfill(n)
    
    for j in range(m):
        for l in range(k_s[j][0]):
            temp1 += int(num3[k_s[j][l + 1] - 1])
        if temp1 % 2 == p[j]:
            temp2 += 1
            temp1 = 0
        else:
            temp1 =0
    
    if temp2 == m:
        ans += 1
    temp2 = 0
    
print(ans)

Submission status: Accepted

Solution code:
# bit全探索
# d = 4
# for mask in range(1 << d):  # 2のd乗になる
#     print("mask =", mask)
#     for i in range(d):
#         print("(mask >>", i, ") & 1 = ", (mask >> i) & 1)
#         # 1のビットが立つかどうかでT/F判断した方が個人的に分かりやすいから(mask >> i) & 1と書いている


# まずスイッチの状態を全て表す方針で行く
N, M = map(int, input().split())  # N個スイッチとM個の電球

connect_infos = []
# それぞれの電球が繋がっているスイッチの情報が与えられる
for i in range(M):
    k, *S = list(map(lambda x: int(x)-1, input().split()))
    connect_infos.append(S)

# print(connect_info)
# 電球が灯されるかの判断材料
P = list(map(int, input().split()))
# print(P)


switches_status = [[] for _ in range(1 << N)]
# print(switches_status)
for mask in range((1 << N)):  # 2のN乗になる
    for i in range(N):
        switches_status[mask].append((mask >> i) & 1)

# print(switches_status)

ans = 0
# 全てのスイッチの状態ついてループを回す
for status in switches_status:
    shine = 0
    # statusは1次元リスト
    for i, connect_info in enumerate(connect_infos):
        # connect_infoにはそれぞれの電球がどのスイッチに接続されているかの情報がある
        on_count = 0
        for j in connect_info:
            on_count += status[j]
        # 接続しているスイッチのon状態を個数を獲得できた
        if on_count % 2 == P[i]:
            shine += 1
    if shine == M:  # 光っている電球の数 と 電球の個数Mが等しいならansをインクリメントする
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# bit全探索
# d = 4
# for mask in range(1 << d):  # 2のd乗になる
#     print("mask =", mask)
#     for i in range(d):
#         print("(mask >>", i, ") & 1 = ", (mask >> i) & 1)
#         # 1のビットが立つかどうかでT/F判断した方が個人的に分かりやすいから(mask >> i) & 1と書いている


# まずスイッチの状態を全て表す
N, M = map(int, input().split())  # N個スイッチとM個の電球

connect_infos = []
# それぞれの電球が繋がっているスイッチの情報が与えられる
for i in range(M):
    k, *S = list(map(lambda x: int(x)-1, input().split()))
    connect_infos.append(S)

# print(connect_info)
# 電球が灯されるかの判断材料
P = list(map(int, input().split()))
# print(P)


switches_status = [[] for _ in range(1 << N)]
# print(switches_status)
for mask in range((1 << N)):  # 2のd乗になる
    for i in range(N):
        switches_status[mask].append((mask >> i) & 1)

# print(switches_status)

ans = 0
# 全てのスイッチの状態ついてループを回す
for status in switches_status:
    shine = 0
    # statusは1次元リスト
    for i, connect_info in enumerate(connect_infos):
        # connect_infoにはそれぞれの電球がどのスイッチに接続されているかの情報がある
        on_count = 0
        for j in connect_info:
            on_count += status[j]
        # 接続しているスイッチのon状態を個数を獲得できた
        if on_count % 2 == P[i]:
            shine += 1
    if shine == M:  # 光っている電球の数 と 電球の個数Mが等しいならansをインクリメントする
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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

lightBulbs = [None]*M
for i in range(M):
    data = list(map(int, input().split()))
    lightBulbs[i] = data[1:]

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

def rec(pos, count, status):
    if pos == N:
        count += judge(status)
        return count
    status[pos] = 0
    count = rec(pos+1, count, status)
    status[pos] = 1
    count = rec(pos+1, count, status)
    return count

def judge(status):
    for i, lightBulb in enumerate(lightBulbs):
        toggle = 0
        for switch in lightBulb:
            toggle += status[switch-1]
        toggle %= 2
        if P[i] != toggle:
            return 0
    return 1 
    

ans = rec(0, 0, [0]*N)
print(ans)