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: Wrong Answer

Solution code:
#電球クラス
class Light:
    def __init__(self,name,switchs,whattype):
        self.name=name
        self.switchs=switchs
        self.whattype=whattype
    def reset(self):
        sumnum=0
        for switch in self.switchs:
            sumnum+=switch.onoff
        if sumnum%2==0:
            self.state="off"
        else:
            self.state="on"
            
#スイッチクラス            
class Switch:
    def __init__(self,name):
        self.name=name
        self.onoff=0
    def click(self,onoff):
        self.onoff=onoff
        
    
#整理用データ
n,m=[int(i) for i in input().split()]
allist=[]
for i in range(m+1):
    allist.append([int(j) for j in input().split()])
      

#全スイッチのリスト
switchlist=[]
for i in range(n):
    switchlist.append(Switch(i))


#全電球のリスト
lightlist=[]
for i in range(m):
    swlist=[]
    swnum=allist[i][1:]
    for j in swnum:
        swlist.append(switchlist[j-1])
    whattype=allist[-1][i]
    lightlist.append(Light(i,swlist,whattype))
    
#全部の付け方について
count=0
clicklist=[0 for i in range(n)]    
for i in range(2**n):
    onoffcheck=0
    j=0
    while i:
        clicklist[j]=i%2
        i=i//2
        j+=1
    for k in range(n):
        switchlist[k].click(clicklist[k])
    for light in lightlist:
        light.reset()
        if light.state=="off":
            onoffcheck+=1
    if onoffcheck==0:
        count+=1
print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

ks_nums = [0]*m
for i in range(m):
    for j in range(ks[i][0]):
        ks_nums[i] += 2**(ks[i][j+1]-1)

ans = 0
success = True
for i in range(2**m):
    for j in range(m):
        cnt = 0
        tmp = i & ks_nums[j]
        for k in range(m):
            if ( tmp >> k ) & 1:
                cnt += 1
        if p[j] != cnt % 2:
            success = False
            break
    if success:
        ans += 1
    else:
        success = True

print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(N**2):
  sl = []
  for j in range(N):
    if (i>>j)&1:
      sl.append(j+1)
  for j in range(M):
    if len(set(KS[j][1:])&set(sl))%2 ==P[j]:
      continue
    else:
      break
  else:
    ans += 1
    
print(ans)

Submission status: Wrong Answer

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_p = 0
ans = 0

#それぞれのスイッチの状態について検証を行う
for i in product(range(2), repeat=N):
    cnt = 0
    #電灯ごとの点滅を調べる
    for j in range(M):
        for k in ks[j][1:]:
            cnt_p += i[k-1]
        if cnt_p %2 == p[j]:
            cnt += 1
        else:
            break
    #全てつくならansに+1
    if cnt == M:
        ans += 1

print(ans)

Submission status: Wrong Answer

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
on_off = [0]*n
checker = [0]*m
for i in range(2**n-1):
    for j in range(n):
        if on_off[j] == 1:
            on_off[j] = 0
        else:
            on_off[j] = 1
            break
    slider = [1]*m
    for j in range(m):
        checker[j] = p[j]
    for j in range(1,n+1):
        for k in range(m):
            for l in range(1,ks[k][0]+1):
                if ks[k][l] == j and on_off[j-1] == 1:
                        checker[k] = 1 - checker[k]
    for j in range(m):
        if checker[j] == 1:
            break
        elif j == m-1:
            ans += 1

print(ans)

Submission status: Wrong Answer

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
on_off = [0]*n
checker = [0]*m
for i in range(2**n-1):
    for j in range(n):
        if on_off[j] == 1:
            on_off[j] = 0
        else:
            on_off[j] = 1
            break
    slider = [1]*m
    for j in range(m):
        checker[j] = p[j]
    for j in range(1,n+1):
        for k in range(m):
            if slider[k] <= ks[k][0]:
                if ks[k][slider[k]] == j:
                    if on_off[j-1] == 1:
                        checker[k] = 1 - checker[k]
                    slider[k] += 1
    for j in range(m):
        if checker[j] == 1:
            break
        elif j == m-1:
            ans += 1

print(ans)

Submission status: Wrong Answer

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

S = []
for i in range(M):
    S.append(set([int(v) for v in input().split()][1:]))
P = [int(v) for v in input().split()]

limit = int('1' * N, 2)
res = 0
for j in range(limit + 1):
    on_idx = set()
    for ki, k in enumerate(list(('{:0' + str(N) + 'b}').format(j))):
        if k == '1':
            on_idx.add(ki)

    cnt = 0
    for i in range(M):
        cnt += int(len(S[i].intersection(on_idx)) % 2 == P[i])

    if cnt == M:
        res += 1
print(res)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import itertools

N, M = [int(item) for item in 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 pat in itertools.product([0, 1], repeat=N):
    for l in range(M):
        ons = sum([pat[item - 1] for item in s[l]])
        if ons % 2 != p[i] % 2:
            break
    else:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
#ABC128 C
N, M = (int(_) for _ in input().split())
A = [list(map(int, input().split()))[1:] for _ in range(M)]
P = list(map(int, input().split()))
ans = 0
for i in range(N):
    for j, S in enumerate(A):
        if P[j] ^ sum(i >> k-1 & 1 for k in S) & 1:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#ABC128 C
N, M = (int(_) for _ in input().split())
A = [list(map(int, input().split()))[1:] for _ in range(M)]
P = list(map(int, input().split()))
ans = 0
for i in range(N):
    for j, S in enumerate(A):
        if P[j] ^ (sum(i >> k-1 & 1 for k in S) & 1):
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

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

t=[]
for i in range(2**n):
        t.append(format(i,'b').zfill(n))
z=[]
p=p*(2**n)
for i in range(2**n):
        for j in range(len(l)):
                count=0
                for k in range(1,len(l[j])):
                        count+=int((t[i][l[j][k]-1]))
                z.append(count%2)
y=[]
u=[]
ans=0
for i in range(2*n):
        y.append(p[i*m:i*m+m])
        u.append(z[i*m:i*m+m])


for l in range(len(y)):
        if y[l]==u[l]:
                ans+=1
print(ans)

Submission status: Wrong Answer

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()))
result=0
for i in range(n**2):
	flag=1
	for j in range (m):
		count=0
		for k in range (s[j][0]):
			if (i>>s[j][k+1]-1)&1 ==1:
				count+=1
		if count%2!=p[j]:
			flag=0
	if flag==1:
		result+=1
print(result)

Submission status: Wrong Answer

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

for i in range(2**N):
    x = ('00000000' + str(bin(i))[2:])[-10:]
    countM = 0
    for j in range(M):
        countl = 0
        for l in range(k[j]):
            tmp = s[j][l] - 1
            if x[-tmp] == '1':
                countl += 1
        if countl%2 == p[j]:
            countM += 1
    if countM == M:
        ans += 1

print(ans) 


#%%

Submission status: Wrong Answer

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

sss = [[] for i in range(m)]

for i in range(m):
  ss = list(map(int, input().split()))
  ss = ss[1:]
  sss[i] = ss
#print(sss)

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

ans = 0
for i in range(2**n):
  s = [0]*n
  for j in range(n):
    if ((i>>j) & 1):
      s[j] = 1
  for a in range(m):
    sum_ = 0
    for b in sss[a]:
      sum_ += s[b-1]
    if sum_%2 !=  ps[a]:
      break
  else:
    ans += 1
    print(s)

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = [list(map(int, input().split()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
c = 0
for n in range(1 << n):
    for i, s in enumerate(a):
        if p[i] ^ sum(n >> s_-1 & 1 for s_ in s) & 1:
            break
        else:
            c += 1
print(c)

Submission status: Wrong Answer

Solution code:
import itertools
n,m=map(int,input().split())
l=[[0]*m for _ in range(n)]
for i in range(m):
    ltmp=list(map(int,input().split()))
    for j in ltmp[1:]:
        l[j-1][i]=1
p=list(map(int,input().split()))
lit=list(itertools.product([0,1],repeat=m))
ans=0

for i in lit:
    atmp=[]
    for j in l:
        tmp=sum([x*y for (x,y) in zip(i,j)])%2
        atmp.append(tmp)
    if atmp==p:ans+=1
print(ans)

Submission status: Wrong Answer

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

ans = 0
for bit in range(2**n):
    f = []
    for i in range(n):
        if ((bit>>i) & 1):
            f.append(1)
        else:
            f.append(0)
    temp = 0
    ok = 1
    for j in range(m):
        for item in lis[j]:
            if (f[item-1]==1):
                temp += 1
        if (temp%2 != p_lis[j]):
            ok = 0
        
    if ok:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
count = 0
for i in range(n**2):
    switch = [0]*n
    for j in range(n):
        if ((i >> j) & 1):
            switch[j] = 1
    for k in range(m):
        on = 0
        All = True
        for l in range(len(lis[k][1:])):
            on += switch[lis[k][1+l]-1]
        if on % 2 == p[k]:
            continue
        else:
            All = False
            break
    if All == True:
        count += 1
        
print(count)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
from itertools import product

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

    all_stats = product((0,1), repeat=N)
    ans = 0
    for stat in all_stats:
        is_ok = True
        for switch_i, switch in enumerate(S):
            on_num = 0
            for i in range(len(switch)):
                if switch[i] == stat[i]:
                    on_num += 1
            if on_num%2 != P[switch_i]:
                is_ok = False
                break
        if is_ok:
            ans += 1
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
	n, m = map(int, input().strip().split())
	A = [0] * n
	for i in range(m):
		sw = list(map(int, input().strip().split()))[1:]
		for e in sw:
			e -= 1
			A[e] |= 1 << i

	pl = list(map(int, input().strip().split()))
	p = 0
	for i, e in enumerate(pl):
		p = p << 1
		p |= e

	j = 0
	ans = 0
	while j < (1 << n):
		t = 0
		for i in range(n):
			if j >> i & 1:
				t ^= A[i]
		if t == p:
			ans += 1
		j += 1

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def main():
	n, m = map(int, input().strip().split())
	A = [0] * n
	for i in range(m):
		sw = list(map(int, input().strip().split()))[1:]
		for e in sw:
			e -= 1
			A[e] |= 1 << i

	pl = list(map(int, input().strip().split()))
	p = 0
	for i, e in enumerate(pl):
		p |= e
		p = p << i

	j = 0
	ans = 0
	while j < (1 << n):
		t = 0
		for i in range(n):
			if j >> i & 1:
				t ^= A[i]
		if t == p:
			ans += 1
		j += 1

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def create_bin_string(data, num):
    c_bin = "{:b}".format(data)
    switches = c_bin
    for _ in range(0, num-len(c_bin)):
        switches = "0" + switches
    return switches


def solve(N, M, data, Ps):
    lamp_sw_comb = list(map(lambda x: string_to_int(x), data))
    lamp_sw_p = string_to_int(Ps)

    count = 0
    for c in range(0, 2**N):
        switches = create_bin_string(c, N)
        print(switches)

        are_all_light = True
        for i, lamp_sw in enumerate(lamp_sw_comb):
            on_num = 0
            for j, sw in enumerate(lamp_sw):
                if j == 0:
                    continue
                if switches[sw-1] == "1":
                    on_num += 1
            if on_num % 2 != lamp_sw_p[i]:
                are_all_light = False
                break

        if are_all_light:
            count += 1
    return count


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    data = inputs(M)
    Ps = input()
    ret = solve(N, M, data, Ps)
    print(ret)

Submission status: Wrong Answer

Solution code:
import itertools
from functools import reduce
from operator import add

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

ans = 0
for i in range(2 ** n):
    STATE = []
    digit = len(format(i, 'b'))
    for j in range(digit):
        if ((i >> j) & 1):
            STATE.append(j + 1)
    check = [0] * m
    for l in range(m):
        if p[l] == 1:
            for o in range(1, len(s[l]) + 1, 2):  
                for r in itertools.combinations(s[l], o):
                    if set(r) <= set(STATE):
                        check[l] = 1
        else:   
            for o in range(2, len(s[l]) + 1, 2):
                for r in itertools.combinations(s[l], o):
                    if set(r) <= set(STATE):
                        check[l] = 1
    if reduce(add, check) == m:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
from functools import reduce
from operator import add

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

for i in range(m):
    s[i].sort()
ans = 0
for i in range(2 ** n):
    STATE = []
    digit = len(format(i, 'b'))
    for j in range(digit):
        if ((i >> j) & 1):
            STATE.append(j + 1)
    check = [0] * m
    for l in range(m):
        if p[l] == 1:
            for o in range(1, len(s[l]) + 1, 2):  
                for r in itertools.combinations(s[l], o):
                    if set(r) <= set(STATE):
                        check[l] = 1
        else:   
            for o in range(2, len(s[l]) + 1, 2):
                for r in itertools.combinations(s[l], o):
                    if set(r) <= set(STATE):
                        check[l] = 1
    if reduce(add, check) == m:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())#n個のスイッチのオンオフの組み合わせ
ks = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))#0/1⇒偶数or奇数
num=2**n
ans=0
for i in range(num+1):
    bin_i = str(bin(i))
    bin_i = bin_i[2:len(bin_i)]
    res = n-len(bin_i)
    bin_i = "0"*res + bin_i
    on=0
    for j in range(m):
        s_num=0
        for k in range(1, ks[j][0]+1):
            if bin_i[ks[j][k]-1] == "1":
                s_num+=1
        if s_num%2==p[j] and s_num!=0:
            on+=1
        else:
            break
    if on==m:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
from math import factorial
from functools import reduce
from operator import mul

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

for i in range(m):
    s[i].sort()
ans = 0
for i in range(2 ** n):
    STATE = []
    digit = len(format(i, 'b'))
    for j in range(digit):
        if ((i >> j) & 1):
            STATE.append(j + 1)
    combi = []
    for l in range(m):
        cnt = 0
        if p[l] == 1:
            for o in range(1, len(s[l]) + 1, 2):  
                for r in itertools.combinations(s[l], o):
                    if set(r) <= set(STATE):
                        cnt += 1
        else:   
            for o in range(2, len(s[l]) + 1, 2):
                for r in itertools.combinations(s[l], o):
                    if set(r) <= set(STATE):
                        cnt += 1
        combi.append(cnt)
    ans += reduce(mul, combi)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
from math import factorial

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

for i in range(m):
    s[i].sort()
ans = 0
for i in range(2 ** n):
    STATE = []
    digit = len(format(i, 'b'))
    for j in range(digit):
        if ((i >> j) & 1):
            STATE.append(j + 1)
    for l in range(m):
        a = 0
        b = 0
        cnt = 0
        if p[l] == 1:
            for o in range(1, len(s[l]) + 1, 2):  
                for r in itertools.combinations(s[l], o):
                    if set(r) <= set(STATE):
                        cnt += 1
                        a = 1
        else:   
            for o in range(2, len(s[l]) + 1, 2):
                for r in itertools.combinations(s[l], o):
                    if set(r) <= set(STATE):
                        cnt += 1
                        b = 1
        if a == 1 and b == 1:
            ans += factorial(cnt) / factorial(m) / factorial(cnt - m)
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

for i in range(m):
    s[i].sort()
ans = 0
cnt = 0
for i in range(2 ** n):
    STATE = []
    digit = len(format(i, 'b'))
    for j in range(digit):
        if ((i >> j) & 1):
            STATE.append(j + 1)
    for l in range(m):
        if p[l] == 1:
            for o in range(1, len(s[l]) + 1, 2):  
                for r in itertools.combinations(s[l], o):
                    if set(r) <= set(STATE):
                        cnt += 1
        else:   
            for o in range(2, len(s[l]) + 1, 2):
                for r in itertools.combinations(s[l], o):
                    if set(r) <= set(STATE):
                        cnt += 1
    if cnt == m:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

for i in range(m):
    s[i].sort()
ans = 0
cnt = 0
for i in range(2 ** n):
    STATE = []
    digit = len(format(i, 'b'))
    for j in range(digit):
        if ((i >> j) & 1):
            STATE.append(j + 1)
    for l in range(m):
        if p[l] == 1:
            for o in range(1, len(s[l]) + 1, 2):  
                for r in itertools.combinations(s[l], o):
                    if set(r) == set(STATE):
                        cnt += 1
        else:   
            for o in range(2, len(s[l]) + 1, 2):
                for r in itertools.combinations(s[l], o):
                    if set(r) == set(STATE):
                        cnt += 1
    if cnt == m:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(2**M):
    cnt = 0
    for j in range(M):
        count = 0
        for k in ks[j][1::]:
            if (i >> k-1)&1 == 1:
                count += 1
        if count%2 == p[j]:
            cnt += 1
    if cnt == M:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#2bit生成　ON=1 OFF=2
import itertools
L = [0,1]
count = 0

N,M = map(int,input().split())
k = []
s = []

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

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

bit_list = list(itertools.product([0,1],repeat = N))

for i in bit_list:
    
    for j in range(M):
        #電球Mのチェック
        counter = 0
        tmp = list(s[j])
        
        for l in tmp:
            if i[l-1] == 1:
                counter += 1
        
        if counter % 2 != p[j-1]:
            break
        
        if j == M-1:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
#2bit生成　ON=1 OFF=2
import itertools
L = [0,1]
count = 0

N,M = map(int,input().split())
k = []
s = []

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

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

bit_list = list(itertools.product([0,1],repeat = N))

for i in bit_list:
    #i番目のチェック
    # print(i)
    
    for j in range(M):
        #電球Mのチェック
        counter = 0
        tmp = list(s[j])
        # print(tmp)
        
        for l in tmp:
            # print(l)
            if i[l-1] == 1:
                counter += 1
        
        if counter % 2 != p[j-1]:
            break
        
        if j == M-1:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import itertools

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


for i in range(m):
    s[i].sort()

cnt = 0
for i in range(2 ** m):
    STATE = []
    digit = len(format(i, 'b'))
    N = int(format(i, 'b'))
    for j in range(digit):
        if ((i >> j) & 1):
            STATE.append(j + 1)
    for k in range(m):
        tmp = []
        if p[k] == 1:
            for l in range(1, len(s), 2):  
                for o, _ in enumerate(s, l):
                    for p in itertools.permutations(s, o):
                        tmp.append(o)
        else:
            for l in range(2, len(s), 2):
                for o, _ in enumerate(s,l):
                    for p in itertools.permutations(s, o):
                        tmp.append(o)
        if STATE == tmp:
            cnt += 1
print(cnt)

Submission status: Wrong Answer

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

ans = 0
for i in range(1 << N):
  f = True
  for j in range(M):
    tmp = 0
    for k in range(1,S[j][0]):
      if ((i >> S[j][k]) & 1):
        tmp += 1
    tmp %= 2
    if tmp != P[j]:
      f = False
  if f:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#N個のスイッチ（1,2,3,...,10）M個の電球（1,2,3,...,10）
N, M = map(int, input().split())
Light_list = []
for _ in range(M):
    Light_list.append(list(map(lambda x:x-1, list(map(int, input().split())))))
Light_requirement_list = list(map(int, input().split()))

for  idx, Light_list_element in enumerate(Light_list):
    Light_list_element.append(Light_requirement_list[idx])
    Light_list_element.pop(0)
#ここまででLight_list[i]の末尾に1か2かの条件が入る
#例　[[0, 1, 0], [1, 1]]

import itertools
#switch_state_list[i][j]はiパターン目のj番目のスイッチの状態を'On''Off'で返す
#例　[('On', 'On'), ('On', 'Off'), ('Off', 'On'), ('Off', 'Off')]
switch_state_list = list(itertools.product(('On', 'Off'), repeat=N))

Ans_list = []
for Light_list_element in Light_list:
    p = Light_list_element.pop()
    for switch_state_list_element in switch_state_list:
        cnt = 0
        for Light_idx in Light_list_element:
            if switch_state_list_element[Light_idx] == 'On':
                cnt += 1
        if cnt % 2 == p:
            Ans_list.append(switch_state_list_element)
            
import collections
c = collections.Counter(Ans_list).most_common()

cnt = 0
for i in c:
    if i[1] == 2:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

A=[]
total=0
count=0
flag=0
for j in range(M+1):
    A.append(list(map(int, input().split())))

for i in range(2**N):
    switch=format(i,'b')
    switch=switch[::-1]+'0000000000'
    

    for a in range(M):
        for b in range(1,len(A[a])):
            
            count += int(switch[int(A[a][b])-1])
            

        if count%2!=A[M][a]:
            flag=1
    if flag==0:
        total +=1
    flag=0
    count=0



print(total)

Submission status: Wrong Answer

Solution code:
N,K = map(int, input().split())
cnt = 0
while 2**cnt < K:
    cnt += 1
result = ((1/2)**cnt)/N
for i in range(2,N+1):
    while (2**cnt)+(2**cnt)*(i-1) >= K and cnt >= 0:
        cnt -= 1
    if cnt == -1:
        result += (N-i+1)/N
        break
    cnt += 1
    result += ((1/2)**cnt)/N
print(result)

Submission status: Wrong Answer

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

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

S = [list(map(int,input().split())) for _ in range(M)]
P = list(map(int,input().split()))
K = [S[i][0] for i in range(M)]
#print("S",S)
#print("P",P)
#print("K",K)

ans = 0

for i in range(2**N):
    switch = [0]*N
    flag = 0
    for j in range(M):
        if i >> j  & 1:
            switch[j] = 1
    #print(switch)
    for j in range(M):
        tmp = 0
        for k in range(1,K[j]+1):
            if switch[S[j][k] - 1] == 1:
                tmp += 1#switch on の数
        #print("tmp",tmp)
        if tmp % 2 == P[j]:
            continue
        else:
            flag = 1
            break
    if not flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

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

S = [list(map(int,input().split())) for _ in range(M)]
P = list(map(int,input().split()))
K = [S[i][0] for i in range(M)]
#print("S",S)
#print("P",P)
#print("K",K)

ans = 0

for i in range(2**N):
    switch = [0]*N
    for j in range(M):
        if i >> j  & 1:
            switch[j] = 1
    flag = 0
    #print(switch)
    for j in range(M):
        tmp = 0
        for k in range(1,K[j]+1):
            if switch[S[j][k] - 1] == 1:
                tmp += 1#switch on の数
        #print("tmp",tmp)
        if tmp % 2 != P[j]:
            flag = 1
            break
    if not flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

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

S = [list(map(int,input().split())) for _ in range(M)]
P = list(map(int,input().split()))
K = [S[i][0] for i in range(M)]
#print("S",S)
#print("P",P)
#print("K",K)

ans = 0

for i in range(2**N):
    switch = [0]*N
    for j in range(M):
        if i >> j  & 1:
            switch[j] = 1
    tmp = 0
    flag = 0
    #print(switch)
    for j in range(M):
        for k in range(1,K[j]+1):
            if switch[S[j][k] - 1] == 1:
                tmp += 1#switch on の数
        #print("tmp",tmp)
        if tmp % 2 != P[j]:
            flag = 1
            break
    if not flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

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()))
a=0
for n in range(2**N):
    s_count=0
    pattern=[i for i in range(n) if n & (1<<i)]
    for j,s in enumerate(S):
        on=0
        for t in s:
            if t-1 in pattern:
                on|=1<<t-1
        s_count^=on
        if bin(s_count).count("1")%2!=P[j]:
            break
    else:
        a+=1
print(a)

Submission status: Wrong Answer

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()))
a=0
for n in range(2**N):
    s_count=0
    for j,s in enumerate(S):
        count=0
        for t in s:
            if n &(1<<t):
               count|=1<<t
        s_count^=count
        if bin(s_count).count("1")%2!=P[j]:
            break
    else:
        a+=1
print(a)

Submission status: Wrong Answer

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()))

a=0
for n in range(2**N):
    s_count=0
    flgs=[]
    for j,s in enumerate(S):
        count=0
        for t in s:
            if n &(1<<t):
               count|=1<<t
        s_count^=count
        if bin(s_count).count("1")%2==P[j]:
           flgs.append(True) 
        else:
            flgs.append(False)
    if all(flgs):
        a+=1
print(a)