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:
inf = input().split()
N = int(inf[0])
M = int(inf[1])
ls = [[] for i in range(N)]
state = [0 for i in range(M)]
count = 0
log = []

for i in range(M):
    line = input().split()[1:]
    for a in line:
        ls[int(a)-1] += [i]

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

for n in range(2**N):
    s = n
    for m in range(N)[::-1]:
        if n>=(2**m):
            n -= 2**m
            for i in ls[m]:
                state[i] += 1
    for i in range(M):
        if not state[i]%2 == rule[i]:
            state[i] = 0
            break
        state[i] = 0
    else:
        count += 1
print(count)

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

pattern_count = 0
for n in range(2 ** N):
	switch_count = 0
	for i, ks in enumerate(KS):
		for s in ks[1:]:
			if n >> (s - 1) & 1:
				switch_count += 1
		else:
			if switch_count % 2 != P[i]:
				break
	else:
		pattern_count += 1
print(pattern_count)

Submission status: Wrong Answer

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

k = []
s = []
for _ in range(m):
    ks = list(map(int, input().split()))
    k.append(ks[0])
    s.append(ks[1:])
p = list(map(int, input().split()))

for bits in range(2**n):
    ans = 0
    for i in range(m):
        flag = True
        on_sum = 0
        for switch in s[i]:
            on_sum += ((bits >> (switch - 1)) & 1)
        flag = flag and ((on_sum % 2) == p[i])
    if flag:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

k = []
s = []
for i in range(m):
  list = input().split()
  k.append(int(list[0]))
  ss = []
  for j in range(k[i]):
    ss.append(int(list[j+1]))
  s.append(ss)

print(k)
print(ss)

Submission status: Wrong Answer

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

lamp=[]
switches=[]
temp=[]

for i in range(m):
    temp=list(map(int,input().split()))
    lamp.append(temp.pop(0))
    switches.append(temp)
    temp=[]

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

bit_list=[]

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

ans = 0

for b in bit_list:
    flag = 0
    sum  = 0
    for s,p in zip(switches,modul):
        for k in range(len(s)):
            sum=sum+int(b[s[k]-1])
        if sum%2 != p:
            flag = 1
            break
    if flag == 0:
        ans=ans+1

print(ans)

Submission status: Wrong Answer

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

lamp=[]
switches=[]
temp=[]

for i in range(m):
    temp=list(map(int,input().split()))
    lamp.append(temp.pop(0))
    switches.append(temp)
    temp=[]

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

bit_list=[]

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

ans = 0

for b in bit_list:
    flag = 0
    sum  = 0
    for s,p in zip(switches,modul):
        for k in range(len(s)):
            sum=sum+int(b[s[k]-1])
        if sum%2 != p:
            flag = 1
            break
    if flag == 0:
        ans=ans+1

print(bit_list)
print(ans)

Submission status: Wrong Answer

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

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

for i in s:
    mask = 0
    for j in i[1:]:
        mask |= 1<<(j-1)        
    kmask.append(mask)

result = 0
for i in range(0<<n):
    ok = True
    for mask,odd in zip(kmask,p):
        bc = bitcount(i&mask)
        if((bc&1)!=odd):
            ok = False
            break
    if ok:
        result += 1

print(result)

Submission status: Wrong Answer

Solution code:
def bitcount(bit):
    return bin(bit).count("1")

s = []
kmask = []
n,m = map(int,input().split())

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

for i in s:
    mask = 0
    for j in i[1:]:
        mask |= 1<<(j-1)        
    kmask.append(mask)

result = 0
for i in range(1,1<<n):
    ok = True
    for mask,odd in zip(kmask,p):
        bc = bitcount(i&mask)
        if((bc&1)!=odd):
            ok = False
            break
    if ok:
        result += 1

print(result)

Submission status: Wrong Answer

Solution code:
def bitcount(bit):
    return bin(bit).count("1")

s = []
kmask = []
n,m = map(int,input().split())

for i in range(m):
    s.append( list(map(int,input().split())) )
p = list(map(int,input().split()))
for i in s:
    mask = 0
    for j in i[1:]:
        mask |= 1<<(j-1)        
    kmask.append(mask)
result = 0
for i in range(1,1<<n):
    ok = True
    for mask,odd in zip(kmask,p):
        bc = bitcount(i&mask)
        if((bc == 0) or (bc&1)!=odd):
            ok = False
            break
    if ok:
        result += 1

print(result)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s = []
k = []
p = []
count = 0
for i in range(m):
    q = input().split()
    k.append(int(q[0]))
    q.remove(q[0])
    s.append(q)
    #print(q)
    for j in range(k[i]):
        s[i][j] = int(q[j])
        #print(s)
    
q = input().split()
for j in range(m):
        p.append(int(q[j]))
        #count.append([0])
#入力終了

       
for i in range(pow(2,n)):
    list = []
    for o in range(n):
        list.append(i%2)
        i = i // 2
    #print(list)
    for j in range(m):
        wa = 0
        q = 0
        for l in range(k[j] ):
            wa += list[s[j][l]-1]
        if wa%2 == p[j]:
            q += 1
        else:
            break
    if q == m-1:
        count += 1

#kotae = count[0]
#for i in range(1,m):
    #kotae *= count[i]

#print(kotae)
print(count)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s = []
k = []
p = []
count = 0
for i in range(m):
    q = input().split()
    k.append(int(q[0]))
    q.remove(q[0])
    s.append(q)
    #print(q)
    for j in range(k[i]):
        s[i][j] = int(q[j])
        #print(s)
    
q = input().split()
for j in range(m):
        p.append(int(q[j]))
        #count.append([0])
#入力終了

       
for i in range(pow(2,n)):
    list = []
    for o in range(n):
        list.append(i%pow(2,o+1))
        i = i // pow(2,o+1)
    #print(list)
    for j in range(m):
        wa = 0
        q = 0
        for l in range(k[j] ):
            wa += list[s[j][l]-1]
        if wa%2 == p[j]:
            q += 1
        else:
            break
    if q == m-1:
        count += 1

#kotae = count[0]
#for i in range(1,m):
    #kotae *= count[i]

#print(kotae)
print(count)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s = []
k = []
p = []
count = 0
for i in range(m):
    q = input().split()
    k.append(int(q[0]))
    q.remove(q[0])
    s.append(q)
    #print(q)
    for j in range(k[i]):
        s[i][j] = int(q[j])
        #print(s)
    
q = input().split()
for j in range(m):
        p.append(int(q[j]))
        #count.append([0])
#入力終了

       
for i in range(pow(2,n)):
    list = []
    for o in range(n):
        list.append(i%pow(2,o+1))
        i = i // pow(2,o+1)
    #print(list)
    for j in range(m):
        wa = 0
        q = 0
        for l in range(k[j] ):
            wa += list[s[j][l]-1]
        if wa%2 != p[j]:
            q += 1
        else:
            break
    if q == m-1:
        count += 1

#kotae = count[0]
#for i in range(1,m):
    #kotae *= count[i]

#print(kotae)
print(count)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s = []
k = []
p = []
for i in range(m):
    q = input().split()
    k.append(int(q[0]))
    q.remove(q[0])
    s.append(q)
    #print(q)
    for j in range(k[i]):
        s[i][j] = int(q[j])
        #print(s)
    
q = input().split()
for j in range(m):
        p.append(int(q[j]))
count = 0
for i in range(pow(2,n)):
    list = []
    for o in range(n):
        list.append(i%pow(2,o+1))
        i = i // pow(2,o+1)
    print(list)
    for j in range(m):
        wa = 0
        for l in range(k[j] ):
            wa += list[s[j][l]-1]
        if wa == p[j]*2:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import copy

L=[]

def check(M,p,tmp):
  n_ok=0
  sum=0
  for i in range(len(L)):
    for l in L[i]:
      sum+= 1 if tmp[l-1]==1 else 0
    if sum%2==p[i]:
      n_ok+=1
      
  if n_ok==M:
    return 1
  else:
    return 0

def rc(N,M,p,i,tmp):
  if i==N-1:
    return check(M,p,tmp)
  else:
    t1=copy.copy(tmp)
    t2=copy.copy(tmp)
    t1.append(0)
    t2.append(1)
    return rc(N,M,p,i+1,t1)+rc(N,M,p,i+1,t2)

N, M = map(int, input().split())
for _ in range(M):
    tmp = list(map(int,input().split()))
    L.append(tmp[1:])
p=list(map(int,input().split()))
S=[0 for _ in range(N)]

print(rc(N,M,p,-1,[]))

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

cmb = []
for i in range(N):
  cmb.extend(list(combinations(range(N), i + 1)))

A = {i: set() for i in range(N)}

for i in range(M):
  line = [int(i) for i in input().strip().split(' ')]
  for s in line[1:]:
    A[s - 1].add(i)

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

counter = 0
for c in cmb:
  # print(c)
  tmp = [0] * M
  for i in c:
    for j in A[i]:
      tmp[j] = (tmp[j] + 1) % 2
  if tmp == P:
    counter += 1

print(counter)

Submission status: Wrong Answer

Solution code:
from itertools import combinations

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

S = range(N)

ls = []
for i in range(N):
  ls.extend(list(combinations(range(N), i + 1)))

A = {i: [] for i in range(N)}

for i in range(M):
  line = [int(i) for i in input().strip().split(' ')]
  for s in line[1:]:
    A[s - 1].append(i)

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

counter = 0
for c in ls:
  #print(c)
  tmp = [0] * M
  for i in c:
    for j in A[i]:
      tmp[j] = (tmp[j] + 1) % 2
  if tmp == P:
    counter += 1

print(counter)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [0 for i in range(N)]
p = 0
ans = 0
for i in range(M):
    k,*s = map(int,input().split())
    for j in s:
        a[j-1] |= 1 << i

ps = list(map(int,input().split()))
for i,j in enumerate(ps):
    p |= j << i
for i in range(1<<N):
    t = 0
    for j in range(N):
        if(i>>j & 1):
            t ^= a[j]
    if t is p:
        ans += 1

print(ans)
#print(p)
#print(a)

Submission status: Wrong Answer

Solution code:
import itertools as itt
#n進m桁のbit列の作成
def bit(n,m):
    bi = list((itt.product([i for i in range(n)],repeat = m)))
    return bi
#入力データの受け取り
N,M = list(map(int,input().split()))
L = [list(map(int,input().split())) for  _ in range(M)]
P = [int(s) for s in input().split()]

ans = 0
petterns = bit(2,N)
for pettern in petterns:#bit列から一つ取り出す
    count = 0
    flag = 1
    for i in range(M): #電球を一つ取り出す
        #点灯しているスイッチをカウント
        for j in range(L[i][0]):#j番目のスイッチを一つ取り出す
            if pettern[L[i][j+1] - 1] == 1:
                count += 1
        if count % 2 != P[i]:
            count = 0
            flag = 0
    if flag == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

# 指定された電球(sたち)が全部付いているときを10進数にしてリスト
s = []
for i in ks :
        t = 0
        for j in range(len(i)) :
                t += 2**(n-i[j])
                s.append(t)

# 2**nまでの二進数の中で電球１がつくやつ→電球２がつく→・・・最後まで満たしたら1を足す。を繰り返す
ans = 0
for i in range(2**n) :
        flag = True
        for j in range(m) :
                if bin(s[j] & i).count('1') % 2 != p[j] :
                        flag = False
                        break
        if flag :
                ans += 1
print(ans)

Submission status: Wrong Answer

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

n_switches = []
switches = []
for i in range(M):
    ipt = list(map(int, input().split()))
    n_switches.append(int(ipt[0]))
    switches.append(ipt[1:])


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

ans = 0

# ランプの光り方のパターンだけ
for i in range(N**2):
    ptn = bin(i)[2:].rjust(N, '0')

    allLight = True  # 全ての電球が光っているかどうか（一つでも光っていなければそのパターンは無効）

    # 電球の数だけ
    for j in range(M):

        n_light = 0
        # 電球に対するスウィッチの数だけ
        for k in range(n_switches[j]):
            # スウィッチが光っていれば
            if ptn[switches[j][k] - 1] == '1':
                n_light += 1

        if n_light % 2 != p[j]:
            allLight = False
            break

    if allLight:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from operator import add
n, m = [int(i) for i in input().split()]

lamp = [None] * m
for i in range(m):
    tmp = ['0'] * n
    for k in [int(j) for j in input().split()][1:]:
        tmp[n-k] = '1'
    lamp[i] = int(''.join(tmp), 2)

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

ans = 0
for i in range(1, 2**n):
    if all([bin(i & lamp[j]).count("1") % 2 == p[j] for j in range(m)]):
        ans += 1

print(ans)

Submission status: Wrong Answer

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

def mask(l):
    m = 0
    for i in l:
        m += 2**(i-1)
    return m

masks = list(map(mask, sw))

ret = 0
for i in range(2**N):
    if all(bin(i&m).count('1')%2 == p for m, p in zip(masks, P)):
        ret += 1
print(ret)

Submission status: Wrong Answer

Solution code:
def c_switches(N, M, Switches, P):
    import numpy as np

    def rank_matrix(matrix):
        """mod2 上で行列の階数を求める"""
        num_row, num_col = matrix.shape[0], matrix.shape[1]
        rank = 0

        for col in range(num_col):
            # ピボット探し
            pivot = -1
            max_element = 0  # 最大の要素(1しかないが)がある場所を探す
            for row in range(rank, num_row):
                if matrix[row][col] > max_element:
                    max_element = matrix[row][col]
                    pivot = row
            if pivot == -1:
                continue  # ピボットが見つからない。次の列へ

            matrix[pivot, :], matrix[rank, :] = matrix[rank, :], matrix[pivot, :]  # 行を交換

            # (行列の要素は0または1しかないので、ピボットの値を1にする操作は不要)
            # ピボットのある列の値がすべて0となるように、掃き出しを行う
            for row in range(num_row):
                if row != rank and matrix[row][col] == 1:
                    for col2 in range(num_col):
                        matrix[row][col2] = (matrix[row][col2] + matrix[rank][col2]) % 2
            rank += 1
        return rank

    # 電球iがスイッチjとつながっているとき a_{ij}=1, そうでないなら0とする
    a = np.zeros((M, N), dtype='int8')
    for t, (_, *switches) in enumerate(Switches):
        for s in switches:
            a[t][s - 1] = 1
    p = np.reshape(P, (-1, 1))
    ap = np.concatenate((a, p), axis=1)  # 拡大係数行列
    rank_a, rank_ap = rank_matrix(a), rank_matrix(ap)
    return 2**(N - rank_a) if rank_a == rank_ap else 0
    # 参考: http://drken1215.hatenablog.com/entry/2019/03/20/202800

N, M = [int(i) for i in input().split()]
Switches = [[int(i) for i in input().split()] for j in range(M)]
P = [int(i) for i in input().split()]
print(c_switches(N, M, Switches, P))

Submission status: Wrong Answer

Solution code:
def c_switches(N, M, Switches, P):
    import numpy as np

    def rank_matrix(matrix):
        """mod2 上で行列の階数を求める"""
        num_row, num_col = matrix.shape[0], matrix.shape[1]
        rank = 0

        for col in range(num_col):
            # ピボット探し
            pivot = -1
            max_element = 0  # 最大の要素(1しかないが)がある場所を探す
            for row in range(rank, num_row):
                if matrix[row][col] > max_element:
                    max_element = matrix[row][col]
                    pivot = row
            if pivot == -1:
                continue  # ピボットが見つからない。次の列へ

            matrix[pivot, :], matrix[rank, :] = matrix[rank, :], matrix[pivot, :]  # 行を交換

            # (行列の要素は0または1しかないので、ピボットの値を1にする操作は不要)
            # ピボットのある列の値がすべて0となるように、掃き出しを行う
            for row in range(num_row):
                if row != rank and matrix[row][col] == 1:
                    for col2 in range(num_col):
                        matrix[row][col2] = (matrix[row][col2] - matrix[rank][col2] + 2) % 2
            rank += 1
        return rank

    # 電球iがスイッチjとつながっているとき a_{ij}=1, そうでないなら0とする
    a = np.zeros((M, N), dtype='int8')
    for t, (_, *switches) in enumerate(Switches):
        for s in switches:
            a[t][s - 1] = 1
    p = np.reshape(P, (-1, 1))
    ap = np.concatenate((a, p), axis=1)  # 拡大係数行列
    rank_a, rank_ap = rank_matrix(a), rank_matrix(ap)
    return 2**(N - rank_a) if rank_a == rank_ap else 0
    # 参考: http://drken1215.hatenablog.com/entry/2019/03/20/202800

N, M = [int(i) for i in input().split()]
Switches = [[int(i) for i in input().split()] for j in range(M)]
P = [int(i) for i in input().split()]
print(c_switches(N, M, Switches, P))

Submission status: Wrong Answer

Solution code:
def c_switches(N, M, Switches, P):
    import numpy as np

    def rank_matrix(matrix):
        """mod2 上で行列の階数を求める"""
        num_row, num_col = matrix.shape[0], matrix.shape[1]
        rank = 0

        for col in range(num_col):
            # ピボット探し
            pivot = -1
            max_element = 0  # 最大の要素(1しかないが)がある場所を探す
            for row in range(rank, num_row):
                if matrix[row][col] > max_element:
                    max_element = matrix[row][col]
                    pivot = row
            if pivot == -1:
                continue  # ピボットが見つからない。次の列へ

            matrix[pivot, :], matrix[rank, :] = matrix[rank, :], matrix[pivot, :]  # 行を交換

            # (行列の要素は0または1しかないので、ピボットの値を1にする操作は不要)
            # ピボットのある列の値がすべて0となるように、掃き出しを行う
            for row in range(num_row):
                if row != rank and matrix[row][col] == 1:
                    for col2 in range(num_col):
                        matrix[row][col2] = (matrix[row][col2] - matrix[rank][col2]) % 2
            rank += 1
        return rank

    # 電球iがスイッチjとつながっているとき a_{ij}=1, そうでないなら0とする
    a = np.zeros((M, N), dtype='int8')
    for t, (_, *switches) in enumerate(Switches):
        for s in switches:
            a[t][s - 1] = 1
    p = np.reshape(P, (-1, 1))
    ap = np.concatenate((a, p), axis=1)  # 拡大係数行列
    rank_a, rank_ap = rank_matrix(a), rank_matrix(ap)
    return 2**(N - rank_a) if rank_a == rank_ap else 0
    # 参考: http://drken1215.hatenablog.com/entry/2019/03/20/202800

N, M = [int(i) for i in input().split()]
Switches = [[int(i) for i in input().split()] for j in range(M)]
P = [int(i) for i in input().split()]
print(c_switches(N, M, Switches, P))

Submission status: Wrong Answer

Solution code:
def c_switches(N, M, Switches, P):
    import numpy as np

    def rank_matrix(matrix):
        """mod2 上で行列の階数を求める"""
        num_row, num_col = matrix.shape[0], matrix.shape[1]
        rank = 0

        for col in range(num_col):
            # ピボット探し
            pivot = -1
            max_element = 0  # 最大の要素(1しかないが)がある場所を探す
            for row in range(rank, num_row):
                if matrix[row][col] > max_element:
                    max_element = matrix[row][col]
                    pivot = row
                    break
            else:
                continue  # ピボットが見つからない。次の列へ

            matrix[pivot, :], matrix[rank, :] = matrix[rank, :], matrix[pivot, :]  # 行を交換

            # (行列の要素は0または1しかないので、ピボットの値を1にする操作は不要)
            # ピボットのある列の値がすべて0となるように、掃き出しを行う
            for row in range(num_row):
                if row != rank and matrix[row][col] == 1:
                    for col2 in range(num_col):
                        matrix[row][col2] = (matrix[row][col2] - matrix[rank][col2]) % 2
            rank += 1
        return rank

    # 電球iがスイッチjとつながっているとき a_{ij}=1, そうでないなら0とする
    a = np.zeros((M, N), dtype='int8')
    for t, (_, *switches) in enumerate(Switches):
        for s in switches:
            a[t][s - 1] = 1
    p = np.reshape(P, (-1, 1))
    ap = np.concatenate((a, p), axis=1)  # 拡大係数行列
    rank_a, rank_ap = rank_matrix(a), rank_matrix(ap)
    return 2**(N - rank_a) if rank_a == rank_ap else 0
    # 参考: http://drken1215.hatenablog.com/entry/2019/03/20/202800

N, M = [int(i) for i in input().split()]
Switches = [[int(i) for i in input().split()] for j in range(M)]
P = [int(i) for i in input().split()]
print(c_switches(N, M, Switches, P))

Submission status: Wrong Answer

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

import numpy as np
n_pattern = 2**N - 1
form = '0{0}b'.format(N)
ans = 0
from operator import itemgetter
for i in range(1, n_pattern+1):
    state = str(format(i, form))
    counter = 0
    for j,k in enumerate(switch_idx):
        if (itemgetter(*(np.array(k)-1))(state).count('1') % 2) == p[j]:
            counter += 1
        if len(switch_idx) == counter:
            ans += 1

print(ans)

Submission status: Wrong Answer

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

for i in range(2**N):#switch loop
    for j in range(M):#num of light
        sw_see=0
        for k in ks[j][1:]:#switch to see
            sw_see+=2**(k-1)
        if (bin(i&sw_see)).count('1')%2!=p[j]:
            break
    else:
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
def c_switches(N, M, Switches, P):
    import numpy
    a = [[0] * N for _ in range(M)]
    ap = [[0] * (N + 1) for _ in range(M)]
    for t, (_, *switches) in enumerate(Switches):
        for s in switches:
            a[t][s - 1] = 1
            ap[t][s - 1] = 1
        ap[t][-1] = P[t]
    a = numpy.array(a)
    ap = numpy.array(ap)
    a_rank = numpy.linalg.matrix_rank(a)
    ap_rank = numpy.linalg.matrix_rank(ap)
    if a_rank != ap_rank:
        ans = 0
    else:
        ans = 2**(N - a_rank)
    return ans

N, M = [int(i) for i in input().split()]
Switches = [[int(i) for i in input().split()] for j in range(M)]
P = [int(i) for i in input().split()]
print(c_switches(N, M, Switches, P))

Submission status: Wrong Answer

Solution code:
import sys

def all_lighted(input, mod, pattern):
    for i, bulb in enumerate(input):
        if bin(bulb & pattern).count('1') % 2 == mod[i]:
            next
        else:
            return False
    
    return True


def main():
    num_switch, num_bulb = [int(x) for x in sys.stdin.readline().split()]
    input = [0] * num_bulb

    for bulb in input:
        for x in sys.stdin.readline().split()[1:]:
            bulb += 2**(int(x) - 1)

    mod = [int(x) for x in sys.stdin.readline().split()]

    count = 0

    for pattern in range(2 ** num_switch):
        if all_lighted(input, mod, pattern): count += 1

    print(count)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

def all_lighted(input, mod, pattern):
    for i, bulb in enumerate(input):
        if bin(bulb and pattern).count('1') % 2 == mod[i]:
            next
        else:
            return False
    
    return True


def main():
    num_switch, num_bulb = [int(x) for x in sys.stdin.readline().split()]
    input = [0] * num_bulb

    for bulb in input:
        for x in sys.stdin.readline().split()[1:]:
            bulb += 2**(int(x) - 1)

    mod = [int(x) for x in sys.stdin.readline().split()]

    count = 0

    for i in range(2 ** num_switch):
        if all_lighted(input, mod, i): count += 1

    print(count)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3.4

# abc128_c

def main():
    # Input
    n, m = [int(s) for s in input().split()]
    reports = [[int(s) for s in input().split()] for _ in range(m)]
    ps = [int(s) for s in input().split()]
    # Get ans
    def get_switch_lists():
        for i in range(2**n):
            yield [(i//2**k)%2 for k in range(n)]
    def get_odd(switch_list, repo):
        return sum(switch_list[r-1] for r in repo if r!=0) % 2
    ans = 0
    for switch_list in get_switch_lists():
        qs = (get_odd(switch_list, repo) for repo in reports)
        if all(p==q for p, q in zip(ps, qs)):
            ans += 1
    # Output
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3.4

# abc128_c

def main():
    # Input
    n, m = [int(s) for s in input().split()]
    reports = [[int(s) for s in input().split()] for _ in range(m)]
    ps = [int(s) for s in input().split()]
    # Get ans
    def get_switch_lists():
        for i in range(n**2):
            yield [(i//2**k)%2 for k in range(n)]
    def is_light(repo):
        return 
    ans = 0
    for switch_list in get_switch_lists():
        qs = (sum(switch_list[r-1] for r in repo if r!=0) % 2 for repo in reports)
        if all(p==q for p, q in zip(ps, qs)):
            ans += 1
    # Output
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

import sys

n,m = [ int(x) for x in sys.stdin.readline().split() ]
s = list()
for _ in range(m):
    t= [ int(x) for x in sys.stdin.readline().split() ][1:]
    flag = 0
    for x in t: flag|= x
    s.append( flag )
p = [ int(x) for x in sys.stdin.readline().split() ]
#
ans= 0
for test in range(2**n):
    fail= False
    for i in range(m):
        if bin(s[i]&test).count("1")%2 != p[i]:
            fail= True
            break
    #
    if not fail: ans+= 1
#
print( ans )

Submission status: Wrong Answer

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

switch = 2**N
answer = 0

for i in range(switch):
  lamp = []
  bit = format(i,"#010b")[::-1]
  print(bit)
  for j in range(len(each_s)):
    count = 0
    for k in each_s[j]:
      if(bit[k-1] == "1"):
        count += 1
    lamp.append(count % 2)
  if lamp == p:
    answer += 1
print(answer)

Submission status: Wrong Answer

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

switch = 2**N
answer = 0

for i in range(switch):
  lamp = []
  for j in range(len(each_s)):
    count = 0
    for k in each_s[j]:
      if(bin(i>>k)[-1] == "1"):
        count += 1
    lamp.append(count % 2)
  if lamp == p:
    answer += 1
print(answer)

Submission status: Wrong Answer

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

switch = 2**N
answer = 0

for i in range(switch):
  lamp = []
  for j in range(len(each_s)):
    count = 0
    for k in each_s[j]:
      if(bin(i>>k)[-1] == "1"):
        count += 1
    lamp.append(count % 2)
  if lamp == p:
    answer += 1
print(answer)

Submission status: Wrong Answer

Solution code:
import itertools

N, M = (int(x) for x in input().split())
ls_k = []

for i in range(M):
    string_k = input().split()
    ls_k.append(list(map(int, string_k)))
    del ls_k[i][0]

string_p = input().split()
ls_p = list(map(int, string_p))

ans = 0


def S_gen(N):
    S_pat = []
    set_lis = list(range(1, N+1))
    for i in range(1, N+1):
        S_pat.extend(list(itertools.combinations(set_lis, i)))
    return S_pat


S_pat = S_gen(N)


count = 0

for i in S_pat:
    correct = True
    for j in range(M):
        check = []
        # print(set(ls_k[j][:]))
        # print(set(i))
        check = list(set(ls_k[j][:]) & set(i))
        # print(check)
        if len(check) % 2 != ls_p[j]:
            correct = False
    # print(correct)
    if correct:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
def solve():
    N, M = map(int, input().split())
    K = [sum([2 ** (int(i) - 1) for i in input().split()]) for _ in
              range(M)]
    P = [int(i) for i in input().split()]
    count = 0
    for i in range(2 ** N):
        for k, p in zip(K, P):
            if bin(k & i).count('1') % 2 != p:
                break
        else:
            count += 1
            # print(bin(i))

    print(count)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import itertools

n, m = [int(elem) for elem in input().split()]
ks = []
ss = []

for i in range(0, m):
  tmp = [int(elem) for elem in input().split()]
  ks.append(tmp[0])
  ss.append(tmp[1:])
  
ps = [int(elem) for elem in input().split()]

res = []
for k, s, p in zip(ks, ss, ps):
  combi = list(itertools.combinations(s, k))
  cand = []
  for elem in combi:
    if p == 0:
      cand.append(list(elem))
    else:
      if len(elem) % p == 0:
        cand.append(list(elem))
  res += cand
  print(res)