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:
n,m=map(int, input().split())
x = [list(map(int, input().split())) for i in range(m)]
p = [list(map(int, input().split()))]
v=pow(2,n)

print(v//pow(2,m))

Submission status: Wrong Answer

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

total_ans=0
for i in range(2**N):
    s=str(bin(i))[2:]
    s='0'*(N-len(s))+s
    
    ans=0
    for a, q in zip(A,p):
        
        total=0
        for item in a:
            #print(s[item-1])
            if s[item-1]=='1':
                total+=1
        #print(total,q, total%2)
        if total%2==int(q):
            ans+=1
    if ans==N:
        total_ans+=1
            
print(total_ans)

Submission status: Wrong Answer

Solution code:
import itertools

def main():
    n,m=list(map(int,input().split(' ')))
    swich_all=list(itertools.product([0,1],repeat=n))
    swich=[]
    cnt =0
    for i in range(m):
        swich.append(list(map(int,input().split(' '))))
    check_p=list(map(int,input().split(' ')))
    for i in swich_all:
        check=0
        check_2=0
        for j in range(m):
            for k in range(swich[j][0]):
                check += i[swich[j][k]-1]
            if check%2 ==check_p[j]:
                check_2 +=1
        if check_2 ==m:
            cnt+=1
    print(cnt)

main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

for m in range(M):
    row = [int(v)-1 for v in input().split()]
    row = row[1:]
    for n in range(N):
        if n in row: matrix[m, n] = 1

p = [int(v) for v in input().split()]
p = np.array([p]).T
matrix = np.hstack([matrix, p])
rank = np.linalg.matrix_rank(matrix)

if N < rank:
    if not any(p): print(1)
    else: print(0)
else:
    print(2**(N-rank))

Submission status: Wrong Answer

Solution code:
import itertools

switch, light = map(int, input().split())
ksm = []
for i in range(1, light+1):
    ks = input().split()
    ksm.append(ks)

pm = input().split()

ans = 0
for i in itertools.product([0, 1], repeat=switch):
    isOk = True
    for li in range(light):
        p = pm[li]
        ks = ksm[li]
        light_sum = 0
        for ksi in range(int(ks[0])):
            light_sum += i[int(ks[ksi + 1]) - 1]
        if light_sum % 2 != p:
            isOk = False
    if isOk:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

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


all_sws = []
for i in range(M):
    elms = list(map(int, input().split(" ")))
    k = elms[0]
    sws = elms[1:]
    all_sws += sws

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

set_sws = set(all_sws)
col_sw = collections.Counter(all_sws)

#print(all_sws)
print(len(set_sws), N)
if N > M:
    shisu = N - M

    out = 2 ** (shisu)
    print(out)

else:
    sval = 0
    for key, val in col_sw.items():
        sval += val
    sval = sval % 2

    s_p = sum(ps)
    if s_p == sval:
        print(1)
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
import copy
class Lamp:

    def __init__(self, id, connected_switches):
        self.id = id
        self.on_number = 0
        self.connected_switches = connected_switches
        self.connected_number = len(connected_switches)

    def set_on_number(self, on_number):
        self.on_number = on_number


inp = input()
st = inp.split()
n = int(st[0])
m = int(st[1])
lamp_dictionary = {}
lamp_list = []
for i in range(m):
    inp = input()
    st = inp.split()
    k = int(st[0])
    connected_switches = []
    for j in range(k):
        s = int(st[j+1])
        connected_switches.append(s)
    lamp_list.append(Lamp(i+1, connected_switches))
# input p
inp = input()
st = inp.split()
for i in range(m):
    p = int(st[i])
    lamp_c = lamp_list[i]
    lamp_c.set_on_number(p)
    k = lamp_c.connected_number
    if k in lamp_dictionary:
        lamps = lamp_dictionary[k]
        lamps.append(lamp_c)
    else:
        lamp_dictionary[k] = [lamp_c]

lamp_sorted_list = sorted(lamp_dictionary.keys())  # つながっているスイッチの少ない順
lamps_list = []  # 小さい順に並べたlampのりすと
for connected_number in lamp_sorted_list:
    lamps = lamp_dictionary[connected_number]
    for lamp in lamps:
        lamps_list.append(lamp)
# スウイッチを決定していく
switch_list = [0 for _ in range(n+1)]  # 0:not decided 1:on 2:off

def decide_switch(i):
    # 可能な数を返す
    if i == len(lamps_list):
        return 1
    lamp = lamps_list[i]
    able_decide_switches = []
    on_count = 0
    for switch in lamp.connected_switches:
        if switch_list[switch] == 0:
            able_decide_switches.append(switch)
        elif switch_list[switch] == 1:
            on_count += 1
    # 少なくとも可能なスイッチのパターが一つあれば次のランプを調べる
    p = lamp.on_number
    if not able_decide_switches:
        if on_count % 2 == p:
            return decide_switch(i+1)
        else:
            return 0
    else:
        # スイッチを変えられる.変えられる可能性すべてを調べる
        changing_list = make_list([], 1, len(able_decide_switches))
        total_able_change_count = 0
        if not changing_list:
            print("")
        for chang in changing_list:
            count = on_count
            for num in chang:
                count += num
            if count % 2 == p:
                # 次のランプを調べる
                for inde, num in enumerate(chang):
                    v = num
                    if num == 0:
                        v = 2
                    switch_list[able_decide_switches[inde]] = v
                total_able_change_count += decide_switch(i+1)
                # すいっちを0にもどす
                for inde, num in enumerate(chang):
                    switch_list[able_decide_switches[inde]] = 0
        return total_able_change_count


def make_list(l, i, max_n):
    ol = copy.deepcopy(l)
    il = copy.deepcopy(l)
    ol.append(0)
    il.append(1)
    if i == max_n:
        return [ol, il]
    ooo = make_list(ol, i+1, max_n)
    iii = make_list(il, i+1, max_n)
    for ii in iii:
        ooo.append(ii)
    return ooo
    # return make_list(ol, i+1, max_n).extend(make_list(il, i+1, max_n))

ans = decide_switch(0)
print(int(ans/2))

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
lamplist = []
for i in range(M):
    A = list(map(int, input().split()))
    lamplist.append(A)
oddeven_ans = list(map(int, input().split()))
print("{}".format(oddeven_ans))
print("{}".format(lamplist))
switch = np.zeros(N)
ans = 0
for j in range(N * N):
    flag = 0
    oddeven = 0
    for k in range(N):
        switch[k] = j % 2
        j //= 2
    print("{}".format(switch))
    for p in range(M):
        for r in range(1, lamplist[p][0]):
            if switch[lamplist[p][r] - 1] == 1:
                oddeven += 1
        if (int(oddeven % 2)) != int(oddeven_ans[p]):
            flag = 1
    if flag == 0:
        ans += 1
        
print("{}".format(ans))

Submission status: Wrong Answer

Solution code:
import itertools

N,M = map(int,input().split())
KS = [list(map(int,input().split())) for i in range(M)]
P = list(map(int,input().split()))
l = []
nums = [0,1]
count = 0
for b in itertools.product(nums, repeat=N):
    c_denkyu = 0
    for sw in KS:
        c_sw = 0
        for i in sw[1:]:
            if b[i-1] == 1:
                c_sw += 1
        if c_sw%2 == 0 and c_sw > 0:
            c_denkyu += 1
    if c_denkyu == N:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split(' '))
k = []
s = []
for i in range(M):
    ksi = list(map(int, input().split(' ')))
    ki = ksi.pop(0)
    si = ksi
    k.append(ki)
    s.append(si)
p = list(map(int, input().split(' ')))

cnt = 0
for i in range(M):
    flag = True
    for j in range(i+1, M):
        if s[i] == s[j]:
            flag = False
            break
    if flag is True:
        cnt += 1
num = (int)(2**(N-cnt))
print(num)

Submission status: Wrong Answer

Solution code:
#C
#switch: 1,2,...N
#bulb: 1,...M
#bulb_i is connected to k_i switches: si1, si2,...sik_i
#bulb_i = 1 iff sum(si1,...sik_i) % 2 == p_i
#p_i = {0, 1}
N, M = map(int,input().split())
maxsig = 2**N
mask_l = []
for _ in range(M):
    li = input().split()
    k = li[0]
    s = list(map(int,li[1:])) #list
    mask = 0
    for itm in s:
        mask += 2**(itm-1)
    mask_l.append(mask)
p = list(map(int,input().split()))
ans = 0
flg = False
for num in range(maxsig):
    for b in range(M):
        mask = mask_l[b]
        dp = p[b]
        if sum(map(int,list(bin(num & mask)[2:]))) // 2 != dp:
            flg = True
            break
    if flg == False : ans += 1
    else: flg = False
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n, m = input().split()
N = int(n)
M = int(m)

K = []
for i in range(M):
    K.append(list(map(int, input().strip().split(' '))))

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

SW = {0, 1}
SWlist = list(itertools.product(SW, repeat=N))

result = 0
fflag = False

for i in range(len(SWlist)):
    for j in range(len(K)):
        count = 0
        for k in range(K[j][0]):
            if SWlist[i][k] == 1:
                count += 1
        if count % 2 != P[j]:
            fflag = True
            break
    if not fflag:
        result += 1
    else:
        fflag = False
print(result)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import itertools
N,M=[int(x) for x in stdin.readline().rstrip().split()]
data=[]
for i in range(M):
    data.append([int(x) for x in stdin.readline().rstrip().split()])
P=[int(x) for x in stdin.readline().rstrip().split()]
ans=0
for n in list(itertools.product([0,1],repeat=N)):
    for ind,j in enumerate(data):
        flag = True
        fired=0
        for k in j[1:]:
            if n[k-1] == 1:
                fired+=1
            if int(fired%2) != P[ind]:
                flag = False
        if flag:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
#入力取得
N, M = map(int, input().split())

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

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


result = 0


if N == 1 and M == 1:
    print(1)


else:
    for i in range(2**N):
        bin_str = format(i, 'b')
        bin_str = bin_str.zfill(N)


        flag = 1

        for j in range(len(k)):

            tmp_sum = 0


            for l in range(len(k[j])):
                if l != 0:
                    tmp_sum += int(bin_str[-l])

            equal_p = tmp_sum % 2

            if equal_p % 2 == p[j]:
                flag = 1

            if equal_p % 2 != p[j]:
                flag = 0
                break

        if  flag == 0:
            continue

        if flag == 1:
            result += 1
            # print(bin_str)



    print(result)

Submission status: Wrong Answer

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

l = max(ks[0])
for m in range(1,M):
    l = max(l,max(ks[m]))

ans = 0

for i in range(1 << l):
    cnt_on = [0]*M
    for j in range(l):
        if ((i >> j) & 1) == 1:
            for m in range(M):
                cnt_on[m]+=ks[m][1:].count(j)
                

    f = True
    for m in range(M):
        if cnt_on[m]%2 != p[m]:
            f = False
            break
    
    if f:
        ans += 1


print(ans)

Submission status: Wrong Answer

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

ans_cnt = 0
for i in range(2**N):
    condition_cnt = 0
    for j in range(M):

        cnt=0
        for k in connections[j][1:]:
            if (i >> k) & 1:
                cnt += 1
        if (cnt +conditions[j])%2 == 0:
            condition_cnt += 1
    if condition_cnt == M:
        ans_cnt += 1

print(ans_cnt)

Submission status: Wrong Answer

Solution code:
o=lambda:map(int,input().split())
n,m=o()
l=[list(o())[1:]for _ in range(m)]
l=[''.join('1'if e+1 in c else'0'for e in range(m))[::-1]for c in l]
p=list(o())
t="%0{}d".format(n)
r=0
for i in range(2**n):
  q=t%int(bin(i).replace("0b",""))
  f=[]
  for c in l:
    v=int(q,2)&int(c,2)
    f+=[sum(map(int,bin(v).replace("0b","")))%2]
  r+= f == p
print(r)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

for m in range(M):
    row = [int(v)-1 for v in input().split()]
    row = row[1:]
    for n in range(N):
        if n in row: matrix[m, n] = 1

p = [int(v) for v in input().split()]
p = np.array([p]).T
matrix = np.hstack([matrix, p])
rank = np.linalg.matrix_rank(matrix)

if N < rank:
    print(0)
elif not any(p):
    print(1)
else:
    print(2**(N-rank))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
n,m=map(int,input().split())
l=[]
for i in range(m):
    a=input().split()
    l.append(a)
p=list(map(int,input().split()))

l2=[0]*10
ans=0
num=0
for a in range(0,2):
    for b in range(0,2):
        for c in range(0,2):
            for d in range(0,2):
                for e in range(0,2):
                    for f in range(0,2):
                        for g in range(0,2):
                            for h in range(0,2):
                                for i in range(0,2):
                                    for j in range(0,2):
                                        if num>2**n-1:
                                            break
                                        else:
                                           l2[0]=a
                                           l2[1]=b
                                           l2[2]=c
                                           l2[3]=d
                                           l2[4]=e
                                           l2[5]=f
                                           l2[6]=g
                                           l2[7]=h
                                           l2[8]=i
                                           l2[9]=j
                                           num+=1
                                         
for aa in l2:
    for bb in l:
        pp=0
        nn=0
        for cc in range(len(bb)):
            pp=pp+int(bb[cc-1])
        if pp%2==p[nn]:
            ans+=1
        nn+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n, m = input().split()
N = int(n)
M = int(m)

K = []
for i in range(M):
    K.append(list(map(int, input().strip().split(' '))))

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

SW = {0, 1}
SWlist = list(itertools.product(SW, repeat=N))

result = 0
fflag = False

for i in range(len(SWlist)):
    for j in range(len(K)):
        count = 0
        for k in range(K[j][0]):
            if SWlist[i][k] == 1:
                count += 1
        if count % 2 != P[j] or count == 0:
            fflag = True
            break
    if not fflag:
        result += 1
    else:
        fflag = False
print(result)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import itertools
N,M=[int(x) for x in stdin.readline().rstrip().split()]
data=[]
for i in range(M):
    data.append([int(x) for x in stdin.readline().rstrip().split()])
P=[int(x) for x in stdin.readline().rstrip().split()]
ans=0
for ind,j in enumerate(data):
    for n in list(itertools.product([0,1],repeat=N)):
        flag = True
        fired=0
        for k in j[1:]:
            if n[k-1] == 1:
                fired+=1
            if int(fired%2) != P[ind]:
                flag = False
    if flag:
      ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int, input().split())
KS=[[0 for i in range(N+1)] for j in range(M)]
for m in range(M):
    KS[m][:]= list(map(int, input().split()))
P = list(map(int, input().split()))
answer=0
A=[0]*N
for x in range(2**N):
    flag = True
    count=0
    a=x
    for i in range(N):
        A[i]=a % 2
        a=int(a/2)
    for m in range(M):
        for y in KS[m][1:]:
            count+=A[y-1]
        if count%2!=P[m]:
            flag=False
    if flag==True:
        answer+=1
print(answer)

Submission status: Wrong Answer

Solution code:
import itertools
N, M = map(int, input().split())
ks = []
k_max = 0
for i in range(M):
	ks_in = list(map(int, input().split()))
	k_max = max(k_max, max(ks_in[1:]))
	ks.append(ks_in)
p = list(map(int, input().split()))

A = [0, 1]
lt = list(itertools.product(A, repeat=k_max))
count = 0
for elem in lt:
	for i in range(M):
		sum = 0
		for j in range(len(ks[i])-1):
			sum += elem[ks[i][j+1]-1]
		if sum % 2 != p[i]:
			break
	else:
		count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
from math import factorial
stdin = sys.stdin

ni = lambda: int(ns()) #int
na = lambda: list(map(int, stdin.readline().split())) #int,list
ns = lambda: stdin.readline().rstrip()  # str
n,m = na()
l=[]
for i in range(m):
	l.append(na()[1:])
p = na()
cnt=0
for i in range(m):
	if p[i]==1:
		s=len(l[i])
		while s>0:
			cnt+=factorial(len(l[i])) / factorial(s) / factorial(len(l[i])-s)
			s-=2
res = [ flatten for inner in l for flatten in inner ]
print(int(2**((n-len(set(res))))*cnt))

Submission status: Wrong Answer

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

ret = [(bin(n)[2:].zfill(N))[::-1] for n in range(2**N)]

# 入力を保持
kss = []
for i in range(M):
  kss.append(input())
ps = list(map(int, input().split()))

#print(ret)

def test(ret):
  if 0 < sum([int(ret[t-1]) for t in tmp]):
    return sum([int(ret[t-1]) for t in tmp]) % 2 == ps[p_i]
  return False

# 処理
p_i = 0
for ks in kss:
  l = list(map(int, ks.split()))
  tmp = l[1:]
  ret = list(filter(test, ret))
  if ret == None:
    break
  p_i = p_i + 1
#  print(ret)

if ret != None:
  print(len(ret))
else:
  print(0)

Submission status: Wrong Answer

Solution code:
from itertools import product

N,M = map(int, input().split() )
k_list = []
for i in range(M):
    k_i_list = [int(s) for s in input().split()]
    k_list.append(k_i_list)

p_list =  [int(t) for t in input().split()]

counter = 0
temp_counter = 0
isOn = 1
## スイッチすべての可能性に対して
for u in product([0,1], repeat=N):
    isOn = 1
    ## 各電球に対して
    for v in range(M):
        ## 各電球が対応するスイッチに対して
        for w in range(int(k_list[v][0])):
            temp_counter += u[w]
        if temp_counter %2 != p_list[v]:
            isOn = 0
            # break
    if isOn == 1:
        counter += 1

print(str(counter))

Submission status: Wrong Answer

Solution code:
#入力取得
N, M = map(int, input().split())

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

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


result = 0


if N == 1 and M == 1:
    print(1)


else:
    for i in range(2**N):
        bin_str = format(i, 'b')
        bin_str = bin_str.zfill(N)


        flag = 1

        for j in range(len(k)):

            tmp_sum = 0


            for l in range(len(k[j])):
                if l != 0:
                    tmp_sum += int(bin_str[-(l-1)])

            equal_p = tmp_sum % 2

            if equal_p % 2 == p[j]:
                flag = 1

            if equal_p % 2 != p[j]:
                flag = 0
                break

        if  flag == 0:
            continue

        if flag == 1:
            result += 1
            # print(bin_str)



    print(result)

Submission status: Wrong Answer

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

klist = []
sdict = {}
for m in range(M):
    tmp = list(map(int, input().split()))
    klist.append(tmp[0])
    sdict[m] = tmp[1:]
plist = list(map(int, input().split()))

def solve(N, plist, switch_num):
    global M
    num = 0

    if N == 1:
        idx = []
        idx2 = []
        for m in range(M):
            if switch_num in sdict[m]:
                idx.append(plist[m])
            else:
                idx2.append(plist[m])
        if sum(idx) == len(idx):
            if sum(idx2) == 0:
                return 1
            else:
                return 0
        elif sum(idx) == 0:
            if sum(idx2) == 0:
                return 2
            else:
                return 0
        else:
            return 0

    # switch1 == OFF
    new_plist = plist
    num += solve(N-1, new_plist, switch_num+1)
    
    # switch1 == ON
    new_plist = []
    for i in range(M):
        if switch_num in sdict[i]:
            new_plist.append(1 - plist[i])
        else:
            new_plist.append(plist[i])
    num += solve(N-1, new_plist, switch_num+1)

    return num

print(solve(N, plist, 1))

Submission status: Wrong Answer

Solution code:
from itertools import product

N,M = map(int, input().split() )
k_list = []
for i in range(M):
    k_i_list = [int(s) for s in input().split()]
    k_list.append(k_i_list)

p_list =  [int(t) for t in input().split()]

counter = 0
temp_counter = 0
isOn = 1
## スイッチすべての可能性に対して
for u in product([0,1], repeat=N):
    isOn = 1
    ## 各電球に対して
    for v in range(M):
        ## 各電球が対応するスイッチに対して
        for w in range(int(k_list[v][0])):
            temp_counter += u[w]
        if temp_counter %2 != p_list[v]:
            isOn = 0
            break
    if isOn == 1:
        counter += 1

print(str(counter))

Submission status: Wrong Answer

Solution code:
import itertools
N, M = map(int, input().split())
list1 = []
kli = []
for i in range(M):
    cur_li = list(map(int, input().split()))
    list1.append(cur_li[1:])
    kli.append(cur_li[0])
pli = list(map(int,input().split()))
anslist = []
kosu_g = []
kosu_k = []
if pli[0] == 0:
    for i in range(1,N):
        if i%2 ==0:
            kosu_g.append(i)
    for i in kosu_g:
        c_list = list(itertools.combinations(list1[0], i))
        anslist = anslist + c_list
if pli[0] == 1:
    for i in range(1,N):
        if i%2 ==1:
            kosu_k.append(i)
    for i in kosu_k:
        c_list = list(itertools.combinations(list1[0], i))
        anslist = anslist + c_list
    anslist.append([""])
for i in range(1,M):
    curlist =[]
    if pli[i] == 0:
        for j in kosu_g:
            c_list = list(itertools.combinations(list1[i], j))
            curlist = curlist + c_list
        curlist.append([""])
        for j in anslist:
            if j in curlist:
                pass
            else:
                anslist.remove(j)
    if pli[i] == 1:
        for j in kosu_k:
            c_list = list(itertools.combinations(list1[i], j))
            curlist = curlist + c_list
        for j in anslist:
            if j in curlist:
                pass
            else:
                anslist.remove(j)
print(2**len(anslist))

Submission status: Wrong Answer

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

result = 0
sij = [i + 1 for i in range(N)]
for m in sij:
    c = itertools.combinations(sij, m)
    for kumi in c:
        flag = True
        for i in range(M):
            # ついてる個数
            kosuu = len(set(K[i][1:]) & set(kumi))
            if kosuu == 0:
                continue
            if kosuu % 2 != P[i]:
                flag = False
        if flag is True:
            result += 1
print(result)

Submission status: Wrong Answer

Solution code:
import itertools

n, m = input().split()
N = int(n)
M = int(m)

K = []
for i in range(M):
    K.append(list(map(int, input().strip().split(' '))))

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

SW = {0, 1}
SWlist = list(itertools.product(SW, repeat=N))

result = 0
fflag = False
for i in range(len(SWlist)):
    count = 0
    for j in range(len(K)):
        for k in range(K[j][0]):
            if SWlist[i][k] == 1:
                count += 1
        if count % 2 != P[j] or count == 0:
            fflag = True
            break
    if not fflag:
        result += 1
    else:
        fflag = False
print(result)

Submission status: Wrong Answer

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

inputs = input().split(' ')
N = int(inputs[0])
M = int(inputs[1])

lights = []
for i in range(M):
    switch = input().split(' ')[1:]
    switch = [int(s) for s in switch]
    lights.append(switch)

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

combi = 0
for i in range(2**N):
    i = str(bin(i)).split('0b')[1]
    if len(i) < N:
        i = '0'*(N-len(i)) + i
    flag = True
    on = 0
    for j, switch in enumerate(lights):
        for s in switch:
            if i[s-1] == '1':
                on += 1
        if (on%2) != p[j]:
            flag = False
            break
    if flag:
        combi += 1

print(combi)

Submission status: Wrong Answer

Solution code:
import math, string
# 10進数整数を2進数文字列に変換する関数
# decimal : 10進数整数
# press   : 上位桁の0を切り詰めるフラグ
def toBinary(decimal, press=True):
    if decimal == 0: return '0'
    bin_str = ""
    i = 31
    while i >= 0:
        bi = int((decimal & int(math.pow(2, i))) >> i)
        bin_str += str(bi)
        i -= 1
    if press:
        try:
            bin_str = bin_str[bin_str.index('1'):]
        except ValueError:
            print('error')
            bin_str = '0'
    return bin_str

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

even_or_odd=list(map(int,input().split()))
pattern_list=[]
ans =0
for i in range(2**N):
    bin_temp = toBinary(i).rjust(N,'0')
    bin_temp=bin_temp[::-1]
    pattern_list.append(bin_temp)
    
    for index,light in enumerate(light_list):
        light_count=0
        for switch_num in light:
            light_count += int(bin_temp[switch_num-1])
    if light_count%2 != even_or_odd[index]:
        continue
    ans += 1
            


print(ans//2)

Submission status: Wrong Answer

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

combs = []
def helper(n, sofar):
    if n == 0:
        combs.append(sofar)
        return
    else:
        helper(n-1,sofar+"0")
        helper(n-1,sofar+"1")
helper(n,"")
counter = 0
ans = []

while len(combs) > 0:
    temp = combs.pop()
    tempcheck = 1
    pindex = 0
    for index,value in enumerate(ks):
        switchon = 0
        for i, v in enumerate(value):
            if i == 0:
                continue
            if temp[i-1] == "1":
                switchon += 1

        a = switchon%2
        if p[pindex] != a:
            tempcheck = 0
            break
        pindex += 1
    if tempcheck == 1:
        counter += 1
print(counter)

Submission status: Wrong Answer

Solution code:
import itertools
N, M = map(int, input().split())
list1 = []
kli = []
for i in range(M):
    cur_li = list(map(int, input().split()))
    list1.append(cur_li[1:])
    kli.append(cur_li[0])
pli = list(map(int,input().split()))
anslist = []
kosu_g = []
kosu_k = []
if pli[0] == 0:
    for i in range(1,N):
        if i%2 ==0:
            kosu_g.append(i)
    for i in kosu_g:
        c_list = list(itertools.combinations(list1[0], i))
        anslist = anslist + c_list
if pli[0] == 1:
    for i in range(1,N):
        if i%2 ==1:
            kosu_k.append(i)
    for i in kosu_k:
        c_list = list(itertools.combinations(list1[0], i))
        anslist = anslist + c_list
    anslist.append([""])
for i in range(1,M):
    curlist =[]
    if pli[i] == 0:
        for j in kosu_g:
            c_list = list(itertools.combinations(list1[i], j))
            curlist = curlist + c_list
        curlist.append([""])
        for j in anslist:
            if j in curlist:
                pass
            else:
                anslist.remove(j)
    if pli[i] == 1:
        for j in kosu_k:
            c_list = list(itertools.combinations(list1[i], j))
            curlist = curlist + c_list
        for j in anslist:
            if j in curlist:
                pass
            else:
                anslist.remove(j)
print(len(anslist))

Submission status: Wrong Answer

Solution code:
import copy
N,M=map(int,input().split())
linkedBulb=[[] for i in range(N)]#各スイッチごとにつながってる電球
for i in range(M):
    S=[int(_) for _ in input().split()]
    for n,s in enumerate(S):
        if n==0:continue
        else:
            linkedBulb[s-1].append(i)
s=[1-int(i) for i in input().split()]
ans=0
for bit in range(2**N):
    start=copy.deepcopy(s)
    for j in range(N):
        if (bit>>j)&1:
            for todo in linkedBulb[j]:
                start[todo]=1-start[todo]
    if all(start):ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
def iterator(n):
    for i in range(pow(2, n)):
        res = []
        for s in range(n):
            if i & (1 << s):
                res.append(s)
        if len(res) > 0:
            yield res


n, m = map(int, input().split())
sws = [[0] * n for _ in range(m)]

for i in range(m):
    k, *s = map(int, input().split())
    for si in s:
        sws[i][si - 1] = 1

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

ans = 0
for on in iterator(n):
    state = [0 for _ in range(m)]
    for ln, sw in enumerate(sws):
        count = 0
        for o in on:
            if sw[o] == 1:
                count += 1
        if count > 0 and count % 2 == p[ln]:
            state[ln] = 1
    if state.count(1) == m:
        ans += 1

print(ans)