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

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

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


result = 0


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


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

        flag = 1

        for j in range(len(k)):

            tmp_sum = 0


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

            equal_p = tmp_sum % 2

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

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

        if  flag == 0:
            continue

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



    print(result)

Submission status: Wrong Answer

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

all_list = []
for i in range(2**N):
    all_list.append([])
    num_str = bin(i)[2:]
    if len(num_str) < N:
        for j in range(N - len(num_str)):
            all_list[i].append(0)
    for k in range(len(num_str)):
        all_list[i].append(int(bin(i)[2:][k]))


ans_num = 0
a = 0
for ans in all_list:#答えのこうほ
    flag = True

    for i, ks in enumerate(ks_list):# 条件
        middle_ans = 0
        for j in range(0,len(ks)):
            
            middle_ans += ans[ks[j]-1]
        
        if middle_ans % 2 == p_list[i]:
            a += 1
        else:
            flag = False
        
    if flag == True:
        ans_num += 1
print(ans_num)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

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

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

ans = 0
for i in range(1,N+1) :
    B = [z for z in range(1,i+1)]
    A = list(combinations(B,i))
    
    for a in A :
        
        for j in range(M) :
            cnt = 0
            for l in L[j][1:] :
                if l in a :
                    cnt += 1
            if (cnt%2) != P[j] :
                break
        else :
            ans += 1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, M = [int(s) for s in input().split()]
light = []
for i in range(M):
  tmp = [int(s) for s in input().split()]
  light.append([1 if j+1 in tmp[1:] else 0 for j in range(N)])
Plist = [int(s) for s in input().split()]
count = 0
for i in range(2**N):
  num = list(bin(i))
  switch = [num[-(j+1)] for j in range(len(num)-2)]
  if len(switch) < N:
    switch.extend(['0' for j in range(N-len(switch))])
  switch = [int(s) for s in switch]
  on = [0 for j in range(M)]
  for j in range(M):
    answer = [light[j][k]*switch[k] for k in range(N)]
    if sum(answer)//2 == Plist[j]  and sum(answer) > 0:
      on[j] = 1
  if sum(on) == len(on):
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from itertools import combinations, chain

n, m = list(map(int, input().split()))
ks = [list(map(int, input().split()))[1:] for i in range(m)]
ps = list(map(int, input().split()))

maxk = max(chain.from_iterable(ks))
cases = [format(i, '0{}b'.format(maxk)) for i in range(2 ** maxk)]


def count1(k, case):
    return len(list(filter(lambda s: s == '1', map(lambda i: case[i-1], k))))


if __name__ == '__main__':
    ans = []
    for case in cases:
        b = []
        for i, k in enumerate(ks):
            cnt = count1(k, case)
            if cnt % 2 == ps[i]:
                #print(case, k)
                b.append(True)
            else:
                b.append(False)
        # print(b)
        if all(b):
            ans.append(1)

    # print(ans)
    print(len(ans))

Submission status: Wrong Answer

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

N, M = map(int, input().split())
L = [list(map(int, input().split()))[1:] for m in range(M)]
p = list(map(int, input().split()))

S = [[] for i in range(N)]
for i, l in enumerate(L):
    for _l in l:
        S[_l-1].append(i)

results = []
for i in list(itertools.chain.from_iterable([list(itertools.combinations(range(N), i+1)) for i in range(N)])):
    l = [0] * M
    for j in i:
        for k in S[j]:
            l[k] += 1
    results.append(list(map(lambda _l: _l%2, l))==p)
print(results.count(True))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ls = []
for _ in range(m):
  tmp = list(map(int,input().split()))[1:]
  lls = []
  for i in range(1,n+1):
    lls += [int(i in tmp)]
  ls += [lls]
p = list(map(int,input().split()))
count = 0
yyy = [0]*n
while True:
  if yyy[-1] == 2:
    break
  for mi in range(m):
    dd = 0
    for ni in range(n):
      c = 0
      c += ls[mi][ni] * yyy[ni]
      d = c%2
      dd += 1-int(d==p[mi])
  if dd == 0:
    count += 1
  yyy[0] += 1
  for j in range(0,n-1):
    if yyy[j] == 2:
      yyy[j] = 0
      yyy[j+1] += 1
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

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

if N < rank:
    print(0)
elif N == rank:
    print(1)
else:
    print(2**(N-rank))

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

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

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

ans = 0
B = []
for i in range(1,N+1) :
    B.append(i)
for i in range(1,N+1) :
    A = list(combinations(B,i))
    
    for a in A :
        
        for j in range(M) :
            cnt = 0
            for l in L[j][1:] :
                if l in a :
                    cnt += 1
            if (cnt%2) != P[j] :
                break
        else :
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=list(map(int,input().split()))
a=[]
for i in range(k):
    p=list(map(int,input().split()))
    p=set(p[1:])
    a.append(p)
r=list(map(int,input().split()))
ans=0
cou=0
for i in range(k):
    cout=0
    for j in range(i+1,k):
        if a[i]==a[j]:
            if r[i]!=r[j]:
                ans=1 
            else:
                cout=1
    if cout==1:
        cou+=1
k-=cou
if ans==0:
    if n<k:
        print(0)
    else:
        print(int(2**(n-k)))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import itertools

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import itertools

def is_lit(i, bit):
    l = [bit[j-1] for j in sockets[i]]
    return p[i] == l.count(True) % 2

count = 0
N, M = map(int, input().split())
bit_list = list(itertools.product([True, False], repeat = N))

sockets = []
for i in range(M):
    args = input().split(' ')
    k = int(args[0])
    sockets.append([int(args[i+1]) for i in range(k)])

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

for bit in bit_list:
    o = [is_lit(i, bit) for i in range(M)]
    if o.count(True):
        count += 1

print(count)

Submission status: Wrong Answer

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

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

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

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

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

print(combi)

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
input=sys.stdin.readline

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

X = 2**N
pf = -1
kssf=-1
for kss,p in zip(ks,ps):
  if X > 2:
    if (pf == p) and (kss==kssf):
      pass
    else:
      X//=2
  else:
    if pf != p:
      print(0)
      exit()
  pf = p
  kssf=kss
print(X)

Submission status: Wrong Answer

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

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

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

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

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

    return num

print(solve(N, plist, 1))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[]
for i in range(M):
    A.append(list(map(int,input().split())))
P=list(map(int,input().split()))
ans=0
for i in range(2**N,2**(N+1)):
        B=bin(i)
        count=0
        for j in range(M):
            tet=0
            for l in range(A[j][0]):
                tet+=int(B[A[j][l+1]+2])
            if tet//2==P[j]:
                  count+=1
        if count==M:
            ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

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

if N+1 < rank:
    print(0)
else:
    print(2**(N-rank))

Submission status: Wrong Answer

Solution code:
import itertools

def is_lit(i, bit):
    l = [bit[j-1] for j in sockets[i]]
    return p[i] == l.count(True) // 2

count = 0
N, M = map(int, input().split())
bit_list = list(itertools.product([True, False], repeat = N))

sockets = []
for i in range(M):
    args = input().split(' ')
    k = int(args[0])
    sockets.append([int(args[i+1]) for i in range(k)])

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

for bit in bit_list:
    o = [is_lit(i, bit) for i in range(M)]
    if o.count(True):
        count += 1

print(count)

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

a=set()

for idx,k in enumerate(K):
    pre = set()
    for i in range(2 ** n):
        pre_ans = 0
        for j in k[1:]:
            pre_ans += i>>(j-1)&1
        if pre_ans%2 == p[idx]:
            pre.add(bin(i))
    if len(a)==0:
        a=pre
    else:
        a=a&pre

print(len(a))

Submission status: Wrong Answer

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

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

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


result = 0


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

    flag = 1




    for j in range(len(k)):

        tmp_sum = 0


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

        equal_p = tmp_sum % 2

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



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



print(result)

Submission status: Wrong Answer

Solution code:

if __name__ == '__main__':
    n,m = list(map(int, input().split()))
    ks = []
    bitnums = []
    for i in range(m):
        ks.append(list(map(int, input().split())))
        bitnum = 0
        for j in range(1, ks[i][0]+1):
            bitnum += 1 << (ks[i][j]-1)
        bitnums.append(bitnum)
    p = list(map(int, input().split()))

    np = [1] * (2**n)
    np[0] = 0

    for i in range(1, len(np)):
        for j in range(m):
            cnt = bin(i & bitnums[j]).count("1")
            #if(cnt == 0):
            #    np[i] = 0
            #    break
            if(cnt % 2 != p[j]):
                np[i] = 0
                break
    
    #for i in range(len(np)):
    #    print("{0} {1}".format(np[i], bin(i)))
        
    print(sum(np))

Submission status: Wrong Answer

Solution code:
N, M = [int(i) for i in input().split()]
masks = [0] * M

for i in range(M):
    inp = [int(j) for j in input().split()]
    k = inp[0]
    s = inp[1:]
    b = [0] * M
    for j in range(M):
        b[j] = "1" if j+1 in s else "0"
    masks[i] = int("".join(reversed(b)), 2)
    # print(list(reversed(b)))

ps = [int(p) for p in input().split()]
s = 0

for t in range(2**N):
    for i in range(M):
        v = masks[i] & t
        # print("i:", i)
        # print("t: {}\nm: {}\nv: {}\n\n".format(format(t, "b"), format(masks[i], "b"), format(v, "b")))
        if format(v, "b").count("1") % 2 != ps[i]:
            break
    else:
        # print("count")
        s += 1

print(s)

Submission status: Wrong Answer

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

ans = 0
for t in product([0, 1], repeat=N):
    sw = {i+1: t[i] for i in range(N)}
    flg = 1
    num = 0
    for ind in range(M):
        for j in s[ind]:
            num += sw[j]
        if num % 2 != p[ind]:
            flg = 0
            break
    if flg:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ks = [list(map(int,input().split())) for x in range(m)]
plis = list(map(int,input().split()))
ans = 0
llis=[]
for x in range(2**n):
    sw_lis = [0]*n
    for y in range(n):
        if ((x >> y)&1):
            sw_lis[y] = 1
    llis.append(sw_lis)
for sw in llis:
    judge = 0
    on = 0
    for x in range(m):
        for i in ks[x][1:]:
            judge += sw[i-1]
        if judge%2 == plis[x]:
            on += 1    
    if on == m:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

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

if N < rank:
    print(0)
else:
    print(2**(N-rank))

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
input=sys.stdin.readline

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

X = 2**N
pf = -1
for p in ps:
  if X > 2:
    X//=2
  else:
    if pf != p:
      print(0)
      exit()
  pf = p
print(X)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
k = []
s = []
for _ in range(m):
    ki, *si = map(int, input().split())
    k.append(ki)
    s.append(si)
p = list(map(int, input().split()))
cnt = 0
for i in range(2**n):
    flag = True
    for ki, si, pi in zip(k,s,p):
        if not list(bin(i & sum(si))).count("1") % 2 == pi:
            flag = False
            break
    if flag == True:
        cnt += 1
            
print(cnt)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
l =[]
pl = []
for i in range(m):
  l.append(list(int(i) for i in input().split()))
pl= list((int(i) for i in input().split()))
cnt = 0
sw = [0]*n
for i in range(2*n):
  sw = list(format(i,"b"))
  while len(sw) < n:
    sw.insert(0,"0")
  flag = 1
  for j in range(m):
    tmp = 0
    for k in range(l[j][0]):
      if sw[-l[j][k+1]] == "1":
        tmp += 1
    if tmp % 2 != pl[j]:
      flag = 0
  if flag == 1:
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:

if __name__ == '__main__':
    n,m = list(map(int, input().split()))
    ks = []
    bitnums = []
    for i in range(m):
        ks.append(list(map(int, input().split())))
        bitnum = 0
        for j in range(1, ks[i][0]+1):
            bitnum += 1 << (ks[i][j]-1)
        bitnums.append(bitnum)
    p = list(map(int, input().split()))

    np = [1] * (2**n)
    np[0] = 0

    for i in range(1, len(np)):
        for j in range(m):
            cnt = bin(i & bitnums[j]).count("1")
            if(cnt == 0):
                np[i] = 0
                break
            if(cnt % 2 != p[j]):
                np[i] = 0
                break
    
    #for i in range(len(np)):
    #    print("{0} {1}".format(np[i], bin(i)))
        
    print(sum(np))

Submission status: Wrong Answer

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

num=2**n
count=0
for i in range(num):
    lump=1
    x=[]
    for j in range(n):
        x.append((i*2//(2**(j+1)))% 2)
    for k in range(m):
        sum=0
        for k1 in range(len(list1[k][1:])):
            if x[list1[k][k1]-1]==1:
                sum=sum+1
        if sum % 2!=p[k]:
            lump=0
    if lump==1:
        count=count+1
print(count)

Submission status: Wrong Answer

Solution code:
import itertools
N,M = map(int,input().split())
K = [0]*M
S = [[0] *N for _ in range(M)]
for i in range(M):
    tmp = list(map(int,input().split()))
    K[i] = tmp[0]
    for s in tmp[1:]:
        S[i][s-1] = 1
P = list(map(int,input().split()))

ptns = list(itertools.product((0,1),repeat=N))
ans = 0
# 全てのON/OFFパターン
for p in ptns:
    # 全ての電球
    on_count = 0
    for i in range(M):
        # ONになっているスイッチ
        for j in range(N):
            on_count += S[i][j] and p[j]
        if on_count%2 != P[i]:
            break
        
    else:
        # print(p)
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools as it
N,M = map(int,input().split())
slk = []
for _ in range(M):
    slk.append(list(map(int,input().split())))
p = list(map(int,input().split()))
#print(N,M)
#print(slk)
#print(p)

s = [i+1 for i in range(N)]
cb = 0
for i in range(1,N+1):
    cmbi = list(it.combinations(s, i))
    #print('i,cmbi:',i,cmbi)
    for ccmb in cmbi:
        for j,slki in enumerate(slk):
            g = 0
            #print('slki',slki)
            for k in range(slki[0]):
                if slki[k+1] in ccmb:
                    g += 1
            #print('g,p:',g,p[j])
            if g%2 == p[j]:
                pass
            else:
                #print('error')
                break
        else:
            cb += 1
            #print('add succ;',cb)
print(cb)

Submission status: Wrong Answer

Solution code:
import numpy as np
NM= list(map(int,input().split()))
N = NM[0]
M = NM[1]

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

P = list(map(int,input().split()))
Pt = np.zeros((len(P),1))
for i in range(len(P)):
    Pt[i,0]=P[i]

ta = np.zeros((M,N))
for i in range(M):
    for j in range(len(S[i])):
        ta[i,S[i][j]-1]=1

sta = np.zeros((N,1))

count = 0

def func(k):
    global count
    global ta
    global sta
    global P
    for s1 in range(2):
        if k < N:
            sta[k] = s1
            func(k+1)
            if (np.dot(ta,sta)%2==Pt).all() and k<N-1:
                count+=1

func(0)
print(int(count))

Submission status: Wrong Answer

Solution code:


import itertools
N, M = map(int, input().split())
ks = [[int(i) for i in input().split()] for _ in range(M)]
p = list(map(int, input().split()))


k = []
s = []
for i in range(M):
    k.append(ks[i][0])
    s.append(ks[i][1:])

result = 1
for i in range(M):
    j = 1
    temp = 0
    while j < k[i]+1:
        c = itertools.combinations(s[i], j)
        for v in c:
            li = list(v)
            if p[i] == len(li) % 2:
                temp += 1
        j += 1
    result *= temp
print(result)

Submission status: Wrong Answer

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

# -*- coding: utf-8 -*-


from sys import stdin

############################################

import numpy as np
temp = stdin.readline().split()
N = int(temp[0])
M = int(temp[1])

data = []
for i in range(M):
    write = stdin.readline().split()
    if int(write[0]) == 1:
        data.append(write[1])
    else:
        data.append(write[1:int(write[0])+1])

ans = stdin.readline().split()

count = 0

datas = data

data = [0,1]

M=N

import itertools
if M == 1:
    a = list(itertools.product(data))
elif M == 2:
    a = list(itertools.product(data, data))
elif M == 3:
    a = list(itertools.product(data, data, data))
elif M == 4:
    a = list(itertools.product(data, data, data, data))
elif M == 5:
    a = list(itertools.product(data, data, data, data, data))
elif M == 6:
    a = list(itertools.product(data, data, data, data, data, data))
elif M == 7:
    a = list(itertools.product(data, data, data, data, data, data, data))
elif M == 8:
    a = list(itertools.product(data, data, data, data, data, data, data, data))
elif M == 9:
    a = list(itertools.product(data, data, data, data, data, data, data, data, data))
elif M == 10:
    a = list(itertools.product(data, data, data, data, data, data, data, data, data, data))
elif M == 11:
    a = list(itertools.product(data, data, data, data, data, data, data, data, data, data, data))

for element in a:
    for i, d in enumerate(datas):
        x = 0
        sum = 0
        if len(d) != 1:
            for dd in d:
               sum += element[int(dd)-1] 
        else:
           sum += element[int(d)-1]
           
        if sum%2 == int(ans[i]):
           continue
        else:
           x = 1
           break
       
    if x == 0:
        count+=1

print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
s = [0] * N
for i in range(M):
    k = list(map(int, input().split()))
    for a in k[1:]:
        s[a-1] = s[a-1] + 1
ans = 0
for i in s:
    if i <= 1:
        if ans == 0: ans = 1
        else: ans = ans * 2
print(ans)

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()))
ans = 0
for i1 in range(2):
    for i2 in range(2):
        for i3 in range(2):
            for i4 in range(2):
                for i5 in range(2):
                    for i6 in range(2):
                        for i7 in range(2):
                            for i8 in range(2):
                                for i9 in range(2):
                                    for i10 in range(2):
                                        switches = [i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]
                                        flag_temp = 0
                                        for i in range(m):
                                            temp = 0
                                            for l in range(s[i][0]):
                                                temp += switches[s[i][l+1]-1]
                                            if temp % 2 == p[i]:
                                                flag = 1
                                                flag_temp += 1
                                            else:
                                                flag = 0
                                        if flag == 1 and flag_temp == m:
                                            ans += 1
                                        elif flag == 0:
                                            break
                                            
print(int(ans/2**(10-n)))

Submission status: Wrong Answer

Solution code:
from itertools import combinations


def count_can_light(N, bulbs, ps):
    count = 0
    for i in range(1, N+1):
        for combi in combinations(range(1, N+1), i):
            is_ok = True
            for n, switches in enumerate(bulbs):
                if len(set(combi) & set(switches)) % 2 != ps[n]:
                    is_ok = False
                    break
            if is_ok:
                count += 1
    return count


def main():
    N, M = map(int, input().split())
    bulbs = []
    for _ in range(M):
        values = list(map(int, input().split()))
        bulbs.append(values[1:])
    ps = list(map(int, input().split()))
    print(count_can_light(N, bulbs, ps))
    

main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

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

if N < rank:
    print(0)
else:
    print(2**(N-rank))

Submission status: Wrong Answer

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

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

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

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

ans_sum = 0
pre_ = 0
for i1 in [0, 1]:
    for i2 in [0, 1]:
        for i3 in [0, 1]:
            for i4 in [0, 1]:
                for i5 in [0, 1]:
                    for i6 in [0, 1]:
                        for i7 in [0, 1]:
                            for i8 in [0, 1]:
                                for i9 in [0, 1]:
                                    for i10 in [0, 1]:
                                        p_ = [i1, i2, i3, i4, i5, i6, i7, i8, i9, i10]
                                        pre = p_[:N]
                                        if pre == pre_:
                                            break
                                        ans_ = 0
                                        for q in range(M):
                                            ans = 0
                                            for r in range(sk[q][0]):
                                                ans += pre[sk[q][r+1]-1]
                                            if ans > 0 and ans%2 == p[q]:
                                                ans_ +=1
                                        
                                        if ans_ == M:
                                            ans_sum += 1

                                        pre_ = pre

print(ans_sum)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M  = map(int,input().split())
coeff = np.zeros((M,N))
for i in range(M):
    inputs = list(map(int,input().split()))
    for switch in inputs[1:]:
        coeff[i][switch-1] = 1
onlist = list(map(int,input().split()))
extension = np.zeros((M,N+1))
extension[:,:N] = coeff
extension[:,N] = onlist
rankcoeff = np.linalg.matrix_rank(coeff)
rankext = np.linalg.matrix_rank(extension)
# print(rankcoeff,rankext)
if rankcoeff != rankext:
    print(0)
else:
    ans = 2**(N-rankcoeff)
    print(ans)

# cardlist = list(map(int,input().split()))