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())
ks = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))


res = 0
for i in range(2**n):
    on = [0 for _ in range(n)]
    for j in range(n):
        if((i>>j)&1):
            on[j]=1
    all_on = True 
    for j in range(m):
        on_num = 0 
        for s in ks[j][1: ]:
            if(on[s-1]): on_num += 1 

        if(on_num%2 != p[j]):
            break 

    if(all_on): res += 1
print(res)

Submission status: Wrong Answer

Solution code:
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(2**n):
#  bit=format(i,'011b')
#  bit=list(reversed(format(i,'b')))
  bit=bin(i)
  print(bit)
  #ある電球
  num=0
  for j in range(m):
    #ある電球に接続されている各スイッチ
    cnt=0
    for k in range(1,l[j][0]+1):
#      print(l[j][k])
#      if bit[l[j][k]]==1:
#      if (i>>k)&1:
#      print(i,l[j][k])
      if (i>>l[j][k]-1)&1:
        cnt+=1
    print(i,j,cnt)
    if cnt%2==p[j]:
      num+=1
  if num==m:
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

N, M = map(int,input().split())
k = []
for i in range(M):
    k.append(list(map(int,input().split())))
p = list(map(int,input().split()))
ks = [i[0] for i in k]
ss = [i[1:] for i in k]

max_s = max([max(s) for s in ss])
prods = list(itertools.product([0, 1], repeat=max_s))
count = 0
for prod in prods:
  check = 0
  for i in range(len(ss)):
    s = ss[i]
    # sごとに
    n = sum([prod[j-1] for j in s])
    if n % 2 == p[i]:
      check += 1
  if check == M:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from itertools import product
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M = map(int, readline().split())
    S = [[int(i) for i in readline().split()] for _ in range(M)]
    P = [int(i) for i in readline().split()]

    ans = 0
    A = [[0, 1] for _ in range(N)]
    for pattern in product(*A):
        on = []
        for s in S:
            tmp = 0
            for i in range(s[0]):
                tmp += pattern[i]
            on.append(tmp % 2)

        if on == P:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def switches(N, M, array, P):
    count = 0
    for i in range(0,2**N):
        flag = 0
        for j in range(M):
            sum = 0
            for k in range(1,array[j][0]+1):
                if format(i, '0'+str(N)+'b')[array[j][k]-1] == '1':
                    sum += 1
            
            if sum%2 == P[j] and flag == 0:
                flag += 1
            elif sum%2 == P[j] and flag == 1:
                flag += 1
            
        if flag == M:
            count += 1

    return count


if __name__ == "__main__":
    N,M = map(int, input().split())
    array = []
    for i in range(M):
        array.append(list(map(int, input().strip().split())))
    P = list(map(int, input().strip().split()))
    print(switches(N,M,array,P))

Submission status: Wrong Answer

Solution code:
def switches(M, array, P):
    count = 0
    for i in range(0,2**N):
        flag = 0
        for j in range(M):
            sum = 0
            for k in range(1,array[j][0]+1):
                if format(i, '0'+str(N)+'b')[array[j][k]-1] == '1':
                    sum += 1
            
            if sum%2 == P[j] and flag == 0:
                flag += 1
            elif sum%2 == P[j] and flag == 1:
                flag += 1
            
        if flag == M:
            count += 1

    return count


if __name__ == "__main__":
    N,M = map(int, input().split())
    array = []
    for i in range(M):
        array.append(list(map(int, input().strip().split())))
    P = list(map(int, input().strip().split()))
    print(switches(M,array,P))

Submission status: Wrong Answer

Solution code:
def switches(M, array, P):
    count = 0
    for i in range(0,2**N):
        flag = 0
        for j in range(M):
            sum = 0
            for k in range(1,array[j][0]+1):
                if format(i, '0'+str(N)+'b')[array[j][k]-1] == '1':
                    sum += 1
            
            if sum%2 == P[j] and flag == 0:
                flag += 1
            elif sum%2 == P[j] and flag == 1:
                flag += 1
            
        if flag >= M:
            count += 1

    return count


if __name__ == "__main__":
    N,M = map(int, input().split())
    array = []
    for i in range(M):
        array.append(list(map(int, input().strip().split())))
    P = list(map(int, input().strip().split()))
    print(switches(M,array,P))

Submission status: Wrong Answer

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,m = readInts()
    # 各電球 i について、 si1, si2, ..., sik のうち、 onのスイッチが何個かを数える
    # それが偶数か奇数かによって、電球 i が付いているかどうかが分かる
    A = []
    for i in range(m):
        A.append(list(map(lambda x: int(x) - 1, input().split()))[1:])
    P = readInts()
    ans = 0

    for bit in range(1 << n):
        ok = True
        for i in range(m):
            con = 0
            for v in A[i]:
                print(v)
                if bit & 1 << v:
                    con += 1
            if con % 2 != P[i]:
                ok = False
        if ok:
            ans += 1
    print(ans)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

for i in range(2 ** N):
  sw = [0]*N
  for j in range(N):
    if ((i >> j) & 1):
      sw[j] = 1
  frg = True
  for j in range(M):
    a = ks[j][0]
    aa = 0
    for k in range(a):
      aa += sw[k]
    if aa%2 != p[j]:
      frg = False
  if frg:
    c += 1
    
print(c)

Submission status: Wrong Answer

Solution code:


N, M = map(int, input().split())
table = [[int(i) for i in input().split()] for _ in range(M)]
on_off = list(map(int, input().split()))
cnt = 0
ans_list = []

for i in range(M):
    switches = sum(table[i]) - table[i][0]
    sw_num = switches // 2
    sw_num_amari = switches % 2
    if on_off[i] == 0:
        ans_list.append(sw_num)
    else:
        ans_list.append(sw_num + sw_num_amari)

ans = 1
for i in ans_list:
    ans *= i

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
light = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    binstr = list(reversed(format(i, '010b')))
    lightnum = 0
    for j in range(m):
        cnt = 0
        for s in light[j]:
            if binstr[s-1] == '1':
                cnt += 1
        if p[j] == cnt%2:
            lightnum += 1
    if lightnum == m:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math

inputted = list(map(int, input().split()))
N = inputted[0]
K = inputted[1]

answer = N - K * math.floor(N / K)

print(answer)

Submission status: Wrong Answer

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

for b in range(1 << n):
    sw = [0] * n
    for i in range(n):
        if b & (1 << i): sw[i] = 1
    for i in range(m):
        c = 0
        for j in s[i]:
            if sw[j - 1] == 1: c += 1
        if c % 2 == p[i]: break
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

for i in range(M):
    input_text = list(map(int, input().split()))
    switches = input_text[1:]
    for switch in switches:
        all_switches[switch - 1].append(i - 1)


# 電球が光る条件(M個)
lightup_terms = list(map(int, input().split()))
# print(all_switches)
count = 0
for i in range(1 << N):
    lightup_counts = [0 for _ in range(M)]
    for j in range(N):
        # 組み合わせを一つずつ確認する
        if i >> j & 1:
            for light in all_switches[j]:
                lightup_counts[light] += 1
    # print(lightup_counts)
    compute_success = True
    for j, term in enumerate(lightup_terms):
        if lightup_counts[j] % 2 != term:
            compute_success = False
            break
    if compute_success:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,m = [int(i) for i in input().split()]
k = []
for i in range(m):
  array = [int(i) for i in input().split()]
  k.append(array)

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

for i in range(2**n):
  r = format(i,'b')
  r = r.zfill(n)[::-1]
  for j in range(m):
    for l in range(1,k[j][0]+1):
      chk += int(r[k[j][l]-1])
    if chk % 2 != p[j]:
      chk = 0
      break
    if j == m-1:
      #print(r,chk)
      ans += 1
      chk = 0
  
print(ans)

Submission status: Wrong Answer

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

#%%
cnt = 0
for bits in itertools.product([0, 1], repeat=n):
    # ライトの配列の初期化
    lights = [0] * m

    # 電球ごとのONになってるスイッチの数をカウント
    # スイッチのindexでループを回す
    for i in range(n):
        if bits[i] == 1: #スイッチがONのとき
            sw = i + 1 # スイッチの番号
            for j in range(len(ks)): # 全部のlight-switchの配線を確認
                if sw in ks[j][1:]: # 配線がつながってるとき
                    lights[j] += 1 # そのlightに1を加算

    # カウント終了後条件判別
    # 一つもスイッチがONになってないとライトが付きもしない
    # if 0 not in lights:
        # 2で割ったあまり
    m_lights = [l%2 for l in lights]
    print(m_lights)
    if m_lights == p:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n,m=MI()
sws=[]
for i in range(m):
    sws.append(list(map(int,input().split())))
#print(sws)
ps=LI()
ans=0
for i in range(2**n):
    count=0
    for j in range(m):
        sm=0
        for k in range(1,len(sws[j])):
            sm+= i>>(sws[j][k]-1) %2
        #print(sm)
        if sm%2==ps[j]:
            count+=1
    if count==m:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n,m=MI()
sws=[]
for i in range(m):
    sws.append(list(map(int,input().split())))
#print(sws)
ps=LI()
ans=0
for i in range(2**n):
    count=0
    for j in range(m):
        sm=0
        for k in range(1,len(sws[j])):
            sm+= i>>(sws[j][k]-1) %2
        #print(sm)
        if sm%2==ps[j-1]:
            count+=1
    if count==m:
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
KS = [[int(x) for x in input().split()] for _ in range(M)]
P = list(map(int, input().split()))
ans = 0
for i in range(2**N):
  switch_pattern = bin(i)[2:].zfill(N)
  succes = 1
  for j in range(M):
    switch_on = 0
    for k in KS[j]:
      if switch_pattern[k-1] == '1':
        switch_on += 1
    if switch_on % 2 != P[j]:
      succes = 0
      break
  if succes == 1:
      ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
KS = [[int(x) for x in input().split()] for _ in range(M)]
P = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    switch_pattern = bin(i)[2:].zfill(N)
    succes = 1
    for j in range(M):
      for k in KS[j]:
        switch_on = 0
        if switch_pattern[k-1] == '1':
          switch_on += 1
      if switch_on % 2 != P[j]:
            succes = 0
            break
    if succes == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N, M = iip(False)
    #A = [iip(False) for i in range(N)]

    A = []
    P = []
    for i in range(M):
        A.append(iip()[1:])

    for i, p in enumerate(iip()):
        P.append(p)

    pat = 0
    for i in range(2**N):
        for denkyuu in range(M):
            ns = 0
            sn = i
            for s in range(N):
                if s+1 in A[denkyuu]:
                    ns += sn % 2
                    #print("a", denkyuu, s+1)
                sn //= 2
            if ns % 2 != P[denkyuu]:
                pat -=1
                print(i, denkyuu, P[denkyuu], sn)
                break

        #print(i)
        pat += 1

    print(pat)

    #print(A)
    #print(P)






#####################################################ライブラリ集ここから

def YesNo(s):
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N, M = iip(False)
    #A = [iip(False) for i in range(N)]

    A = []
    P = []
    for i in range(M):
        A.append(iip()[1:])

    for i, p in enumerate(iip()):
        P.append(p)

    pat = 0
    for i in range(2**N):
        for denkyuu in range(M):
            ns = 0
            sn = i
            for s in range(N):
                if s+1 in A[denkyuu]:
                    ns += sn % 2
                    print("a", denkyuu, s+1)
                sn //= 2
            if ns % 2 != P[denkyuu]:
                pat -=1
                print(i, denkyuu, P[denkyuu], sn)
                break

        #print(i)
        pat += 1

    print(pat)

    #print(A)
    #print(P)






#####################################################ライブラリ集ここから

def YesNo(s):
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N, M = iip(False)
    #A = [iip(False) for i in range(N)]

    A = []
    P = []
    for i in range(M):
        A.append(iip()[1:])

    for i, p in enumerate(iip()):
        P.append(p)

    pat = 0
    for i in range(2**N):
        for denkyuu in range(M):
            ns = 0
            sn = i
            for s in range(N):
                if s+1 in A[denkyuu]:
                    ns += sn % 2
                    print("a", denkyuu, s+1)
                sn //= 2
            if ns % 2 != P[denkyuu]:
                pat -=1
                print(i, denkyuu, P[denkyuu], sn)
                break

        #print(i)
        pat += 1

    #print(pat)

    #print(A)
    print(P)






#####################################################ライブラリ集ここから

def YesNo(s):
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

def iip(listed=True):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def iip_ord():
    return [ord(i) - ord("a") for i in input()]


def main():
    ans = solve()
    if ans is not None:
        print(ans)

def solve():
    N, M = iip(False)
    #A = [iip(False) for i in range(N)]

    A = []
    P = []
    for i in range(M):
        A.append(iip()[1:])

    for i, p in enumerate(iip()):
        P.append(p)

    pat = 0
    for i in range(2**(N-1)):
        sn = i

        for denkyuu in range(M):
            ns = 0
            for s in range(N):
                if s+1 in A[denkyuu]:
                    ns += sn % 2
                sn //= 2
            if ns % 2 != P[denkyuu]:
                pat -=1
                break
        #print(i)
        pat += 1

    print(pat)

    #print(A)
    #print(P)






#####################################################ライブラリ集ここから

def YesNo(s):
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):
    for i in s:
        print(i)

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import time
import itertools
from heapq import heappush, heappop
import heapq
import numpy as np
import random
from collections import deque
from collections import defaultdict
from decimal import *
import bisect
import math
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, input().split())
KS = [[int(x) for x in input().split()] for _ in range(M)]
P = list(map(int, input().split()))

bit = (1 << N) - 1
cnt = 0

for i in range(bit):
    switch = [0] * N
    for j in range(N):
        isOn = (i >> j) & 1
        switch[j] = isOn

    ok = True
    for k in range(M):
        t = KS[k][1:]
        c = 0
        for l in t:
            c += switch[l - 1]

        if c % 2 != P[k - 1]:
            ok = False
            break

    if ok:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

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

bit = (2 << N) - 1
cnt = 0

for i in range(bit):
  switch = [0] * N
  for j in range(N):
    isOn = (i >> j) & 1
    switch[j] = isOn

  ok = True
  for k in range(M):
    t = KS[k][1:]
    for l in t:
      if not isOn:
        ok = False
        break
    if not ok:
      break

  if ok:
    cnt += 1
    
print(cnt)

Submission status: Wrong Answer

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

on = list(map(int,input().split()))
  
n = N
anscnt = 0
arr = [0 for i in range(N+1)]

for i in range(2 ** n):
  arr = [0 for i in range(N+1)]
  for j in range(n):  # このループが一番のポイント
    if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
      arr[j+1] = 1
  ok = 1

  for k in range(M):
    a = List[k][0]
    cnt = 0
    for l in range(1,a+1):
      if arr[ List[k][l] ] == 1:
        cnt += 1
    if cnt%2 == on[k]:
      ok = 1
    else:
      ok = 0
  if ok == 1:
    anscnt += 1
      
print(int(anscnt/2))

Submission status: Wrong Answer

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

ans = 0
for bits in range(2 ** n):
    ons = set()
    b = bits
    for shift in range(10):
        b = b >> shift
        if b & 1 > 0:
            ons.add(shift + 1)

    ok = True
    for i in range(m):
        c = [s in ons for s in ss[i]].count(True)
        if c % 2 != ps[i]:
            ok = False
            break
    if ok:
        ans += 1

print(ans)