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())
light = [
    tuple(map(int, input().split())) for i in range(m)
]
light = sorted(light, key=lambda x: x[0])
p = tuple(map(int, input().split()))

ans = 0
for i in range(2**n+1):
    x = str(bin(i))[2:]
    if len(x) < n:
        x = "0" * (n - len(x)) + x
    a = 1
    for j in range(m):
        check = 0
        for k in light[j][1:]:
            if x[k-1] == "1":
                check += 1
        if check % 2 == p[j]:
            pass
        else:
            a = 0
            break
    if a:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
light = [
    tuple(map(int, input().split())) for i in range(m)
]
light = sorted(light, key=lambda x: x[0])
p = tuple(map(int, input().split()))

ans = 0
for i in range(2**n):
    x = str(bin(i))[2:]
    if len(x) < n:
        x = "0" * (n - len(x)) + x
    a = 1
    for j in range(m):
        check = 0
        for k in light[j][1:]:
            if x[k-1] == "1":
                check += 1
        if check % 2 == p[j]:
            pass
        else:
            a = 0
            break
    if a:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m = map(int, input().split())
light = [
    tuple(map(int, input().split())) for i in range(m)
]
light = sorted(light, key=lambda x: x[0])
p = tuple(map(int, input().split()))

ans = 0
for i in range(2**n):
    x = str(bin(i))[2:]
    if len(x) < n:
        x = "0" * (n - len(x)) + x
    a = 1
    for j in range(m):
        check = 0
        for k in light[j][1:]:
            if x[k-1] == "1":
                check += 1
        if check % 2 == p[j]:
            pass
        else:
            a = 0
            break
    if a:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

for i in range(2**n+1):
    check2 = [0]*m
    for j in range(n):
        if ((i>>j) & 1):
            for k in range(m):
                
                if j+1 in check[k]:
                    check2[k] += 1
                    
    check3 = True
    for l in range(m):
        if check2[l]%2 != p[l]:
            check3 = False
    if check3 :
        count += 1
        

print(count)

Submission status: Wrong Answer

Solution code:
import itertools

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

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

li = [0,1]
ans = 0
for elm in itertools.product(li,repeat=n):
    for i in range(m):
        mm = 0
        for j in range(len(s[i])-1):
            if elm[s[i][j]-1]==1:
                mm += 1
        if mm%2!=p[i]:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
k=[0]*m
s=[[]for _ in range(m)]
for i in range(m):
  k[i], *s[i] = map(int, input().split())
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
  res=0
  for a in range(m):
    tmp=p[a]
    for j in s[a]:
      if (i >> (j-1)) & 1:
        tmp^=1
    res+=tmp
  if res==m:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
k=[0]*m
s=[[]for _ in range(m)]
for i in range(m):
  k[i], *s[i] = map(int, input().split())
ans=0
for i in range(2**n):
  res=0
  for a in range(m):
    tmp=0
    for j in s[a]:
      if (i >> (j-1)) & 1:
        tmp^=1
    res+=tmp
  if res==m:
    ans+=1
print(ans)

Submission status: Wrong Answer

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

N, M = map(int, input().split())
l_list = []
for _ in range(M):
    data = list(map(int, input().split()))[1:]
    l_list.append(sum(2**(x-1) for x in data))

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

# ビット全探索
count = 0
for sw in range(2**N):
    for l, p in zip(l_list, p_list):
        A = l & sw
        A = (0x55555555 & A) + ((0xAAAAAAAA & A)>>1)
        A = (0x33333333 & A) + ((0xCCCCCCCC & A)>>2)
        A = (0x0f0f0f0f & A) + ((0xf0f0f0f0 & A)>>3)
        A = (0x00ff00ff & A) + ((0xff00ff00 & A)>>4)
        A = (0x0000ffff & A) + ((0xffff0000 & A)>>5)
        if A % 2 != p:
            break
    else:
        count += 1
print(count)

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(m):
    s[i].pop(0)

#print(s)
for i in range(2**n):
    tmp = [False] * m
    for j in range(m):
        if (i>>j) & 1:
            for k in range(m):
                if (j+1) in s[k]:
                    tmp[k] = not tmp[k]
    #print(tmp,p)
    if tmp == p:
        ans += 1
print(ans)

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(bool,input().split()))
ans = 0
for i in range(2**n):
    tmp = [False] * m
    for j in range(m):
        if (i>>j) & 1:
            tmp[j] = not tmp[j]
    if tmp == p:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

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

def judge(x):
    for i in range(M):
        if not((k-len(S[i]-x)) % 2 == P[i]):
            return False
    return True

res = 0
for bit in range(2**N):
    on = set()
    for i in range(N):
        if bit & (2**i):
            on.add(i)
    if judge(on):
        res += 1

print(res)

Submission status: Wrong Answer

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

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

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

# print(s)

def isAllOn(n):
    # print('\nn:', n)
    for i in range(m):
        # print('Light:', i)
        bitCnt = 0
        for j in range(len(s[i])):
            pos = s[i][j] - 1
            # print('pos:', pos)
            bit = (n >> pos) & 1
            if bit == 1:
                bitCnt += 1
        if bitCnt % 2 != p[i]:
            # print('False!')
            return False

    return True

ans = 0

for i in range(2**n+1):
    if isAllOn(i):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
x = [list(map(int,input().split())) for i in range(m)]
eo = list(map(int,input().split()))
ans = 0
for i in range(2**n):
  sw = [0]*n
  binstr = format(i,"b").zfill(n)
  for j in range(n):
    if binstr[j] == "1":
      sw[j] = 1
  light = 0
  for k,y in enumerate(x):
    numsw = 0
    for z in range(1,y[0]+1):
      if sw[z-1] == 1:
        numsw += 1  
    if numsw%2 == eo[k]:
      light += 1
  if light == m:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

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

ans=0
for i in range(2**N):
  for j in range(M):
    cnt=0
    for k in L[j]:
      cnt+=A[i][k-1]
    if P[j]!=(cnt%2):
      break
ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
lis = []
count = 0
temp = 0
flag = True
for _ in range(M):
  In = list(map(int,input().split()))
  lis.append(In)
p = list(map(int,input().split()))
for i in range(2**N):
  flag = True
  for j in range(M):
    temp = 0
    for k in range(1,lis[j][0]):
      temp += int((i>>(lis[j][k]-1))&1)
    if temp%2 != p[j]:
      flag = False
  if flag:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
lis = []
count = 0
temp = 0
flag = True
for _ in range(M):
  In = list(map(int,input().split()))
  lis.append(In)
p = list(map(int,input().split()))
for i in range(2**N):
  flag = True
  for j in range(M):
    temp = 0
    for k in range(1,lis[j][0]):
      temp += int((i>>(lis[j][k]-1))&1)
      if temp%2 != p[j]:
        flag = False
  if flag:
    print(i)
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
lis = []
count = 0
temp = 0
flag = True
for _ in range(M):
  In = list(map(int,input().split()))
  lis.append(In)
p = list(map(int,input().split()))
for i in range(2**N):
  flag = True
  for j in range(M):
    temp = 0
    for k in range(1,lis[j][0]):
      temp += (i>>lis[j][k])
      if temp%2 != p[j]:
        flag = False
  if flag:
    count += 1
print(count)

Submission status: Wrong Answer

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

l = []

for _ in range(M):
    k, *s = map(int, input().split())
    l.append(s)

*P, = map(int, input().split())
count = 0
for i in range(2**N):
    switch = ["on"] * N
    m = [False]*M
    for j in range(N):
        if (i>>j) & 1:
            switch[j] = "off"

    switch_count = 0
    n = 0
    #onと繋がっているスイッチを探す。
    for switch_element in switch:
        if switch_element == "on":
            switch_index = n + 1
            for l_element in l:
                if switch_index in l_element:
                    for ind in range(1,len(switch)+1):
                        if ind in l_element and (switch[ind-1] == 'on'):
                            switch_count = switch_count + 1
                    if switch_count%2==P[l.index(l_element)]:
                        m[l.index(l_element)] = True
        n = n + 1
    
    if False in m:
        continue
    count = count + 1
        

print(count)

Submission status: Wrong Answer

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

l = []

for _ in range(M):
    k, *s = map(int, input().split())
    l.append(s)

*P, = map(int, input().split())
count = 0
for i in range(2**N):
    switch = ["on"] * N
    m = [False]*M
    for j in range(N):
        if (i>>j) & 1:
            switch[j] = "off"

    switch_count = 0
    n = 0
    #onと繋がっているスイッチを探す。
    for switch_element in switch:
        if switch_element == "on":
            switch_index = n + 1
            for l_element in l:
                if switch_index in l_element:
                    for ind in range(1,len(switch)+1):
                        if ind in l_element and (switch[ind-1] == 'on'):
                            switch_count = switch_count + 1
                    print(P[l.index(l_element)])
                    if switch_count%2==P[l.index(l_element)]:
                        m[l.index(l_element)] = True
        n = n + 1
    
    if False in m:
        continue
    count = count + 1
        

print(count)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
k = []
s = []
for i in range(m):
    x = tuple(map(int,input().split()))
    k.append(x[0])
    s.append(x[1:])
p = list(map(int,input().split()))
ans = 0
for i in range(1<<n):
    flag = [0] * m
    cnt = 0
    for j,sj in enumerate(s):
        for l in sj:
            if i >> (l-1) & 1:
                cnt += 1
        if cnt % 2 == p[j]:
            flag[j] = 1
    if all(flag):
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
k = []
s = []
for i in range(m):
    x = tuple(map(int,input().split()))
    k.append(x[0])
    s.append(x[1:])
p = list(map(int,input().split()))
ans = 0
for i in range(1<<n):
    flag = [0] * m
    cnt = 0
    for j in range(m):
        for l in s[j]:
            if i >> (l-1) & 1 == 1:
                cnt += 1
        if cnt % 2 == p[j]:
            flag[j] = 1
    if all(flag):
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import combinations


def solve():
    N, M = map(int, input().split())
    k = [0 for _ in range(M)]
    s = [[] for _ in range(M)]
    for i in range(M):
        k[i], *s[i] = map(int, input().split())
    p = list(map(int, input().split()))
    
    ans = 0
    for i in range(1, N+1):
        for on_switches in combinations(range(1, N+1), i):
            flag = True
            for j in range(M):
                count = 0
                for on_switch in on_switches:
                    if on_switch in s[j]:
                        count += 1
                if count % 2 != p[j]:
                    flag = False
                    break
            if flag:
                ans += 1
    
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

    k[i] = tmp[0]
    s.append(tmp[1:])
p = [int(i) for i in input().split()]

answer = 0
for i in range(N ** 2):
    flag = 1 # 1: 全部点灯
    for j in range(M):
        count = 0
        need = s[j]
        for k in need:
            if ((i >> k-1) & 1):
                count += 1
        if np.mod(count, 2) != p[j]:
            flag = 0
    if flag == 1:
        answer += 1

print(answer)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ls = []
for i in range(M):
    tmp = list(map(int,input().split()))
    ls.append(tmp[1:])
p = list(map(int,input().split()))
onof=[bin(x)[2:].zfill(N) for x in list(range(2**N))]
ans = 0
for i in range(len(onof)):
    all = True
    for j in range(M):
        num = 0
        for k in range(len(ls[j])):
            if onof[i][k-1] == "1":
                num += 1
        if num%2 != p[j]:
            all = False
            break
    ans += all
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(M)]
p = list(map(int,input().split()))
onof=[bin(x)[2:].zfill(N) for x in list(range(2**N))]
ans = 0
for i in range(len(onof)):
    flag = True
    for j in range(M):
        count = 0
        for k in range(1,len(ls[j])):
            if onof[i][k-1] == "1":
                count += 1
        if count%2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(M)]
p = list(map(int,input().split()))
onof=[bin(x)[2:].zfill(N) for x in list(range(2**N))]
ans = 0
for i in range(len(onof)):
    flag = True
    for j in range(M):
        if flag == False:
            break
        count = 0
        for k in range(1,len(ls[j])):
            if onof[i][k-1] == "1":
                count += 1
        if count%2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=[]
for i in range(m):
    ks=list(map(int,input().split()))
    s.append(ks[1:])
p=list(map(int,input().split()))
ans=0
for i in range(1<<n):
    cnt=0
    for j in range(m):
        for k in s[j]:
            if i&1<<(k-1):
                cnt+=1
        if cnt%2!=p[j]:
            break
    else:
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product
import numpy as np

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

lst = [list(map(int, input().split())) for _ in range(M)]
p_lst = np.array(list(map(int, input().split())))

ans = 0
mat = [[0]*N for _ in range(M)]

for j, lst2 in enumerate(lst):
    for i in lst2[1:]:
        mat[j-1][i-1] = 1

mat_np = np.array(mat)

for a in product([0, 1], repeat=N):
    l = np.array(a)
    b = np.dot(mat_np, l)%2
    if np.sum(b==p_lst)==M:ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations, product
import numpy as np

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

lst = [list(map(int, input().split())) for _ in range(M)]
p_lst = np.array(list(map(int, input().split())))

ans = 0
Mat = [[0]*N for _ in range(M)]

for j, lst2 in enumerate(lst):
    for i in lst2[1:]:
        Mat[j-1][i-1] = 1

for a in product([0, 1], repeat=N):
    l = np.array(a)
    b = np.dot(Mat, l)%2
    if np.sum(b==p_lst)==M:ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import itertools
N,M = map(int,input().split())
switch = [list(map(int,input().split())) for m in range(M)]
p = list(map(int,input().split()))
S = list(itertools.product([0,1], repeat=N))
ans = 0
for s in S:
    s_ok = 0
    for m in range(M):
        count = 0
        for i in range(1, len(switch[m])):
            if s[switch[m][i]-1] == 1:
                count += 1
        if count%2 == p[m-1]:
            s_ok += 1
        else:
            break
    if s_ok == M:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import copy

N,M = map(int, input().split())
jisho = [[] for i in range(N)]
for i in range(M):
    val = input().split()
    for j in val[1:]:
        jisho[int(j)-1].append(i)

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

sw = []
def create_ki(data):
    if len(data) == N:
        sw.append(data)
        return
    tmp = copy.copy(data)
    tmp.append(0)
    create_ki(tmp)
    tmp2 = copy.copy(data)
    tmp2.append(1)
    create_ki(tmp2)

create_ki([])

ans = 0
for val in sw:
    num = 0
    sw2 = [0]*M
    for i in val:
        if i == 0:
            num += 1
            continue
        data = jisho[num]
        for j in data:
            sw2[j] += 1
        num += 1
    cn = 0
    for j in sw2:
        if j % 2 == p[cn]:
            break
        cn += 1
    if cn == M:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import copy

N,M = map(int, input().split())
jisho = [[] for i in range(N)]
for i in range(M):
    val = input().split()
    for j in val[1:]:
        jisho[int(j)-1].append(i)

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

sw = []
def create_ki(data):
    if len(data) == N:
        sw.append(data)
        return
    tmp = copy.copy(data)
    tmp.append(0)
    create_ki(tmp)
    tmp2 = copy.copy(data)
    tmp2.append(1)
    create_ki(tmp2)

create_ki([])

ans = 0
for val in sw:
    num = 0
    sw2 = [0]*M
    for i in val:
        if i == 0:
            num += 1
            continue
        data = jisho[num]
        for j in data:
            sw2[j] += 1
        num += 1
    cn = 0
    for j in sw2:
        if j % 2 == 0:
            break
        cn += 1
    if cn == M:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
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()))
# print(*K, *S, *P)

ans = [0] * M
for i in range(M):
    total = 0
    for bit in range(2**len(S[i])):
        tmp = 0
        for j in range(len(S[i])):
            if (bit >> j) & 1 == 1:
                tmp += 1
        if tmp % 2 == P[i]:
            total += 1
    ans[i] += total
    if P[i] == 0:
        ans[i] -= 1
    
# print(ans)

answer = 1
for i in range(len(ans)):
    answer *= ans[i]
print(answer)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[[int(i) for i in input().split()] for i in range(m)]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    l=[False]*n
    for j in range(n):
        if(i>>j & 1):
            l[j]=True
    light=0
    for x,aa in enumerate(a):
        cnt=0
        for k in range(len(aa)):
            if k==0:
                continue
            if l[k-1]==True:
                cnt+=1
        if cnt%2==p[x]:
            light+=1
    if light==m:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

n, m = input().split()
n, m = int(n), int(m)
 
bulbs = []
 
for i in range(m):
    l = input().split()
    arr = [int(x) for x in l][1:]
    bulbs.append(arr)

needs = [int(x) for x in input().split()]
 
combos = 0

def test(lis):
  curr = 0
  for i in range(m):
    need = needs[i]
    for b in bulbs[i]:
      if lis[b-1] == 1:
        curr += 1
    if curr % 2 != need:
      return False
  return True
  
for i in itertools.product([0, 1], repeat=n):
  if test(list(i)):
    combos += 1

print(combos)

Submission status: Wrong Answer

Solution code:
import math

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

k_list = []
count_switch = [0] * n

for i in range(m):
  k = int(ks[i][0])
  k_list.append(k)
  for j in range(k):
  	count_switch[ks[i][j+1]-1] += 1

ans = 1
for k in k_list:
  ans *= math.pow(2, k-1)
  
for c in count_switch:
  if c > 1:
    ans /= math.pow(2, c-1)
  elif c == 0:
    ans *= 2
print(int(ans))

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools


def main():
    N,M = map(int,input().split())
    S={}
    P=[0] * (M+1)
    List=[]
    for i in range(1,M+1):
        array = list(map(int, input().split()))
        for s in range(1,len(array)):
            #print(s)
            if i in S.keys():
                S[i].append(array[s])
            else:
                S[i]=[]
                S[i].append(array[s])

    array = list(map(int, input().split()))
    for i in range(1,M+1):
        P[i]=array[i-1]

    for i in range(N):
        List.append(i+1)

    comb=[]
    count=0
    for i in range(1,N+1):
        for l in itertools.combinations(List,i):
            comb=l       
            flag=-1
            for j in range(1,M+1):
                
                cnt=0
                for k in range(0,len(comb)):
                    if comb[k] in S[j]:
                        cnt+=1
                if cnt%2==P[j]:
                    flag=1
                else:
                    flag=-1
                    break
            if flag==1:
                #print(comb)
                count+=1
    print(count)
                    
                               
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
li = [list(map(int,input().split())) for i in range(m)]
odd_even = list( map(int,input().split()))
counter = 0
for i in range(1,2**n):
    switches = ["off"] * n
    num1 = 0
    for j in range(n):
        if (i>>j)&1:
            switches[n-j-1] = "on"
    for i in range(m):
        # numは条件に当てはまる電球の点灯数
        num = 0
        for k in range(1,len(li[i])):
            if switches[li[i][k]-1] == "on":
                num += 1
        if num % 2 == odd_even[i]:
            num1 += 1
            continue
        else:
            break
    if num1 == m:
        counter += 1
print(counter)

Submission status: Wrong Answer

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

for i in range(2**n): # bitで全状態を列挙
    for j in range(m): # あるスイッチ状態における各電球のONOFFを探索する
        count = 0
        for k in range(n):
            if (i >> j) & 1 and (k+1) in l[j][1:]: 
                # j番目の電球にスイッチkがつながっていたらcountを追加
                count += 1
        if count % 2 != p[j]:
            break
        if j == m-1: ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,m = map(int,(input().split()))
bulb = [0]*m
p = [0]*m
j = 1
odd = 0
even = 0
for i in range(m):
    bulb[i] = list(map(int,input().split()))
p = list(map(int,input().split()))

for i in range(m):
    if not bulb[i][0]%2==p[i]:
        print(0)
        exit()
    elif bulb[i][0]%2==0:
        for j in range(0,bulb[i][0]+1,2):
            even = even + comb(bulb[i][0],j)

        if len(bulb[i])==2:
            even = even/2
            
    else:
        for j in range(1,bulb[i][0]+1,2):
            odd = odd + comb(bulb[i][0],j)

        if len(bulb[i])==2:
            odd = odd/2              
print(int(odd*even))

Submission status: Wrong Answer

Solution code:
def p_c():
    N, M = map(int, input().split())
    switch = [0] * N
    light = [0] * (1 << M)
    light[0] = 1
    for i in range(M):
        for s in list(map(int, input().split()))[1:]:
            switch[s - 1] += (1 << i)

    all_value = 0
    for i, p in enumerate(map(int, input().split())):
        all_value += p << (M - i - 1)

    for i in range(N):
        next_light = light.copy()
        for j in range(len(light)):
            next_light[j ^ switch[i]] += light[j]
        light = next_light

    print(light[all_value])

p_c()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
L=[]
for i in range(m):
    l=[]
    l=list(map(int,input().split()))
    s=0
    for j in range(l[0]):
        s+=2**(l[j+1]-1)
        L.append(s)
P=list(map(int,input().split()))
r=0
for i in range(1<<n):
	p=0
	for j in range(m):
		if bin(i&L[j]).count('1')%2==P[j]:
			p+=1
	if p==m:
		r+=1
print(r)

Submission status: Wrong Answer

Solution code:
#%%
import sys
def input():
    return sys.stdin.readline().rstrip()

def main():
    N, M = map(int, input().split())
    SW = [list(map(int, input().split()))[1:] for _ in range(M)]
    P = list(map(int, input().split()))

    num = 0
    for i in range(2**N+1):
        ng = False
        for j, sw in enumerate(SW):
            n = 0
            for k in sw:
                if i & 2**(k-1):
                    n = n + 1
            if n%2 != P[j]:
                ng = True
                break
        else:
            num = num + 1
    
    print(num)



# %%
if __name__ == '__main__':
    main()

# %%
# from atcoder_test import doTest
# doTest("abc128","c",main)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
D = [[] for i in range(N)]
for i in range(M):
    a = [int(j) for j in input().split()]
    for v in a[1:]:
        D[v - 1].append(i)

P = [int(i) for i in input().split()]
print(D)
ans = 0
for i in range(1 << N):
    S = [0] * M #各電球が何回スイッチ入ってるか
    for k in range(N):
        if ((i >> k) & 1) == 1:
            for d in D[k]:
                S[d] += 1

    if all([(s % 2) == p for  s,p in zip(S, P)]):
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ks_list = []
for i in range(M):
    ks = list(map(int, input().split()))
    ks_list.append(ks)
    
p = list(map(int, input().split()))
ans = 0

for x in range(2 ** N + 1):
#     print("===========", x, ans)
    for m in range(M):
        c = 0
        for k in range(1, ks_list[m][0]+1):
            ks_mk = -ks_list[m][k]
            if int(format(x,'b').zfill(10)[ks_mk]) == 1:
                c += 1
#             print(ks_list, ks_list[m][k], ks_mk, format(x,'b').zfill(10), format(x,'b').zfill(10)[ks_mk])
#         print(c, p[m])
        if c % 2 != p[m]:
#             print("break")
            break
        if m == M-1:
            ans += 1
#     print(ans, ks_list, c, p)

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from sys import stdin


def main():
    input = lambda: stdin.readline()
    N, M = map(int, input().split())
    KS = [list(map(int, input().split())) for _ in [0] * M]
    P = tuple(map(int, input().split()))

    sw = defaultdict(list)
    for i, ks in enumerate(KS, start=1):
        for s in ks[1:]:
            sw[s].append(i)

    light = [False] * (M + 1)
    ans = 0
    for mask in range(1 << N):
        li = light[:]
        for i in range(N):
            if mask & 1 << i:
                for j in sw[i+1]:
                    li[j] = (li[j] + 1) % 2
        if P == tuple(li[:0:-1]):
            ans += 1
    print(ans)


main()

Submission status: Wrong Answer

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

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

p = list(map(int, input().split()))
ans = 0
state = [i for i in itertools.product((0, 1), repeat=n)]

for case in state:
    sum = 0
    flag = True
    for i in range(m):  # 電球iにおいて
        for j in s[i]:
            sum += case[j-1]
        if sum % 2 != p[i]:
            flag = False
        if not flag:  # 電球消えてたら次のケースに移る
            break
    if flag:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

cnt = 0
for i in range(pow(2, n)):
    switch = [i>>j&1 for j in range(n)]
    light = 0
    for j in range(m):
        on = 0
        for k in range(s[j][0]):
            if switch[k-1]==1:
                on += 1
        if on%2 == p[j]:
            light += 1
    if light == m:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

cnt = 0
for i in range(pow(2, n)):
    switch = [i>>j&1 for j in range(n)]
    light = 0
    for j in range(m):
        on = 0
        for k in range(1, s[j][0]+1):
            if switch[k-1]==1:
                on += 1
        if on%2 == p[j]:
            light += 1
    if light == m:
        cnt += 1
print(cnt)

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()))
ans = 0
for i in range(2 ** N):  # all comb
    for j in range(M):  # k loop
        c = 0
        for k in range(M):  # s loop
            if ((i >> k) & 1) and (k + 1) in s[j][1:]:
                c += 1
        if c % 2 != p[j]:
            break
        elif j == M - 1:
            ans += 1
print(ans)