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:
def main():
    N, M = map(int,input().split())
    k = [None] * M
    s = [None] * M
    for i in range(M):
        k[i], *s[i] = map(int, input().split())
    p = list(map(int, input().split()))

    # スイッチのONOFFパターンをbit全探索
    ans = 0
    for i in range(1, 2**N):
        # ONOFFリスト取得
        switchs = [0] + [False for _ in range(N)]
        for j in range(1,N+1):
            if (i>>j-1) & 1:
                switchs[j] = True
        # 各電球が点灯しているか判定
        for si,pi in zip(s,p):
            # ONの個数
            on_count = sum([v for v in [switchs[sij] for sij in si] if v])
            # 消灯していた場合
            if on_count % 2 != pi:
                break
        else: # ひとつでも消灯があればスルー
            ans += 1
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

# print("n,m:",n,m)
# print("s:",s)
# print("p:",p)

def bitlist(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

ans = 0
for i in range(2**n):
    bitnow = bitlist(i,n)
    checker = 0
    flag = 0
    for j in range(m):
        for l in s[j]:
            if bitnow[l]==1:
                checker += 1
        if checker%2 != p[j]:
            flag = 1
    if flag == 0:
        ans += 1

print(ans)

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):
    s=[0]*n
    f=1
    for j in range(n):
        if (i>>j)&1:
            s[j]=1
    for j in range(m):
        c=0
        for k in range(1,1+l[j][0]):
            if s[k-1]:
                c+=1
        if c%2!=p[j]:
            f=0
            break
    if f:
        ans+=1
print(ans)

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

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
LST = []
for _ in range(m):
    lst = list(map(int, input().split()))
    lst = lst[1:]
    lst = map(lambda x: x - 1, lst)
    LST.append(list(lst))

p = list(map(int, input().split()))
cnt = 0
for i in range(1, 2 ** n):
    tmp_denkyuu = 0
    for j in range(m):
        tmp_bit = 0
        s_cs = LST[j]
        for s_c in s_cs:
            if (i >> (n - 1 - s_c)) & 1:
                tmp_bit += 1
        if tmp_bit % 2 == p[j]:
            tmp_denkyuu += 1
    if tmp_denkyuu == m:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

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

ans=0
for i in range(2**N):
    switch=[False]*N

    for j in range(N):
        if ((i>>j) & 1):
            switch[N-j-1]=True

    light=True
    for m in range(M):
        cnt=0
        for o in range(k[m][0]):
            if switch[k[m][o+1]-1]==True:
                cnt+=1

        if not (cnt%2==p[m] and cnt!=0):
            light=False

    if light==True:
        ans+=1
      
            
print(ans)

Submission status: Wrong Answer

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

ans=0
for i in range(2**N):
    switch=[False]*N

    for j in range(N):
        if ((i>>j) & 1):
            switch[N-j-1]=True

        light=True
        for m in range(M):
            cnt=0
            for o in range(k[m][0]):
                #cnt=0
                if switch[k[m][o+1]-1]==True:
                    cnt+=1

            if not (cnt%2==p[m] and cnt!=0):
                light=False

        if light==True:
            ans+=1
      
            
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,M=map(int,input().split())
k=[list(map(int,input().split())) for _ in range(M)]
p=list(map(int,input().split()))
#print(k)
#cnt=0
#ok=[[False]*N for _ in range(M)]
#print(ok)
ans=0
for i in range(2**N):
    switch=[False]*N
    #print(switch)
    #on=0
    #ans=0
    for j in range(N):
        if ((i>>j) & 1):
            switch[N-j-1]=True
    #print(switch)

        light=True
        for m in range(M):
            cnt=0
            for o in range(k[m][0]):
                #cnt=0
                if switch[k[m][o+1]-1]==True:
                    cnt+=1

            if not (cnt%2==p[m] and cnt!=0):
                light=False
        if light==True:
            ans+=1
      
            
print(ans)

#cf. https://www.planeta.tokyo/entry/3963/

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,M=map(int,input().split())
k=[list(map(int,input().split())) for _ in range(M)]
p=list(map(int,input().split()))
#print(k)
#cnt=0
#ok=[[False]*N for _ in range(M)]
#print(ok)
val=0
for i in range(2**N):
    switch=[False]*N
    #print(switch)
    #on=0
    for j in range(N):
        if ((i>>j) & 1):
            switch[N-j-1]=True
    #print(switch)

        ok=0
        for m in range(M):
            
            cnt=0
            for o in range(k[m][0]):
                #cnt=0
                if switch[k[m][o+1]-1]==True:
                    cnt+=1

            if not (cnt%2==p[m] and cnt!=0):
                break
            
            if cnt%2==p[m] and cnt!=0 and m==M-1:
                ok+=1
       
      
            
print(ok)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,M=map(int,input().split())
k=[list(map(int,input().split())) for _ in range(M)]
p=list(map(int,input().split()))
#print(k)
#cnt=0
#ok=[[False]*N for _ in range(M)]
#print(ok)
val=0
for i in range(2**N):
    switch=[False]*N
    #print(switch)
    #on=0
    for j in range(N):
        if ((i>>j) & 1):
            switch[N-j-1]=True

        
        for m in range(M):
            cnt=0
            for o in range(k[m][0]):
                #cnt=0
                if switch[k[m][o]-1]==True:
                    cnt+=1
            if cnt%2==p[m]:
                if m==M-1:
                    val+=1
            else:
                break
            
print(val)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()
s=[]
k=[]
for i in range(m):
    temp=limii()
    s0=temp[0]
    k0=temp[1:]
    s.append(s0)
    k.append(k0)

p=limii()
ans=0
#bit全探索
#print(p)
for i in product([0,1], repeat=n):
    #点灯している電球の数
    temp=0

    #全ての電球で探索
    for j in range(m):
        #対象の電球のonになっている個数
        cnt=0
        for x in range(s[j]):
            
            if i[x]==1:
                cnt+=1
            
        if cnt%2==p[j]:
            temp+=1
        #print(i,j,cnt)
    if temp==m:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()
s=[]
k=[]
for i in range(m):
    temp=limii()
    s0=temp[0]
    k0=temp[1:]
    s.append(s0)
    k.append(k0)

p=limii()
ans=0
#bit全探索
print(p)
for i in product([0,1], repeat=n):
    #点灯している電球の数
    temp=0

    #全ての電球で探索
    for j in range(m):
        #対象の電球のonになっている個数
        cnt=0
        for x in range(s[j]):
            
            if i[x]==1:
                cnt+=1
            
        if cnt%2==p[j]:
            temp+=1
        print(i,j,cnt)
    if temp==m:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()
s=[]
k=[]
for i in range(m):
    temp=limii()
    s0=temp[0]
    k0=temp[1:]
    s.append(s0)
    k.append(k0)

p=limii()
ans=0
#bit全探索
for i in product([0,1], repeat=n):
    #点灯している電球の数
    temp=0

    #全ての電球で探索
    for j in range(m):
        #対象の電球のonになっている個数
        cnt=0
        for x in range(s[j]):
            #print(i,j,x,i[x-1])
            if i[x]==1:
                cnt+=1
        if cnt%2==p[j]:
            temp+=1
    if temp==m:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()
s=[]
k=[]
for i in range(m):
    temp=limii()
    s0=temp[0]
    k0=temp[1:]
    s.append(s0)
    k.append(k0)

p=limii()
ans=0
#bit全探索
for i in product([0,1], repeat=n):
    #点灯している電球の数
    temp=0

    #全ての電球で探索
    for j in range(m):
        #対象の電球のonになっている個数
        cnt=0
        for x in range(s[j]):
            #print(i,j,x,i[x-1])
            if i[x-1]==1:
                cnt+=1
        if cnt%2==p[j]:
            temp+=1
    if temp==m:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
bulbs = []
for _ in range(M):
    bulbs.append(list(map(int, input().split()))[1:])
P = list(map(int, input().split()))

# print('bulbs', bulbs)
# print('P', P)


def f(state):
    for bulb, p in zip(bulbs, P):
        if state[[bulb]].sum() % 2 != p:
            return 0
    return 1


ans = 0
for i in range(N**2):
    state = format(i, 'b').zfill(N)
    state = np.array(list(map(int, ['9'] + list(state))))
    # if f(state) == 1:
    # print(state)
    ans += f(state)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
bulbs = []
for _ in range(M):
    bulbs.append(list(map(int, input().split()))[1:])
P = list(map(int, input().split()))

print('bulbs', bulbs)
print('P', P)


def f(state):
    for bulb, p in zip(bulbs, P):
        if state[[bulb]].sum() % 2 != p:
            return 0
    return 1


ans = 0
for i in range(N**2):
    state = format(i, 'b').zfill(N)
    state = np.array(list(map(int, ['9'] + list(state))))
    if f(state) == 1:
        print(state)
    ans += f(state)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import deque
import itertools
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()
ans = 0
N, M = map(int, input().split())
ks = [tuple(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
t = []
for i in range(N):
    tt = list(itertools.combinations(range(1, N+1), i+1))
    for l in tt:
        t.append(l)
for i in range(len(t)):
    pp = 0
    for l in range(M):
        if len(set(ks[l][1:]) & set(t[i])) % 2 == p[l]:
            pp += 1
    if pp == M:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

sw = [i + 1 for i in range(n)]

t_on = []
for i in range(2 ** n):
    on = []
    for j in range(n):
        if (i>>j) & 1:
            on.append(sw[j])

    t_on.append(on)

ans = 0
for i in range(len(t_on)):
    for j in range(m):
        c = set(t_on[i]) & set(ks[j][1:])
        print(ks[j][1:], t_on[i], c, len(c), p[j])
        if len(c) % 2 != p[j]: break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

sw = [i + 1 for i in range(n)]

t_on = []
for i in range(2 ** n):
    on = []
    for j in range(n):
        if (i>>j) & 1:
            on.append(sw[j])

    t_on.append(on)

ans = 0
for i in range(1, len(t_on)):
    for j in range(m):
        c = set(t_on[i]) & set(ks[j][1:])
        # print(ks[j][1:], t_on[i], c, len(c), p[j])
        if len(c) % 2 != p[j]: break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

for i in range(2**N):
    ii =str(bin(i))[2:].zfill(N)
    Judge = 1
    cnt = 0
    
    for k in range(M):
        for j in range(1,K[k][0]+1):
            cnt += int(ii[K[k][j]-1])                
        if cnt % 2 != P[k]:
            Judge = 0
            break
    if Judge :
        Ans += 1

print(Ans)

Submission status: Wrong Answer

Solution code:
def main():
  import itertools
  n,m=map(int,input().split())
  li=[list(map(int,input().split())) for _ in range(m)]
  p=list(map(int,input().split()))
  li=[set(x[1:]) for x in li]
  
  ans=0
  g=range(1,n+1)
  
  for i in g:
    for s in itertools.combinations(g,i):
      s=set(s)
      for i,t in enumerate(li):
        u=s&t
        if len(u)%2==p[i]:
          continue
        else:
          break
      else:
        ans+=1
   
  print(ans)
  
  
if __name__=="__main__":
  main()

Submission status: Wrong Answer

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


pattern = []
for i in range(2**n):
    pattern.append(list(bin(i)[2:].zfill(n)))

ans = 0

for i in pattern:
    turn = []
    count = 0
    on = 0
    for j in range(n):
        if i[j] == '1':
            turn.append(switch[j])
    for k in range(m):
        for l in range(1,ls[k][0]+1):
            if ls[k][l] in turn:
                count += 1
        if count % 2 == p[k]:
            on += 1
    if on == m:
        ans += 1
            
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ls = []
switch = []
for i in range(m):
    ks = list(map(int,input().split()))
    ls.append(ks)
    for j in range(1,ks[0]+1):
        if not ks[j] in switch:
            switch.append(ks[j])
p = list(map(int,input().split()))

#print(switch)
pattern = []
for i in range(2**len(switch)):
    pattern.append(list(bin(i)[2:].zfill(len(switch))))
#print((pattern))
ans = 0

for i in pattern:
    turn = []
    on = 0
    for j in range(len(switch)):
        if i[j] == '1':
            turn.append(switch[j])
    #print(turn)
    for k in range(m):
        count = 0
        for l in range(1,ls[k][0]+1):
            if ls[k][l] in turn:
                count += 1
        if count % 2 == p[k]:
            on += 1
    if on == m:
        #print(turn)
        ans += 1
            
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ls = []
switch = []
for i in range(m):
    ks = list(map(int,input().split()))
    ls.append(ks)
    for j in range(1,ks[0]+1):
        if not ks[j] in switch:
            switch.append(ks[j])
p = list(map(int,input().split()))

#print(switch)
pattern = []
for i in range(2**len(switch)):
    pattern.append(list(bin(i)[2:].zfill(len(switch))))
#print(pattern)
ans = 0

for i in pattern:
    turn = []
    count = 0
    on = 0
    for j in range(len(switch)):
        if i[j] == '1':
            turn.append(switch[j])
    #print(turn)
    for k in range(m):
        for l in range(1,ls[k][0]+1):
            if ls[k][l] in turn:
                count += 1
        if count % 2 == p[k]:
            on += 1
    if on == m:
        ans += 1
            
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N,M=map(int,input().split())
    s=[[] for i in range(0,M)]
    for i in range(0,M):
        s[i]+=list(map(int,input().split()))
    p=list(map(int,input().split()))
    ans=0
    for i in range(0,2**N):
        x=0
        flag=0
        for j in range(0,M):
            for k in range(1,s[j][0]+1):
                x+=(i >> (s[j][k]-1) & 1)
            if x%2!=p[j]:
                flag=1
        if flag==0:
            ans=ans+1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def bits2tuple(n):
    ret = []
    i = 0
    while (1 << i) <= n:
        if n & (1 << i) != 0:
            ret.append(i)
        i += 1
    return tuple(ret)


def main():
    N, M = map(int, input().split())

    kM = []
    skM = []
    for _ in range(M):
        sk = list(map(int, input().split()))
        k = sk.pop(0)

        kM.append(k)
        skM.append(sk)

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

    ans = 0
    for bits in range(1, 1 << N):
        on_switch = list(map(lambda x: x + 1, bits2tuple(bits)))

        all_on = True
        for p, k, sk in zip(pM, kM, skM):
            if 0 < len(set(on_switch) & set(sk)) and len(set(on_switch) & set(sk)) % 2 != p:
                all_on = False
                break

        if all_on:
            ans += 1

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
# This source is wrong answer


def bits2tuple(n):
    ret = []
    i = 0
    while (1 << i) <= n:
        if n & (1 << i) != 0:
            ret.append(i)
        i += 1
    return tuple(ret)


def main():
    N, M = map(int, input().split())

    kM = []
    skM = []
    for _ in range(M):
        sk = list(map(int, input().split()))
        k = sk.pop(0)

        kM.append(k)
        skM.append(sk)

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

    ans = 0
    for bits in range(1, 1 << N):
        on_switch = list(map(lambda x: x + 1, bits2tuple(bits)))

        all_on = True
        for p, k, sk in zip(pM, kM, skM):
            if len(set(on_switch) & set(sk)) % 2 != p:
                all_on = False
                break

        if all_on:
            ans += 1

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
def bits2tuple(n):
    ret = []
    i = 0
    while (1 << i) <= n:
        if n & (1 << i) != 0:
            ret.append(i)
        i += 1
    return tuple(ret)


def main():
    N, M = map(int, input().split())

    kM = []
    skM = []
    for _ in range(M):
        sk = list(map(int, input().split()))
        k = sk.pop(0)

        kM.append(k)
        skM.append(sk)

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

    k_on_s_ans = None
    for p, k, sk in zip(pM, kM, skM):
        k_on_s = []
        # for i in range(0 + p, k + 1, 2):
        #     k_on_s += itertools.combinations(sk, i)
        for i in range(1, 1 << N):
            i_bits = list(map(lambda x: x + 1, bits2tuple(i)))

            if len(set(sk) & set(i_bits)) % 2 == p:
                k_on_s.append(i_bits)

        if k_on_s_ans is not None:
            k_on_s_ans = [k_on for k_on in k_on_s if k_on in k_on_s_ans]
        else:
            k_on_s_ans = k_on_s

    print(len(k_on_s_ans))


main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s = []
k = []
for i in range(m):
    s_in = list(map(int,input().split()))
    s.append(s_in[1:])
    k.append(s_in[0])
p = list(map(int,input().split()))
ans = 0
def bfs(switch):
    global ans
    if len(switch)==n:
        ok = 1 #全部の電球がつく
        for i in range(m):
            on_cnt=0
            for j in range(k[i]):
                if switch[j-1]==1:
                    on_cnt+=1
            if on_cnt%2!=p[i]:
                ok = 0
        if ok:
            ans+=1
    else:
        bfs(switch+[0])
        bfs(switch+[1])
bfs([])
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
switch = [0]*N
for m in range(M):
    ss = list(map(int, input().split()))[1:]
    for s in ss:
        switch[s-1] |= 2**m
li = 0
for index,p in enumerate(list(map(int, input().split()))):
    if p==1: li = 2**index
answer = 0
for n in range(2**N):
    l = 0
    for s in range(N):
        if (n>>s)&1: l^=switch[s]
    if p==l: answer+=1
print(answer)

Submission status: Wrong Answer

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

for i in range(1 << n):
   for r in range(m):
      on_sum = 0
      for j in range(n):
         if i >> j & 1 and j in lamps[r]:
            on_sum += 1
      if (on_sum % 2 != p[r]):
         break
   else:
      ans += 1

print()
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
lights=[]
for i in range(M):
    k,*s=map(int,input().split())
    lights.append(list(map(lambda x:x-1,s)))
P=list(map(int,input().split()))
cnt=0
for b in range(1<<N):#bit
    flg=True
    for m in range(M):#各bitごとに各電球を調べる
        on_cnt=0
        for switch in lights[m]:#つながってるスイッチ番号
            if (b>>switch)&2:
                on_cnt+=1
        if on_cnt==0 or on_cnt%2 != P[m]:
            flg=False
    if flg:
       cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
lights=[]
for i in range(M):
    k,*s=map(int,input().split())
    lights.append(list(map(lambda x:x-1,s)))
P=list(map(int,input().split()))
cnt=0
for b in range(1<<N):#bit
    on_cnt=0
    flg=True
    for m in range(M):#各bitごとに各電球を調べる
        for switch in lights[m]:#つながってるスイッチ番号
            if (b>>switch)&1:
                on_cnt+=1
        if on_cnt==0 or on_cnt%2 != P[m]:
            flg=False
    if flg:
       cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
lights=[]
for i in range(M):
    k,*s=map(int,input().split())
    lights.append(list(map(lambda x:x-1,s)))
P=list(map(int,input().split()))
cnt=0
for i in range(1<<N):#bit
    on_cnt=0
    flg=True
    for j in range(M):#各bitごとに各電球を調べる
        for switch in lights[j]:#つながってるスイッチ番号
            if (i>>switch)&1:
                on_cnt+=1
        if on_cnt%2 != P[j]:
            flg=False
    if flg:
       cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
k = []

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

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

cnt = 0
ans = 0
for i in range(2 ** n):
    lis = [False] * n

    for j in range(n):
        if (i >> j) & 1:
            lis[j] = True
    print(lis)
    cnt = 0
    for j in range(m):
        val = 0
        for l in range(len(k[j])):
            if lis[k[j][l]-1] == True:
                val += 1
            #print(lis[k[j][l]-1])
        if val % 2 == p[j]:
            cnt += 1
        #print(val)
        #print(cnt)
    if cnt == m:
        ans += 1
    #print(ans)



print(ans)

Submission status: Wrong Answer

Solution code:
k = []

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

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

cnt = 0
ans = 0
for i in range(2 ** n):
    lis = [False] * n

    for j in range(n):
        if (i >> j) & 1:
            lis[j] = True
    #print(lis)
    cnt = 0
    for j in range(m):
        val = 0
        for l in range(len(k[j])):
            if lis[k[j][l]-1] == True:
                val += 1
            #print(lis[k[j][l]-1])
        if val % 2 == p[j]:
            cnt += 1
    if cnt == m:
        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(int,input().split()))
n2 = [0]*n
ans = 0
for _ in range(2**n):
    check = 0
    on = 0
    #電球チェック
    for i in range(m):
        for k in range(s[i][0]):
            if n2[s[i][k+1]-1] == 1:
                check += 1
        if check%2 == p[i]:
                on += 1
    if on == m:
            ans +=1
    #他の組み合わせ
    for j in range(n):
        if n2[j] == 0:
            n2[j] = 1
            break
        else:
            n2[j] = 0
            continue
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
n,m = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
n2 = [0]*n
cnt = 0
on = 0
ans = 0
for _ in range(2**n):
    check = 0
    on = 0
    #電球チェック
    for i in range(m):
        for k in range(s[i][0]):
            if n2[s[i][k+1]-1] == 1:
                check += 1
        else:
            if check%2 == p[i]:
                on += 1
    else:
        if on == m:
            ans +=1
    #他の組み合わせ
    for j in range(n):
        if n2[j] == 0:
            n2[j] = 1
            cnt +=1
            break
        else:
            n2[j] = 0
            cnt -=1
            continue
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

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

ans = 2 ** n
for prod in (product([0, 1], repeat=n)):
    tmp = 0
    for i in range(m):
        for j in s[i]:
            tmp += prod[j - 1]
        if (tmp % 2 != p[i]):
            ans -= 1
            break
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]:
            a = 0
            break
    if a:
        ans += 1
print(ans)