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:
def i_input(): return int(input())


def i_map(): return map(int, input().split())


def i_list(): return list(i_map())


def i_row_list(n): return [i_list() for _ in range(n)]


def bit_search(n):
    bit_ans = []
    for i in range(2 ** n):
        temp = []
        for j in range(n):
            if ((i >> j) & 1):
                temp.append(1)
            else:
                temp.append(0)
        bit_ans.append(temp)
    return bit_ans


def light_check(switchpattern, lightswitches, onstat):
    cnt = 0
    for i in range(len(switchpattern)):
        if switchpattern[i] == 1 and lightswitches[i] == 1:
            cnt += 1
    if cnt % 2 == onstat:
        return 1
    else:
        return 0


n, m = i_map()
kkk = i_row_list(m)
onstates = i_list()
kkk_row = []
for i in range(m):
    tmp = [0] * n
    for j in kkk[i]:
        if j != 0:
            tmp[j - 1] = 1
    kkk_row.append(tmp)

switchpatterns = bit_search(n)
ans = 0
for switchpattern in switchpatterns:
    cnt = 0
    for i in range(m):
        cnt += light_check(switchpattern, kkk_row[i], onstates[i])
    if cnt == m:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def i_input(): return int(input())


def i_map(): return map(int, input().split())


def i_list(): return list(i_map())


def i_row_list(n): return [i_list() for _ in range(n)]


def bit_search(n):
    bit_ans = []
    for i in range(2 ** n):
        temp = []
        for j in range(n):
            if ((i >> j) & 1):
                temp.append(1)
            else:
                temp.append(0)
        bit_ans.append(temp)
    return bit_ans


def light_check(switchpattern, lightswitches, onstat):
    cnt = 0
    for i in range(len(switchpattern)):
        if switchpattern[i] == 1 and lightswitches[i] == 1:
            cnt += 1
    if cnt % 2 == onstat:
        return 1
    else:
        return 0


n, m = i_map()
kkk = i_row_list(m)
onstates = i_list()
kkk_row = []
for i in range(m):
    tmp = [0] * n
    for j in range(len(kkk[i])):
        if j != 0:
            tmp[j - 1] = 1
    kkk_row.append(tmp)

switchpatterns = bit_search(n)
ans = 0
for switchpattern in switchpatterns:
    cnt = 0
    for i in range(m):
        cnt += light_check(switchpattern, kkk_row[i], onstates[i])
    if cnt == m:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:

def i_input(): return int(input())


def i_map(): return map(int, input().split())


def i_list(): return list(i_map())


def i_row_list(N): return [i_list() for _ in range(N)]


def bit_search(n):

    bit_ans=[]
    for i in range(2 ** n):
        tmp=[]
        for j in range(n):
            if ((i >> j) & 1):
                tmp.append(1)
            else:
                tmp.append(0)
        bit_ans.append(tmp)
    return bit_ans

def light_check(switchpattern, lightswitches, onstat):
    cnt=0
    for i in range(len(switchpattern)):
        if switchpattern[i]==1 and lightswitches[i]==1:
            cnt+=1
    if cnt%2==onstat:
        return 1
    else:
        return 0



n,m = i_map()
kkk = i_row_list(m)
onstates=i_list()
kkk_row=[]
for i in range(m):
    tmp=[0]*n
    for j in range(len(kkk[i])):
        if j!=0:
            tmp[j-1]=1
    kkk_row.append(tmp)

switchpatterns=bit_search(n)
ans=0
for switchpattern in switchpatterns:
    cnt=0
    for i in range(len(kkk_row)):
        cnt+=light_check(switchpattern,kkk_row[i],onstates[i])
    if cnt==len(kkk_row):
        ans+=1

print(ans)

Submission status: Wrong Answer

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

ki = [ None ] * m
pi = [ None ] * m
smi = [ None ] * m

for _ in range(m):
    k, *si = map(int, input().split())

    if k == 0:
        while True:
            pass

    else:
        exit()

Submission status: Wrong Answer

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key
from bisect import bisect_left


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

def bindex(a,x):
    i = bisect_left(a,x)
    if i != len(a) and a[i] == x:
        return i
    return None


class UnionFind:
    def __init__(self, n):
        self.r = [-1]*(n+1)

    def root(self, x):
        if self.r[x] < 0:
            return x
        self.r[x] = self.root(self.r[x])
        return self.r[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.r[x] > self.r[y]:
            x,y = y,x
        self.r[x] += self.r[y]
        self.r[y] = x
        return True

    def size(self, x):
        return -1 * self.r[self.root(x)]


class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N, M = mulinputs()
    ks, ss, ps = [], [], []
    for _ in range(M):
        k, *s = list(mulinputs())
        ks.append(k)
        ss.append(s)
    ps = list(mulinputs())

    cnt = 0
    for n in range((1<<N)+1):
        state = [0] * N
        for j in range(N):
            state[j] = (n&(1<<j))>>j
        is_light = True
        for j in range(M):
            icnt = 0
            for s in ss[j]:
                icnt += state[s-1]
            if icnt%2 != ps[j]:
                is_light = False
                break
        if is_light:
            cnt+=1

    # 出力
    print(cnt)

Submission status: Wrong Answer

Solution code:
def light(l,i):
    k=1<<i
    if l&k:
        return 1
    else:
        return 0

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

a=0
for l in range(0,1<<N):
    b=0
    for j in range(0,M):
        c=0
        for i in range(1,s[j][0]+1):
            c+=light(l,s[j][i])
        if c%2==p[j]:
            b+=1
    if b==M:
        a+=1
print(a)

Submission status: Wrong Answer

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

ans = 0
for i in range(2**n):
    bnt = 0
    for j in range(m):
        cnt = 0
        for l in range(1, len(ks[j])):
            if (i>>(l-1))&1 == 1:
                cnt += 1
        if cnt%2 == p[j]:
            bnt += 1
    if bnt == m:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#m = int(input())
n, m = map(int, input().split())
#al = list(map(int, input().split()))
#al=[list(input()) for i in range(n)]
switch = []
kl = []
for i in range(m):
    temp = list(map(int, input().split()))
    kl.append(temp[0])
    switch.append(temp[1:])
pl = list(map(int, input().split()))
# print(switch)

pattern = [[0 for _ in range(n)] for _1 in range(2**n)]
for i in range(2**n):
    for j in range(n):
        if ((i >> j) & 1):  # 二進数iの下から数えてj桁目が1か否か
            pattern[i][j] = 1

ans = 0
for spt in pattern:
    islit = True
    count = 0
    for lightnum in range(m):
        for s in switch[lightnum]:
            if spt[s-1] == 1:
                count += 1
        if count % 2 != pl[lightnum]:
            islit = False
            break
    if islit:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

ans=0
for i in range(1,1<<n):
  on=0
  for j in range(m):
    cnt=0
    for k in range(ks[j][0]):
      if 1<<(ks[j][k+1]-1) & i:
        cnt+=1
    if cnt%2==p[j]:
      on+=1
    if on==m:
      ans+=1
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(2**n):
    light = 0
    for ki, j in enumerate(k):
        switch = 0
        for s in j[1:]:
            if i & (1 << s):
                switch += 1
        if switch % 2 == p[ki]:
            light += 1
    if light == m:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(2**n):
    light = 0
    for ki, j in enumerate(k):
        switch = 0
        for s in j[1:]:
            if i & s == s:
                switch += 1
        if switch % 2 == p[ki]:
            light += 1
    if light == m:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(2**n):
    s = 0
    for ki, j in enumerate(k):
        count = 0
        for t in j[1:]:
            if i & t == t:
                count += 1
        if count % 2 == p[ki]:
            s += 1
    if s == m:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(2**n):
    s = 0
    for ki, j in enumerate(k):
        count = 0
        for t in j[1:]:
            if i & t == t:
                count += 1
        if count % 2 != p[ki]:
            s += 1
    if s == m:
        ans +=1 
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(2**n):
    for ki, j in enumerate(k):
        target = j[1:]
        count = 0
        for t in target:
            if i & t == t:
                count += 1
        if count % 2 != p[ki]:
            break
    else:
        ans += 1
print(ans)

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


ans = 0
for i in range(2**n):
    s = 0
    for j in range(m):
        c = 0
        for k in range(len(ks[j])-1) :
            if ((i >> (ks[j][k+1]-1)) & 1) :
                c += 1
        if c != 0 and c % 2 == p[j]:
            s += 1
    if s == m :
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
def f(i):
    if i == n:
        on = [0] * m
        for j in range(m):
            for k in range(1, s[j][0] + 1):
                if t[k - 1]:
                    on[j] += 1
        for j in range(m):
            if not on[j] % 2 == p[j]:
                return
        global ans
        ans += 1
        return
    t[i] = 1
    f(i + 1)
    t[i] = 0
    f(i + 1)
    return

n, m = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
t = [0] * n
f(0)
print(ans)

Submission status: Wrong Answer

Solution code:
def abc128_c():
    # n個のスイッチ、m個の電球
    N, M = map(int, input().split())

    connected_switches = []
    for i in range(M):
        # [k, s1, s2, ...sn][1:]
        tmp = list(map(int, input().split()))[1:]
        connected_switches.append(tmp)

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

    ans = 0

    # スイッチの状態(ON/OFF)をすべて列挙してすべての電球がついている場合はカウントする
    for i in range(2 ** N):
        # 各電球が点灯しているかをチェックする
        for j in range(M):
            on_lamp_count = 0
            on_switch_count = 0
            # スイッチがつながっていて、かつ、onになっているものをカウント
            for k in range(N):
                # connected_switches[j]には[s1, s2, ...]が入っているため+1が必要
                if k + 1 in connected_switches[j] and ((i >> k) & 1):
                    on_switch_count += 1

            # 電灯をチェックして一つでもついていないものがあればそのスイッチの状態ではすべての電灯が付くという条件を満たせない
            if on_switch_count % 2 != p[j]:
                break
            else:
                on_lamp_count += 1

        if on_lamp_count == p[j]:
            ans += 1

    print(ans)

if __name__ == '__main__':
    abc128_c()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]
p = list(map(int, input().split()))
ans=0
for i in range(N**2):
    a=[]
    flag=0
    for j in range(N):
        if (i>>j)&1:
            a.append(j+1)
    for k in range(M):
        cnt=0
        for l in A[k][1:]:
            if l in a:
                cnt+=1
        if cnt%2!=p[k]:
            flag=1
    if flag==0:
        ans+=1
    
print(ans)

Submission status: Wrong Answer

Solution code:
# cs: c nnected switches
n, m = map(int, input().split())

def get_switch_number():
    # k s1 s2 s3 .. sn 
    # k is not use.
    sn = 0
    for s in list(map(int, input().split()))[1:]:
        sn |= (1<<(s-1))
    return sn
    
cs = [get_switch_number() for _ in range(m)]
# print(f'cs: {cs}')
ps = list(map(int, input().split()))
# print(f'ps: {ps}')

# bit全探索(0: すべてoffは不要)
ans = 0
# on: 0:消えてる、1:点いてる
# 10: 1 2  3   4 
# 0b: 1 10 11, 100..
for on in range(1, 1<<n):
    # print(f'on: {on}')
    all_on = True
    i = 0
    # on と cs(conected_switch) の全パターンをチェック
    for s in cs:
        # print(f's: {s}')
        # bin: バイナリ文字列に変換
        # 3 -> '0b11'
        # list で 1 or 0 の配列を作成 ['1', '1']
        ct = len([n for n in list(bin(on&s)[2:]) if n == '1'])
        if (ct == 0) or (ct%2 != ps[i]):
            all_on = False
            break
        i += 1
    if all_on:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
lights=[]
for _ in range(M):
    number=list(map(int,input().split()))
    lights.append(number[1:])
p=list(map(int,input().split()))
switches=[n for n in range(1,N+1)]
kouho=[]
n=len(switches)
for i in range(2**n):
    switch=[]
    for j in range(n):
        if ((i>>j)&1):
            switch.append(switches[j])
    kouho.append(switch)
del kouho[0]
ans=0
for kou in kouho:
    numbers=[0 for _ in range(M)]
    for k in kou:
        for n in range(M):
            if k in lights[n]:
                numbers[n]+=1
    for n in range(M):
        numbers[n]=numbers[n]%2
    if numbers==p:
        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()))

ans = 0
for bit in product([0, 1], repeat=n):
    for ksi, pi in zip(ks, p):
        cnt = sum(bit[pi - 1] for sij in ksi[1:])
        if cnt % 2 != pi:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
k_s = [list(map(int, input().split())) for i in range(M)]
p = list(map(int, input().split()))
ans=0
for i in range(2**N):
    for u in range(M):
        t=True
        num=0
        for y in range(1,len(k_s[u])):
            #print(bin(i),u,y-1,bin(i >> (y-1)))
            if ((i >> (y-1)) & 1):
                num+=1
        if not num%2==p[u]:
            t=False
        if not t :
            break
    else:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

ans = 0
for i in range(2 ** n):
    for j in range(m):
        cnt = 0
        for k in range(n):
            if i >> j & 1 and k + 1 in ks[j]:
                cnt += 1
        if cnt % 2 != p[j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
combiList = []
for i in range (M):
  combiList.append(list(map(int, input().split())))
kakuninList = list(map(int, input().split()))
statusList = [0]*M

for j in range (M):
  combiList[j].pop(0)
res = 0
# 010 なら2番目のみ派閥 
for bits in range(1,2**N): #k番目のグループ
  flag = True
  statusList = [0]*M
  for j in range(N):
    if((bits>>j) & 1): 
      for k in range(M):
        if j+1 in combiList[k]:
          statusList[k] +=1
  for k in range(M):
    if statusList[k] % 2 != kakuninList[k]:
      flag = False
      break
  if flag:
    res +=1
print(res)

Submission status: Wrong Answer

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

# input
n, m = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
k = [t[i][0] for i in range(m)]
s = [t[i][1:] for i in range(m)]

# calc
# bit full search
ans = 0 
for i in range(2**n):
    tmp = i 
    sw = []
    if i == 0:
        sw = [0] 
    while tmp > 0:
        sw.append(tmp&1)
        tmp = tmp>>1
    while len(sw) < n:
        sw.append(0)

    #print('sw =', sw)
    
    # check whether current sw satisfies the condision.
    ok = True
    # light bulb j
    for j in range(m):
        tmp = 0 
        for a in range(k[j]):
            tmp += sw[a-1]
        if tmp%2 != p[j]%2:
            ok = False
            break
    if ok: 
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    lights = [0]*m
    onoff = [0]*n
    cnt = 0
    for j in range(n):
        if (i >> j) &  1:
            onoff[j] = 1
    for k in range(m):
        for l in s[k][1:]:
            if onoff[l-1] == 1:
                cnt += 1
        if cnt % 2 == p[k]:
            lights[k] = 1
    if all(g == 1 for g in lights):
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def is_all_on(on_switches):
    all_on_cnt = 0
    for i in range(M):#電球の数
        cnt = 0
        for on in on_switches:
            if on in lights[i]: #i個目の電球と繋がってるスイッチの中にonになってるものがあるか
                cnt += 1
        if cnt % 2 == P[i]:        
            all_on_cnt += 1
    return True if all_on_cnt == M else False        
            
            

N,M = map(int,input().split())
lights = []
for m in range(M):
    lights.append(list(map(lambda x:int(x) - 1,input().split()))[1:])
P = list(map(int,input().split()))
#print(lights)

ans = 0
for i in range(1 << N): #スイッチon/offの全パターン数
    on_switches = []
    for j in range(M): #電球の数
        if ((i >> j) & 1) == 1: #１が立ってる電球がonの電球
            on_switches.append(j) #onになってる電球の位置
    #if len(on_switches) == 0: continue #1個も点灯してなければ次へ進む
    if is_all_on(on_switches): ans += 1 #全ての電球が点灯しているかをチェック
    #print(i,on_switches)    
print(ans)

Submission status: Wrong Answer

Solution code:
def is_all_on(on_switches):
    all_on_cnt = 0
    for i in range(M):#電球の数
        cnt = 0
        for on in on_switches:
            if on in lights[i]: #i個目の電球と繋がってるスイッチの中にonになってるものがあるか
                cnt += 1
        if cnt % 2 == P[i]:        
            all_on_cnt += 1
    return True if all_on_cnt == M else False        
            
            

N,M = map(int,input().split())
lights = []
for m in range(M):
    lights.append(list(map(lambda x:int(x) - 1,input().split()))[1:])
P = list(map(int,input().split()))
#print(lights)

ans = 0
for i in range(1 << N): #スイッチon/offの全パターン数
    on_switches = []
    for j in range(M): #電球の数
        if ((i >> j) & 1) == 1: #１が立ってる電球がonの電球
            on_switches.append(j) #onになってる電球の位置
    if len(on_switches) == 0: continue #1個も点灯してなければ次へ進む
    if is_all_on(on_switches): ans += 1 #全ての電球が点灯しているかをチェック
    #print(i,on_switches)    
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int,input().split())
s = list(list(map(int, input().split())) for _ in range(m)) 
p = list(map(int,input().split()))
ans = 0
for i in range(1<<n):             # 全switch(n)のon/offパターン数
    sw = [False]*m                # 各電球の点灯リストを作成
    for j in range(m):            # 各電球について
        cnt = 0
        for k in range(1,len(s[j])):   # 各電球のswitchについて
            if i>>s[j][k]&1:
                cnt += 1
        if cnt%2==p[j]:
            sw[j]=True
    if all(sw):
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = []
for _ in range(M):
    A.append(tuple(map(int, input().split())))
P = tuple(map(int, input().split()))
import itertools
def hantei(A, RETU, P):
    for i in range(len(A)):
        count = 0
        for k in RETU:
            if k in A[i][1:]:
                count += 1
        if not count % 2 == P[i]:
            return False
    return True
ans = 0
for i in range(1, N + 1):
    for k in itertools.combinations(range(1, N + 1), i):
        if hantei(A, k, P):
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
sys.setrecursionlimit(500*500)
import itertools
from collections import Counter,deque

def main():
    n,m = map(int, input().split())
    ans = 0
    S = []
    for i in range(m):
        s = list(map(int, input().split()))
        k = s.pop(0)
        S.append(s)
    p = list(map(int, input().split()))

    for i in range(1<<n):
        ok = True
        for j in range(m):
            cnt = 0
            for s in S[j]:
                if ((i>>s-1)&1): # スイッチが対象であれば
                    cnt += 1
            if cnt%2!=p[j]:
                od = False
        if ok:
            ans += 1
    print(ans)





if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools

def allCombination(n):
    switch = [i for i in range(1,n+1)] 
    slis = []
    for i in range(n):
        for pair in itertools.combinations(switch, i+1):
            slis.append(pair)
    return slis

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

slis = allCombination(n)
cnt = 0
for s in slis:
    flag = 1
    for i,eachs in enumerate(kS):
        same = set(eachs[1:]) & set(s)
        if len(same) % 2 != p[i]:
            flag = 0
    
    if flag:
        cnt += 1

print(cnt)

Submission status: Wrong Answer

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

klist = []
slist = [list() for _ in range(m)]

for i in range(m):
    k,*s = map(int,input().split())
    klist.append(k)
    slist[i] = s

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

ans = 0
for i in range(2**n):
    for j in range(m):
        cnt = 0
        for l in slist[j]:
            if (i >> (l-1))&1 ==1:
                cnt += 1
        if cnt%2 != p[j]:
            break
        else:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import itertools

[N,M] = input().split()
N = int(N)
M = int(M)
a =[]
p = []
list_bin = []

for j in range(M):
    list_temp = [int(s) for s in input().split()]
    list_temp.pop(0)
    for i in range(N):
        if i+1 in list_temp:
            list_bin.append(1)
        else:
            list_bin.append(0)

    a.append(list_bin)
    list_bin = []
p = [int(s) for s in input().split()]

arr_switch = np.array(a)
arr_p = np.array(p)
arr_pattern = np.array(list(itertools.product([0,1], repeat=N)))

count = 0
flag = 1
for switch in arr_pattern:
    for m in range(M):
        if (not (np.dot(switch, arr_switch[m]) % 2 == arr_p[m])) or  (np.dot(switch, np.ones(N)) == 0):
           flag = 0
    if flag == 1:
        count = count + 1
    flag=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import itertools

[N,M] = input().split()
N = int(N)
M = int(M)
a =[]
p = []
list_bin = []

for j in range(M):
    list_temp = [int(s) for s in input().split()]
    list_temp.pop(0)
    for i in range(N):
        if i+1 in list_temp:
            list_bin.append(1)
        else:
            list_bin.append(0)

    a.append(list_bin)
    list_bin = []
p = [int(s) for s in input().split()]

arr_switch = np.array(a)
arr_p = np.array(p)
arr_pattern = np.array(list(itertools.product([0,1], repeat=N)))

count = 0
flag = 1
for switch in arr_pattern:
    for m in range(M):
        if (not (np.dot(switch, arr_switch[m]) % 2 == arr_p[m])) or  (np.dot(switch, np.ones(N)) == 3):
           flag = 0
    if flag == 1:
        count = count + 1
    flag=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import itertools

[N,M] = input().split()
N = int(N)
M = int(M)
a =[]
p = []
list_bin = []

for j in range(M):
    list_temp = [int(s) for s in input().split()]
    list_temp.pop(0)
    for i in range(N):
        if i+1 in list_temp:
            list_bin.append(1)
        else:
            list_bin.append(0)

    a.append(list_bin)
    list_bin = []
p = [int(s) for s in input().split()]

arr_switch = np.array(a)
arr_p = np.array(p)
arr_pattern = np.array(list(itertools.product([0,1], repeat=N)))

count = 0
flag = 1
for switch in arr_pattern:
    for m in range(M):
        print(switch)
        print(arr_switch[m])
        print(np.dot(switch, arr_switch[m]))
        if (not (np.dot(switch, arr_switch[m]) % 2 == arr_p[m])) and (not (np.dot(switch, np.ones(N)) == 0)):
           flag = 0
    if flag == 1:
        count = count + 1
    flag=1
print(count-1)