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())
target = [[num-1 for num in list(map(int,input().split()))[1:]] for _ in range(M)]
#各sについてのリストを元にした配列を、それぞれの値から1を引いて作成
judge = list(map(int,input().split()))
#2で割った余り=最終判定のリスト
cnt = 0

for i in range(2 ** N):
#スイッチの状態について全探索
#N = 2の時、スイッチは[00,01,10,11]の4 = 2^N通り
	switches = [0] * M
	for k in range(M):
	#各電球についてfor文を回す
		for j in range(N):
		#各スイッチについてfor文を回す
			if ((i >> j) & 1) and j in target[k]:
			#jビット右シフト(ex:6 = 0b110 >> 1 → 0b11 = 3)かつ、1と論理積をとる
			#⇨下位1ケタのビットが立っているか = j番目スイッチが押されているかどうかに対応を判定
			#j番目のスイッチが押されており、かつj番目のスイッチが電球Kの点灯条件であれば
			#+1カウント
				switches[k] += 1

	switches =	[switch % 2 for switch in switches]
	print(switches)
	#2で割ったあまりを算出し、点灯するかどうかのリストに
	if switches == judge:
		cnt += 1
		
print(cnt)

Submission status: Wrong Answer

Solution code:
import itertools
ans = 0
n,m = map(int, input().split())
s_list = []
s_count_list = []
for _ in range(m):
    s = list(map(int,input().split()))
    s_count_list.append(s[0])
    s_list.append(s[1:])
oe = list(map(int,input().split()))   
seq = list(range(1, n+1))
for i in range(1, n+1):
    cmb = list(itertools.combinations(seq,i))
    for j in range(len(cmb)):
        ansv = []
        for k in range(m):
            ss = []
            for l in range(s_count_list[k]):
                if s_list[k][l] in list(cmb[j]):
                    ss.append(s_list[k][l])
            if len(ss)%2 == oe[k]:
                ansv.append(True)
            else:
                ansv.append(False)
        if all(ansv):
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations


N, M = [int(n) for n in sys.stdin.readline().strip().split()]

ks = []
ss = []
ss_all = []
for i in range(M):
  tmp = [int(n) for n in sys.stdin.readline().strip().split()]
  ks.append(tmp[0])
  ss.append(tmp[1:])
  ss_all += tmp[1:]
  
ps = [int(n) for n in sys.stdin.readline().strip().split()]

ss_set = set(ss_all)

cnt = 0
for i in range(len(ss_set)):
  for comb in combinations(ss_set, i+1):
    flag = True
    for i_ramp, s in enumerate(ss):
      if not sum([1 for se in s if se in comb])%2==ps[i_ramp]:
        flag = False
        break
    if flag:
      cnt += 1

cnt *= 2**(N - len(ss_set))
print(cnt)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import combinations_with_replacement

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]
p = list(map(int,stdin.readline().rstrip().split()))

hai = [0,1]
hai = list(combinations_with_replacement(hai, n))
point = 0

for i in range(len(hai)):
    h = list(hai[i])
    kai = 0
    for j in range(m):
        gou = 0
        for k in range(1,len(li[j])):
            if h[li[j][k]-1] == 1:
                gou += 1
        if p[j] != gou%2:
            kai += 1
    if kai == 0:
        point += 1
print(point)

Submission status: Wrong Answer

Solution code:
from sys import stdin


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    X = [sum(1 << int(j) - 1 for j in i.split()[1:]) for i in lines[1:-1]]
    Z = lines[-1].split()
    ans = 0
    for i in range(1, 1 << N):
        tmp = 0
        for x, y in zip(X, Z):
            if bin(i & x).count("1") % 2 == int(y):
                tmp += 1
        if tmp == M:
            ans += 1
    print(ans)

    return


main()

Submission status: Wrong Answer

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

n,m=map(int,input().split())
s=[list(map(int,input().split()))for i in range(m)]
"""
for i in range(m):
    s=list(map(int, input().split()))
"""
p=list(map(int, input().split()))
q=[0]*11


ans=0
while(True):
    for i in range(n):
        if(q[i]==2):
            q[i+1]+=1
            q[i]=0
    if(q[n]==1):
        break
    
    flag=1
    for i in range(m):
        tmp=0
        for j in s[i]:
            tmp+=q[j-1]
        if(tmp%2!=p[i]):
            flag=0
            break
    if(flag==1):
        ans+=1
    q[0]+=1

print(ans)

Submission status: Wrong Answer

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

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

n=0
m=0
q=[0]*10
p=[0]*10
s=[0]*10


ans=0
while(True):
    for i in range(n+1):
        if(q[i]==2):
            q[i+1]+=1
            q[i]=0
    if(q[n]==1):
        break
    
    flag=1
    for i in range(m):
        tmp=0
        for j in s[i]:
            tmp+=q[j-1]
        if(tmp%2!=p[i]):
            flag=0
            break
    if(flag==1):
        ans+=1
    q[0]+=1

print(ans)

Submission status: Wrong Answer

Solution code:

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

n=0
m=0
q=[0]*10
p=[0]*10
s=[0]*10


ans=0
while(True):
    for i in range(n+1):
        if(q[i]==2):
            q[i+1]+=1
            q[i]=0
    if(q[n]==1):
        break
    
    flag=1
    for i in range(m):
        tmp=0
        for j in s[i]:
            tmp+=q[j-1]
        if(tmp%2!=p[i]):
            flag=0
            break
    if(flag==1):
        ans+=1
    q[0]+=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()))

ans = 0

for i in range(2**N):
    switch = [0]*N
    
    for j in range(N):
        if (i>>j & 1):
            switch[j] = 1
    
    n_on_light = 0
    
    for x in range(M):
        n_on_switch_for_one_light = 0
        for k in range(ks[x][0]):
            n_on_switch_for_one_light += switch[ks[x][k+1]-1]
        if n_on_switch_for_one_light%2 == p[x]:
            n_on_light += 1
    
    if n_on_light == M:
        print(switch)
        ans += 1
    
print(ans)

Submission status: Wrong Answer

Solution code:
N , M = map(int , input().split())
switch = []
bit_switch = []
for _ in range(M):
    switch = list(map(int ,input().split()))
    del switch[0]
    k = 0
    for i in switch:
        k += 1 << (i - 1)
    bit_switch.append(k)
p = list(map(int,input().split()))
cnt = 0
dp = [[] for _ in range(M + 1)]
dp[0] = [i for i in range(2 ** N)]
print(bit_switch)
print(dp)
for i in range(M):
    for j in dp[i]:
        if str(bin(j & bit_switch[i])).count('1')% 2 == p[i]:
            dp[i + 1].append(j)
print(dp)
print(len(dp[M]))

Submission status: Wrong Answer

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    s = [[int(i) for i in input()[2:].split()] for j in range(M)]
    p = [int(i) for i in input().split()]
    ans = 0
    for bit in range(1<<N):
        switches = [0] * N
        for i in range(N):
            if bit & (1<<i):
                switches[i] = 1
        for ss,pp in zip(s,p):
            tmp = 0
            for i in ss:
                if switches[i-1]:
                    tmp += 1
            if tmp%2 != pp:
                break
        else:
            print(switches)
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,M = map(int, input().split())
    RAMPS = [0]*M
    for i in range(M):
        tmp = list(map(int, input().split()))
        RAMPS[i] = [x-1 for x in tmp[1:]]
    PS = list(map(int, input().split()))
    ans = 0
    for bit in range(2**N+1):
        for i in range(M):
            cnt = 0
            for j in RAMPS[i]:
                if 1<<j & bit != 0: cnt += 1
            if cnt%2 != PS[i]:
                break
        else:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import product
N,M=map(int,input().split())
A=[]
for _ in range(M):
    A.append(list(map(int,input().split()))[1:])
P=list(map(int,input().split()))

ans=0

for st in product([0,1],repeat=N):
    f=True
    for i in range(M):
        k=0
        for j in A[i]:
            k+=st[j-1]
        f= k//2==P[i]
        if not f:
            break
    if f:
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import product

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

bulb = {}
for i in range(1, m+1):
    k_s = list(map(int, input().split()))
    bulb[i] = k_s[1:]

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

count = 0
for item in product([0, 1], repeat=n):
    on = [ind+1 for ind, status in enumerate(item) if status == 1]
    for k, v in bulb.items():
        if p[i-1] != len(set(v).intersection(set(on))) % 2:
            break
    else:
        count += 1

print(count)

Submission status: Wrong Answer

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

ans = 0
for i in range(1<<N):#すいっちのくみあわせ
  for j in range(M):#でんきゅうをみてく
    rel=0
    for k in swis[j]:
      if i & (1<<(k-1)) != 0:
        rel+=1
        
      if rel%2 != need[j]:
        break
  else:
     ans+=1
      
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(1<<N):#すいっちのくみあわせ
  for j in range(M):#でんきゅうをみてく
    rel=0
    for k in swis[j]:
      if i & 1<<(k-1) != 0:
        rel+=1
        
      if rel%2 != need[j]:
        break
  else:
     ans+=1
      
print(ans)

Submission status: Wrong Answer

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

L=[0 for i in range(2**N)]
#print(L)

for i in range(2**N):
  cnt=0
  for j in range(M):
    for k in K[j]:
      if (i>>(k-1))&1==1:
        cnt+=1
    if cnt%2==p[j]:
      L[i]+=1
#print(L)

ans=0
for i in L:
  if i==M:
    ans+=1
print(ans)

Submission status: Wrong Answer

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

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

p=list(map(int,input().split()))
#以上入力

def binary_ume(N,K):  #Nを2進数表示し、K桁まで0埋めする
    A = []
    while N >= 2:
        A.append(N%2)
        N = N//2
    A.append(N)
    while len(A) < K:
        A.append(0)
    return A

ans = 0
print(k,p)

for i in range(m):
    for j in range(1,len(k[i])):
        k[i][j] -= 1

for i in range(2**n):
    switch = binary_ume(i,n)  #スイッチの推し方全部見る
    all_on = 1  #何かひとつでもダメならすぐ切る
    for j in range(m):
        if sum(switch[l] for l in k[j][1:])%2 != p[j]:
            all_on = 0
            break
    if all_on == 1:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,M=map(int,input().split())
l=[]*M

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

count=0
s=[-1]*10

for i in range(2):
    s[0]=i
    for ii in range(2):
        s[1]=ii
        for iii in range(2):
            s[2]=iii
            for iiii in range(2):
                s[3]=iiii
                for iiiii in range(2):
                    s[4]=iiiii
                    for iiiiii in range(2):
                        s[5]=iiiiii
                        for iiiiiii in range(2):
                            s[6]=iiiiiii
                            for iiiiiiii in range(2):
                                s[7]=iiiiiiii
                                for iiiiiiiii in range(2):
                                    s[8]=iiiiiiiii
                                    for iiiiiiiiii in range(2):
                                        s[9]=iiiiiiiiii
                                        #いかれてる
                                        for j in range(M):
                                            sum=0
                                            is_success=True
                                            for item in l[j]:
                                                sum=sum^s[item-1]
                                            if sum!=p[j]:
                                                is_success=False
                                                break
                                        if is_success:
                                            count+=1
                                            
print(count/2**(10-N))

Submission status: Wrong Answer

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

ans=0
for i in range(2**n):
  tmp=0
  f=1
  for mm in range(m):
    for j in info[mm][1:]:
      tmp+=int(str(format(i,'b').zfill(n))[int(j)-1])
    if tmp%2!=p[mm]:
      f=0
  if f==1:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
def f_c():
    n, m = map(int, input().split())
    l = []
    for _ in range(m):
        _, *s = map(lambda x: int(x)-1, input().split())
        sb = 0
        for si in s:
            sb |= 1<<si
        l.append(sb)
    *p, = map(int, input().split())

    a, c = 0, 0
    for i in range(1, 1<<n):
        for j, sb in enumerate(l):
            if bin(i&sb).count("1")%2!=p[j]:
                break
            else:
                c += 1
        a = a+1 if c==m else a
        c = 0
    print(a)

if __name__ == "__main__":
    f_c()

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
k=[]
for j in range(0,M):
    k.append([int(x) for x in input().split()])
    k[j]=k[j][1:]
p=[int(x) for x in input().split()]
condition=[0]*M
sum_=0
for u in range(0,2**N):
    switch=list(bin(u)[2:].zfill(N))
    for i in range(0,M):
        for j in k[i]:
            condition[i] += int(switch[j-1])
        condition[i] = condition[i] % 2
    #print(switch,condition)
    sum_ += (condition==p)
print(sum_)

Submission status: Wrong Answer

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

X = np.zeros((M,N))
for m in range(M):
  tmp = list(map(int,input().split()))
  for n in tmp[1:]:
    X[m-1,n-1] = 1
p = list(map(int,input().split()))

cnt = 0
for pattern in itertools.product([0,1], repeat=N):
  a = np.sum(X[:,np.array(pattern)==1],axis=1)
  if p == (a%2).tolist():
    cnt += 1
print(cnt)

Submission status: Wrong Answer

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

prod = list(itertools.product([0,1], repeat = N))
cnt = 0
for i in range(len(prod)):
  judge = True
  if sum(prod[i]) == 0:
    judge = False
  for j in range(M):
    temp = 0
    for k in range(K[j][0]):
      if prod[i][K[j][k+1]-1] == 1:
        temp += 1
    if temp % 2 != P[j]:
      judge = False
  if judge == True:
    cnt += 1

print(cnt)

Submission status: Wrong Answer

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

ans = 0
for patterns in range(2**n):
    ptn = bin(patterns)[2:].rjust(n, '0')
    # print(ptn)
    for i in range(m):
        num = 0
        for j in range(len(k[i])):
            num += int(ptn[k[i][j] - 1])
        if (p[i] == 0 and (num+p[i]) % 2 == 1) or (p[i] == 1 and (num+p[i]) % 2 == 0):
            break
        ans += 1
print(2**n - ans)

Submission status: Wrong Answer

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

		if cnt%2 != p[j]:
			flag = False
			
	if flag: res += 1
print(res)

Submission status: Wrong Answer

Solution code:
from itertools import product

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


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

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

print(res)

Submission status: Wrong Answer

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



if __name__ == '__main__':
    slove()

Submission status: Wrong Answer

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


if __name__ == '__main__':
    slove()

Submission status: Wrong Answer

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

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

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

ans = 0

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

Submission status: Wrong Answer

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

#create 0/1 matrix for all lamps and switches 
s=np.zeros((M,N))
for i in range(M):
    ks = list(map(int, input().split()))  
    for j in range(ks[0]):
        s[i, ks[j+1]-1]=1
P = list(map(int, input().split()))      
    
#remove any swith not connected to any lamp
s_sum_index = np.sum(s, axis=0) != 0
s1 = s[:,s_sum_index]

#print(s1)
counter=0
# 2^N possible combinations of switches
for k in range(2**s1.shape[1]):
    k_bit = list(map(int, list(np.binary_repr(k, s1.shape[1]))))
    #calculate how many switches are on for each lamp
    b_status = np.dot(s1, k_bit)%2
    #print(k_bit, b_status)
    if all(b_status==P)==True:
        counter +=1

print(counter)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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

class LightBulb:
    def __init__(self, k, switches):
        self.k = k
        self.switches = switches

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
Switch = [0] * N
for i in range(M):
  k,*S = map(int,input().split())
  for s in S:
    s -= 1
    Switch[s] |= (1 <<i)
#print(Switch)
P = list(map(int,input().split()))
p = 0
for i in range(len(P)):
  p |= (P[i] <<i)
#print(p)

ans = 0
for i in range(2 ** N):
  light = 0
  for j in range(M):
    if (i >>j) & 1 == 1:
      light ^= Switch[j]
  if light == p:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

for i in range(2**n):
  i_2 = str(bin(i))[2:]
  i_bit = i_2.zfill(n)
  print(i_bit)

Submission status: Wrong Answer

Solution code:
import itertools

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

sw = [[] for _ in range(M)]
for i in range(M):
    sw[i] = list(map(int,input().split()))

P = list(map(int,input().split()))
ans = 0
for tpl in itertools.product([0,1], repeat=N):
    bl = True
    for i in range(M):
        s = sum([tpl[j-1] for j in sw[i]])
        if (s-P[i])%2 == 1:
            bl = False
            break
    if bl:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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

class LightBulb:
    def __init__(self, k, switches):
        self.k = k
        self.switches = switches

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from itertools import combinations as combi
N, M = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
def check(s):
  for i in range(M):
    temp = 0
    for j in range(1, S[i][0] + 1):
      if S[i][j] in s:
        temp += 1
    if temp % 2 != p[i]:
      return False
  return True
res = 0
for i in range(1, N + 1):
  for com in combi(range(1, N + 1), i):
    if check(set(com)) == True:
      res += 1
print(res)

Submission status: Wrong Answer

Solution code:
n, m = (int(i) for i in raw_input().split())
switches = []
for i in range(m):
    line = [int(i) for i in raw_input().split()]
    switches.append(line[1:]) 
ps = [int(i) for i in raw_input().split()]
ans = 0
for i in range(2 ** n):
    pattern = []
    for d in range(n):
        if (1 << d) & i:
            pattern.append(True)
        else:
            pattern.append(False)

    ok = True
    print pattern
    for j in range(m):
        count = 0
        for k in switches[j]:
            if pattern[k-1]:
                count += 1
        ok = ok and (count % 2 == ps[j])
    if ok:
        ans += 1
print ans

Submission status: Wrong Answer

Solution code:
n, m = (int(i) for i in raw_input().split())
switches = []
for i in range(m):
    line = [int(i) for i in raw_input().split()]
    switches.append(line[1:])

ps = [int(i) for i in raw_input().split()]

ans = 0
for i in range(2 ** n):
    pattern = []
    for d in range(n):
        if (1 << d) & i:
            pattern.append(True)
        else:
            pattern.append(False)

    ok = True
    for j in range(m):
        count = 0
        for p in pattern[switches[j][0]-1:switches[j][-1]]:
            if p:
                count += 1
        ok = ok and (count % 2 == ps[j])
    if ok:
        ans += 1
print ans

Submission status: Wrong Answer

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

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


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