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)]
for i in range(M):
    k = list(map(int, input().split()))
    K[i] = k[1:]
 
P = list(map(int, input().split()))

ans = 0
for i in range(1, 2 ** N):
    switch = [0] * M
    for j in range(N):
        if (i >> j) & 1: # bitチェック、1桁目が1かどうか、1ならスイッチがオン
            for l in range(M):
                if j + 1 in K[l]: # j+1番のスイッチがオンだがl番の電球につながっているか？
                    switch[l] += 1 # l番目の電球につながっているスイッチがオンの数
     
    for j in range(M):
        if switch[j] % 2 != P[j]:
            break 
    else:
        ans += 1
            
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Apr  3 14:23:44 2020

@author: liang
"""

N, M = map(int,input().split())
bulbs = [list(map(int,input().split()))[1:] for _ in range(M)]
p = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    lights = [1 if (i>>j)&1 == 1 else 0 for j in range(N)]
    if all(sum(lights[x-1] for x in bulbs[k])%2 == p[k] for k in range(len(bulbs))):
            ans += 1



print(bulbs)
print(p)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from itertools import product

def main():
    n, m = [int(i) for i in input().split()]
    sw = np.zeros((m, n), int)
    for i in range(m):
        for s in input().split()[1:]:
            sw[i][int(s)-1] = 1

    p = np.array([int(i) for i in input().split()])
    print(sw)
    res = 0
    for t in product((0, 1), repeat=n):
        stat = np.array(t)
        if np.array_equal(p, np.dot(sw, stat) % 2):
            res += 1
    print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def readlines(n):
    for _ in range(n):
        k, *s = map(int, input().split())
        yield s

def on(s, p, comb):
    return len([s_ for s_ in s if s_ in comb]) % 2 == p

def main():
    n, m = map(int, input().split())
    switches = list(range(1, n+1))
    S = list(readlines(m))
    P = list(map(int, input().split()))
    for i in range(1, n+1):
        for comb in combinations(switches, i):
            if all(on(s, p, set(comb)) for s, p in zip(S, P)):
                yield 1

print(sum(main()))

Submission status: Wrong Answer

Solution code:
from functools import reduce
N,M = [int(x) for x in input().split()]
st = [0]*M
st2 = [0]*N
for i in range(M):
  a = list(map(int,input().split()))
  for j in range(a[0]):
    st[i] += 10**(a[j+1]-1)
for i in range(N):
  for j in range(M):
    st2[i] += (st[j] & 1)*(10**(M - (j+1)))
    st[j] = st[j] // 10
b = map(int,input().split())
p = reduce( lambda c,d:10*c+d, b)
h = 0
cnt = 0
for i in range(2**N):
  for j in range(M):
    if (i >> j) & 1:
      h = h ^ st2[j]
  if p == h:
    cnt += 1
  h = 0
print(cnt)

Submission status: Wrong Answer

Solution code:
import math
import copy
from copy import deepcopy
import sys
import fractions
# import numpy as np
from functools import reduce
# import statistics
import decimal
import heapq
import collections
import itertools
from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

s = getSomeInputListInt(m)
p = getInputListInt()

s_bit = []

for tmp_s in s:
    tmp_bit = 0
    for i in range(1, tmp_s[0] + 1, 1):
        aaa = 1 << (i - 1)
        tmp_bit = aaa | tmp_bit
    s_bit.append(tmp_bit)

ans = 0
for i in range(int(pow(2, m))):
    flg = True
    for j in range(m):
        cnt = bin(s_bit[j] & i).count("1")
        if cnt % 2 != p[j]:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
dic_s = {}
for i  in range(n):
    dic_s[i] = []
for i in range(m):
    a = list(map(int, input().split()[1:]))
    for num in a:
        dic_s[num-1].append(i)
p = list(map(int, input().split()))
oridinal = []
for tmp in p:
    if tmp == 0:
        oridinal.append(True)
    else:
        oridinal.append(False)

total = 0

for i in range(2 ** n): # n個のスイッチの組み合わせ
    judge = [oridinal[i] for i in range(m)]
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 1だったら(オンだったら)
            for d in dic_s[j]: #jにつながる電球つく
                judge[d] = not judge[d]
    if all(judge):      # ぜんぶついた！
        total+=1
        break
print(total)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = []
for _ in range(M):
    arr = list(map(int, input().split()))
    bit = 0
    for i in arr[1:]:
        # print(i)
        bit = bit | (1 << (i - 1))
    # print('bit', bit, bin(bit))
    S.append(bit)
    # S.append(arr[1:])
P = list(map(int, input().split()))
# print('S')
# print(S)
# print('P', P)
ans = 0
for bit in range(1 << N):
    cnt = 0
    for i in range(M):
        # print('S[i], bit', bin(S[i]), bin(bit))
        p = S[i] & bit
        # print('p', bin(p))
        on = 0
        for j in range(N):
            # print('judge', 1 << j, p & (1 << j))
            if p & (1 << j):
                on += 1
            # if p & (1 << j):
            #     on += 1
        # print('P[i], i, on', P[i], i, on)
        # print('on', on)
        if (on % 2) == P[i]:
            cnt += 1
    if cnt == M:
        ans += 1
    if bit == 100:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = []
for _ in range(M):
    arr = list(map(int, input().split()))
    bit = 0
    for i in arr[1:]:
        # print(i)
        bit = bit | (1 << (i - 1))
    # print('bit', bit, bin(bit))
    S.append(bit)
    # S.append(arr[1:])
P = list(map(int, input().split()))
# print('S')
# print(S)
# print('P', P)
ans = 0
for bit in range(1 << N):
    cnt = 0
    for i in range(M):
        # print('S[i], bit', bin(S[i]), bin(bit))
        p = S[i] & bit
        # print('p', bin(p))
        on = 0
        for j in range(N):
            # print('judge', 1 << j, p & (1 << j))
            if p & (1 << j):
                on += 1
            # if p & (1 << j):
            #     on += 1
        # print('P[i], i, on', P[i], i, on)
        # print('on', on)
        if (on % 2) == P[i]:
            cnt += 1
    if cnt >= M:
        ans += 1
    if bit == 100:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = []
for _ in range(M):
    arr = list(map(int, input().split()))
    bit = 0
    for i in arr[1:]:
        # print(i)
        bit = bit | (1 << (i - 1))
    # print('bit', bit, bin(bit))
    S.append(bit)
    # S.append(arr[1:])
P = list(map(int, input().split()))
# print('S')
# print(S)
# print('P', P)
ans = 0
for bit in range(1 << N):
    cnt = 0
    for i in range(M):
        # print('S[i], bit', bin(S[i]), bin(bit))
        p = S[i] & bit
        # print('p', bin(p))
        on = 0
        for j in range(N):
            # print('judge', 1 << j, p & (1 << j))
            if (p >> j) & 1:
                on += 1
            # if p & (1 << j):
            #     on += 1
        # print('P[i], i, on', P[i], i, on)
        # print('on', on)
        if (on % 2) == P[i]:
            cnt += 1
    if cnt >= M:
        ans += 1
    if bit == 100:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = []
for _ in range(M):
    arr = list(map(int, input().split()))
    bit = 0
    for i in arr[1:]:
        bit = bit | (1 << (i - 1))
    # print('bit', bit, bin(bit))
    S.append(bit)
    # S.append(arr[1:])
P = list(map(int, input().split()))
# print('S')
# print(S)
# print('P', P)
ans = 0
for bit in range(1 << N):
    cnt = 0
    for i in range(M):
        p = S[i] & bit
        # print('p', bin(p), bin(S[i]), bin(bit))
        on = 0
        for j in range(M):
            if p & (1 << j):
                on += 1
        # print('P[i]', P, i)
        if (on % 2) == P[i]:
            cnt += 1
    if cnt >= M:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = []
for _ in range(M):
    arr = list(map(int, input().split()))
    bit = 0
    for i in arr[1:]:
        bit = bit | (1 << (i - 1))
    # print('bit', bit, bin(bit))
    S.append(bit)
    # S.append(arr[1:])
P = list(map(int, input().split()))
# print('S')
# print(S)
# print('P', P)
ans = 0
for bit in range(1 << N):
    cnt = 0
    for i in range(M):
        p = S[i] & bit
        # print('p', bin(p), bin(S[i]), bin(bit))
        on = 0
        for j in range(M):
            if p & (1 << j):
                on += 1
        # print('p[i]', P, i)
        if (on % 2) == P[i]:
            cnt += 1
    if cnt == M:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def roop(onoff, n):
    swit[n] = onoff
    if n == N-1:
        cur = 0
        flag = True
        for i in range(M):
            for s in range(1,data[i][0]+1):
                cur += swit[data[i][s]-1]
            if cur%2 != p[i]:
                flag = False
                break
        if flag:
            return 1
        else:
            return 0
    else:
        return roop(0,n+1) + roop(1,n+1)
        

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

swit = [0]*N
print(roop(0,0) + roop(1,0))

Submission status: Wrong Answer

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

res = 0
for bit in range(2**N):
  sw = [0] * N
  for i in range(N):
    sw[i] = (bit >> i) & 1
  are_shining = True
  for i in range(M):
    cnt_on = 0
    for j in range(k[i]):
      if sw[s[i][j]-1] == 1:
        cnt_on += 1
    if cnt_on % 2 != p[i]:
      are_shining = False
  if are_shining:
    res += 1

print(res)

Submission status: Wrong Answer

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

cnt = 0

for i in range(2 ** N):
    flag = True
    for j in range(M):
        if not([(i >> k-1) for k in s[j]].count(1) % 2 == p[j] & 1):
            flag = False
    if flag:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

Solution code:
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
# mod = 10**9 + 7

from itertools import product

n, m = map(int, input().split())
s = [list(map(lambda x:int(x)-1,input().split())) for _ in range(m)]
p = list(map(int,input().split()))


count = 0
for i in product([0,1], repeat=n):
    i = list(i)
    on = True
    for j in range(m):
        score = 0
        for k in s[j]:
            if i[k] == 1:
                score += 1
        if score % 2 == p[j]:
            continue

        else:
            on = False
            break

    if on:
        count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
L = [[] for _ in range(M)]
for i in range(M):
  L[i] = list(map(int,input().split()))
  L[i].remove(L[i][0])
P = list(map(int,input().split()))
Cand = []
for i in range(2**N):
  res = []
  for j in range(N):
    if ((i>>j) & 1):
      res.append(1)
    else:
      res.append(0)
  Cand.append(res) 
res = 0
for i in range(2**N):
    key = 0
    loop = 0
    for j in range(M):
        loop = 1
        if P[j] == 0:
            Even_counter = 0
            for el in L[j]:
                if Cand[i][el-1] == 1:
                    Even_counter += 1
            if Even_counter % 2 != 1:
                key = 1
                break
        if P[j] == 1:
            Od_counter = 0
            for el in L[j]:
                if Cand[i][el-1] == 1:
                    Od_counter += 1
            if Od_counter % 2 != 1:
                key = 1
                break           
        if key == 0 and j == M-1 and loop == 1:
            res += 1    
print(res)

Submission status: Wrong Answer

Solution code:
def resolve():
    N, M = map(int, input().split())
    S = [tuple(map(int, input().split()))[1:] for _ in range(M)]
    P = tuple(map(int, input().split()))
    ans = 0

    for c in range(2**N):
        flg_list = [False]*M
        for i, s_l in enumerate(S):
            cnt = 0
            for s in s_l:
                if c & (s-1 << 1):
                    cnt += 1

            if cnt % 2 == P[i]:
                flg_list[i] = True

        if all(flg_list):
            ans += 1

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    N, M = map(int, input().split())
    S = [tuple(map(int, input().split()))[1:] for _ in range(M)]
    P = tuple(map(int, input().split()))
    ans = 0

    for c in range(2**N):
        flg_list = [False]*M
        for i, s_l in enumerate(S):
            cnt = 0
            for s in s_l:
                if c & (s-1):
                    cnt += 1

            if cnt % 2 == P[i]:
                flg_list[i] = True

        if all(flg_list):
            ans += 1

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
f=lambda:map(int,input().split())
n,m=f()
ll=[]
for _ in range(m):
  k,*s=f()
  l=[0]*n
  for s in range(k): l[s-1]=1
  ll+=[l]
p=list(f())
import itertools as it
print(sum(all(sum(ll[i][j]*t[j] for j in range(n))%2==p[i] for i in range(m)) for t in it.product([0,1],repeat=n)))

Submission status: Wrong Answer

Solution code:
from sys import stdin

N, M = map(int, stdin.readline().split())
light = [None] * M
for i in range(M):
    light[i] = list(map(int, stdin.readline().split()))[1:]
P = list(map(int, stdin.readline().split()))

ans = 0
for i in range(1, 2 ** N + 1):
    on_switch = [0] * N
    for j in range(N):
        if int(format(i, 'b').zfill(N)[j]) == 1:
            on_switch[j] = 1

    on_bulb = 0
    for j in range(M):
        num_of_on_switch = 0
        for index in light[j]:
            num_of_on_switch += on_switch[index - 1]
        if num_of_on_switch % 2 == P[j]:
            on_bulb += 1
    if on_bulb == M:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

sw = list(product([True, False], repeat=N))
ans = 0
for pat in sw:
  cnt = 0
  flag = True
  for i in range(1, M+1):
    for j in range(ks[i-1][0]):
      if pat[ks[i-1][j+1]-1]:
        cnt += 1
    if cnt % 2 != p[i-1]:
      flag = False
      break
  if flag:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

switch = [False] * n

def valid():
  for i, indices in enumerate(s):
    if sum((switch[index-1] for index in indices)) % 2 != p[i]:
      return False
  return True

cnt = 0
def dfs(start):
  global cnt
  for i in range(start, n):
    if not switch[i]:
      switch[i] = True
      if valid():
        cnt += 1  
      dfs(i+1)
      switch[i] = False
      # dfs(i+1)
      
dfs(0)
print(cnt)

Submission status: Wrong Answer

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

P = list(map(int, input().split()))[::-1]
ans = 0

for i in range(2 ** N):
    on = []
    for j in range(N):
        if i >> j & 1 == 1:
            on.append(N - j)
    for i in range(M):
        if len(set(on) & set(S[i])) % 2 != P[i]:
            break
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def ma():
  n,m=map(int,input().split())
  ans=0
  e=[set(list(map(int,input().split()))[1:]) for i in range(m)]
  f=list(map(int,input().split()))
  for i in range(2**n):
    l={a for a,b in zip(range(1,n+1),bin(i)[2:].zfill(n)) if b=="1"}
    if sum(int(len(e[j-1]&l)%2!=f[j-1])for j in range(1,m+1)):break
    else:ans+=1
  print(ans)

if __name__=="__main__":
  ma()

Submission status: Wrong Answer

Solution code:
L = []
S = []
N, M = map(int, input().split())
cnt = 0
ans = 0
for i in range(M):
    l = list(map(int, input().split()))
    L.append(l)
p = list(map(int, input().split()))

for j in range(2**N):
    switch = [0]*N
    for k in range(N):
        if (j >> k) & 1:
            switch[k-1]=1
    S.append(switch)
    #ここまでで全パターン
#あるパターンにおいて全点灯しているか？
print(S)

for i in range(2**N):
    I = [0]*M
    cnt = 0
    for k in range(M):
        for x in range(1, len(L[k])):
            if S[i][L[k][x]-1]==1:
                I[k]+=1
    for i in range(M):
        if I[i]%2==p[i]:
            cnt +=1
    if cnt == M:
        ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
l=[]
for i in range(M):
    L = list(map(int, input().split()))
    l.append(l[1:]) 
s=list(map(int, input().split()))
c=0
for i in range(2**N):
    d =True
    for j in range(M):
        a = 0
        for k in range(N):
            if ((i >>k)&1 == 1) and (k+1 in l[j]):
                a += 1
        if a%2 == s[j]:
            continue
        else:
            d = False
            break
    if d is True:
        c += 1
print(c)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ks = [list(map(int, input().split()))for i in range(M)]
p = list(map(int, input().split()))
cnt = 0
all_on = 1
ans = 0
for i in range(2**N):
    all_on = 1
    bits = "0" + str(N) + "b" 
    sw_line = str(format(i,bits))
    for j in range(M):
        for k in range(1,ks[j][0]+1):
            sw = sw_line[ks[j][k]-1]
            if(sw== "1"):
                cnt += 1
        if(cnt % 2 != p[j]):
            all_on = 0
    if(all_on == 1):
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = [int(i) for i in input().split()] #Nがスイッチの数、Mは電球の数
sss = []
for i in range(M):
    buff = [int(i) for i in input().split()]
    onoff = 0
    for b in buff:
        onoff += 1<<(b-1)
    sss.append(onoff)

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

ct=0
for i in range(1<<N):
    for s,p in zip(sss,ppp):
        if bin(i&s).count("1")%2!=p:
            break
    else:
        ct+=1

print(ct)

Submission status: Wrong Answer

Solution code:
N,M = [int(i) for i in input().split()] #Nがスイッチの数、Mは電球の数
sss = []
for i in range(M):
    buff = [int(i) for i in input().split()]
    onoff = 0
    for b in buff:
        onoff += 1<<(b-1)
    sss.append(onoff)

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

ct=0
for i in range(1<<N):
    for s,p in zip(sss,ppp):
        if sum([int(i)  for i in list(bin(i&s)[2:])])%2!=p:
            break
    else:
        ct+=1

print(ct)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
s = []
k = []

for _ in range(M):
    tmp = list(map(int, input().split()))
    k.append(tmp.pop(0))
    s.append(tmp)
p = list(map(int, input().split()))
counter = 0

for bit in range(1 << N):
    tmp = 0
    hantei = True
    for n1, j in enumerate(s):
        for i in j:
            if(bit & (1 << (i-1))):
                tmp += 1
        if(tmp % 2 != p[n1]):
            hantei = False
    if(hantei == True):
        counter += 1

print(counter)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = list(map(int, input().split()))
Switches = np.zeros((N,M)) # N = Switch, M = light

for i in range(M):
    arr = list(map(int, input().split()))
    for item in arr[1:]:
        Switches[item-1, i] = 1
Ps = np.array(list(map(int, input().split())))

bit_max = 2 ** N
stat = np.zeros(M)
cnt = 1 if (stat == Ps).all() else 0

for i in range(1, bit_max):
    bits = [j for j in range(M) if (i >> j &1)]
    res = stat + Switches[bits].sum(axis=0) % 2
    cnt += 1 if (res == Ps).all() else 0

print(cnt)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc128/tasks/abc128_c
from itertools import product
N, M = map(int, input().split())
k = []
s = []
for _ in range(M):
    std_in = list(map(int, input().split()))
    k.append(std_in[0])
    # for i in range(std_in[0]):
    #     std_in[i+1] -= 1
    s.append(std_in[1:])
p = [int(i) for i in input().split()]

switches = [0] * N

# def judge_bulbs(switches):
#     for i in range(M):

#         k_sum = 0
#         for ki in range(k[i]):
#             k_sum += switches[ki]

#         if k_sum % 2 == p[i]:
#             continue
#         else:
#             return False
#     return True

# def solve(idx, switches):
#     if idx == N:
#         if judge_bulbs(switches):
#             return 1
#         else:
#             return 0

#     ans = 0
#     switches = switches.copy()
    
#     ans += solve(idx+1, switches)

#     switches[idx] = 1
#     ans += solve(idx+1, switches)
#     return ans

# print(solve(0, switches))

ans = 0

for x in product([0, 1], repeat=N):
    for i in range(M):
        cnt = 0
        for n in s[i]:
            if x[n-1] == 1:
                cnt += 1
        if cnt % 2 != 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc128/tasks/abc128_c
from itertools import product
N, M = map(int, input().split())
k = []
s = []
for _ in range(M):
    std_in = list(map(int, input().split()))
    k.append(std_in[0])
    for i in range(std_in[0]):
        std_in[i+1] -= 1
    s.append(std_in[1:])
p = [int(i) for i in input().split()]

switches = [0] * N

# def judge_bulbs(switches):
#     for i in range(M):

#         k_sum = 0
#         for ki in range(k[i]):
#             k_sum += switches[ki]

#         if k_sum % 2 == p[i]:
#             continue
#         else:
#             return False
#     return True

# def solve(idx, switches):
#     if idx == N:
#         if judge_bulbs(switches):
#             return 1
#         else:
#             return 0

#     ans = 0
#     switches = switches.copy()
    
#     ans += solve(idx+1, switches)

#     switches[idx] = 1
#     ans += solve(idx+1, switches)
#     return ans

# print(solve(0, switches))

ans = 0

for x in product([0, 1], repeat=N):
    for i in range(M):
        cnt = 0
        for n in s[i]:
            if x[n] == 1:
                cnt += 1
        if cnt % 2 != 0:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc128/tasks/abc128_c

N, M = map(int, input().split())
k = []
s = []
for _ in range(M):
    std_in = list(map(int, input().split()))
    k.append(std_in[0])
    for i in range(std_in[0]):
        std_in[i+1] -= 1
    s.append(std_in[1:])
p = [int(i) for i in input().split()]

switches = [0] * N

def judge_bulbs(switches):
    for i in range(M):

        k_sum = 0
        for ki in range(k[i]):
            k_sum += switches[ki]

        if k_sum % 2 == p[i]:
            continue
        else:
            return False
    return True

def solve(idx, switches):
    if idx == N:
        if judge_bulbs(switches):
            return 1
        else:
            return 0

    ans = 0
    switches = switches.copy()
    
    ans += solve(idx+1, switches)

    switches[idx] = 1
    ans += solve(idx+1, switches)
    return ans

print(solve(0, switches))

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M= list(map(int, input().split()))
K = []
S=[]
state_S = np.zeros(N)
for m  in range(M):
    _input = list(map(int, input().split()))
    K.append(_input[0])
    S.append(np.array(_input[1:]))
P = list(map(int, input().split()))
ans=0
for i in range(N ** 2):
    pattern= np.array([i >> bit & 1 for bit in range(N)])
    if all(np.sum(pattern[S[j] -1 ]) % 2 == P[j] for j in range(M)):
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M= list(map(int, input().split()))
K = []
S=[]
state_S = np.zeros(N)
for m  in range(M):
    _input = list(map(int, input().split()))
    K.append(_input[0])
    S.append(np.array(_input[1:]))
P = list(map(int, input().split()))
ans=0
for i in range(N ** 2):
    pattern= np.array([i >> bit & 1 for bit in range(N)])
    if all(np.sum(pattern[K[j] -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())
k=[0]*m
s=[set() for i in range(m)]
for i in range(m):
  k[i],*t=map(int,input().split())
  for j in range(k[i]):
    s[i].add(t[j])
ans=0
p=list(map(int,input().split()))
for i in range(2**n):
  switch=[0]*n
  flag=True
  for j in range(n):
    if i>>j&1:
      switch[j]=1
  for j in range(m):
    on_cnt=0
    for k in range(n):
      if switch[k]==1 and k in s[j]:
        on_cnt+=1
    if on_cnt%2!=p[j]:
      flag=False
      break
  if flag:
    ans+=1
print(ans)

Submission status: Wrong Answer

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

cnt=0
for i in range(2**n):
    # output=[False]*n
    flag=True
    for k in range(len(sl)):
        count=0
        for j in range(len(sl[k])):
            if((i>>j)&1):
                count+=1
        if count%2!=p[k]:
            flag=False
            break
    if flag:
        cnt+=1

print(cnt)

Submission status: Wrong Answer

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

ans = 0
for i in range(1 << n):
    check = []
    for j in range(n):
        if i >> j & 1:
            check.append(j)

    check = set(check)

    flag = True
    for j in range(m):
        tmp = 0
        for k in range(1, s[j][0]):
            if s[j][k] in check:
                tmp += 1

        if tmp % 2 != p[j]:
            flag = False
            break

    if flag == True:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
switch_state = [None] * N
which_switch = []

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

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

cnt = 0
for i in range(1<<N):
    flag = 0
    for j in range(M):
        check = 0
        for el in which_switch[j]:
            check += (1<<(el-1))
            if str(bin(i & check)).count('1') % 2 != p[j]:
                flag = 1
                break
        if flag == 1:
            break
        cnt += 1
        
print(cnt)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int,input().split())
    k = [None] * M
    s = [None] * M
    for i in range(M):
        k[i], *s[i] = map(int, input().split())
    p = list(map(int, input().split()))

    # スイッチのONOFFパターンをbit全探索
    ans = 0
    for i in range(1, 2**N):

        # ONOFFリスト取得
        switchs = [False for _ in range(N)]
        for j in range(N):
            if (i>>j) & 1:
                switchs[j] = True
        # print(bin(i))
        # print(switchs)

        # 各電球が点灯しているか判定
        ok = True
        for si,pi in zip(s,p):
            # print(si)
            # print(pi)
            # ONの個数
            on_count = len([v for v in [switchs[sij-1] for sij in si] if v])
            # 消灯していた場合
            if on_count % 2 != pi:
                ok = False
                break
        if ok:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int,input().split())
    k = [None] * M
    s = [None] * M
    for i in range(M):
        k[i], *s[i] = map(int, input().split())
    p = list(map(int, input().split()))

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

if __name__ == "__main__":
    main()