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: Accepted

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


def base_n(x, n, zero_padding=8):
    retval = [[], ['0']][x == 0]
    while x > 0:
        x, r = divmod(x, n)
        retval.append(str(r))
    cnt = zero_padding - len(retval)
    pad = ['', '0'*cnt][cnt > 0]
    return pad+''.join(retval[::-1])


ans = 0
for i in range(2**n):
    base_2 = base_n(i, 2, n)
    for j in range(m):
        switchs = ls[j]
        cond = p[j]

        on_cnt = 0
        for switch in switchs:
            if int(base_2[switch]):
                on_cnt += 1
        if on_cnt % 2 != cond:
            break

    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
li = []
kli = []
for i in range(m):
    s = list(map(int,input().split()))
    k = s[0]
    kli.append(k)
    s.pop(0)
    li.append(s)
p = list(map(int,input().split()))
def judge():
    light = [0]*m
    for i in range(m):
        cnt = 0
        for j in range(kli[i]):
            if switch[li[i][j]-1] == 1:
                cnt += 1
        if cnt%2 == p[i]:
            light[i] = 1
    if sum(light) == m:
        return True
        
ans = 0
for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if (i>>j)&1:
            switch[n-1-j] = 1
    if judge():
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
def main():
    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(1<<N):
        isConflict = False

        for j in range(M):
            tmp = 0
            for k in ks[j][1:]:
                k -= 1
                tmp += (i>>k)
            if tmp%2 != p[j]:
                break
        else:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(2**n):
  li2=[0]*n
  for j in range(n):
    if (i>>j)&1==1:
      li2[j]=1
  li1.append(li2)

ans=0  
for i in li1:
  light=True
  for j in range(m):
    cnt=0
    for k in range(1,ks[j][0]+1):
      if i[ks[j][k]-1]==1:
        cnt+=1
        
    if cnt%2!=p[j]:
      light=False
      
  if light:
    ans+=1
      
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
right = {}
for i in range(M):
    li = list(map(int,input().split()))
    right[i] = li[1:]

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


ans = 0

for pattern in range(2**N):
    ri = 0
    for i, v in right.items():
        cnt = 0
        for sw in v:
            if pattern & (1 << (sw-1)) != 0:
                cnt += 1
        if cnt % 2  == p[i]:
            ri += 1

    if ri == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
km = [0]*m
sm = [0]*m
for i in range(m):
    inp = input().split()
    km[i] = int(inp[0])
    sm[i] = list(map(int, inp[1:]))
    
pm = list(map(int, input().split()))

cnt = 0
for i in range(2**n):
    m_state = [0]*m
    for j in range(n):
        if (i>>j)&1:
            for k in range(m):
                if j+1 in sm[k]:
                    m_state[k]+=1
    all_flg = 1
    for x in range(m):
        if m_state[x]%2!=pm[x]:
            all_flg = 0
            break
    if all_flg:
        cnt +=1

print(cnt)

Submission status: Accepted

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
  if valid():
    cnt += 1  
  for i in range(start, n):
    if not switch[i]:
      switch[i] = True
      dfs(i+1)
      switch[i] = False
      # dfs(i+1)
      
dfs(0)
print(cnt)

Submission status: Accepted

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()))
ans = 0
for i in range(1<<n):   #全部分集合について
    all_flug = True
    for j in range(m):  #全電球(パターン)について
        cnt = 0
        for k in range(n):   #全スイッチについて
            # print(bin(i), k+1, ks[j][1:], (i & (1<<k)) and (k+1 in ks[j][1:]))
            if (i & (1<<k)) and (k+1 in ks[j][1:]):   #スイッチがオンかつ電球に繋がってる
                cnt += 1
        # print(bin(i), cnt, p[j])
        # print(bin(i), cnt, p[j], cnt % 2 == p[j])
        if cnt % 2 != p[j]:
            all_flug = False
            # break
    # print(bin(i), all_flug)
    if all_flug:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

sys.setrecursionlimit(10 ** 6)

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

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


def switch(bit, ans):
    check = [(bit >> i) & 1 for i in range(N)]
    light = 0
    for i in range(M):
        num = 0
        for l in s[i]:
            if check[l - 1] == 1:
                num += 1
        if num % 2 == p[i]:
            light += 1
    if light == M:
        ans += 1
    if bit == 1:
        return ans
    else:
        return switch(bit - 1, ans)


print(switch(2 ** N, 0))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
blst = []
cnt = 0
for i in range(2 ** N):
    slst = []
    for j in range(N):
        if i >> j & 1:
            slst.append(j)
    blst.append(slst)

for i in blst:
    ansF = False
    for j in range(M):
        ctmp1 = 0
        for k in i:
            if ks[j][1:].count(k + 1) == 1:
                ctmp1 += 1
        if ctmp1 % 2 == p[j]:
            ansF = True
        else:
            ansF = False
            break
    if ansF:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = [[int(i) for i in input().split()] for j in range(m)]
p = [int(i) for i in input().split()]
count = 0
for i in range(1 << n):
    light_bulbs = 0
    for j in range(m):
        on_switches = 0
        for k in range(s[j][0]):
            if (i >> s[j][k + 1] - 1) & 1:
                on_switches += 1
        if on_switches % 2 == p[j]:
            light_bulbs += 1
    if light_bulbs == m:
        count += 1
print(count)

Submission status: Accepted

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

k = []
s = []
for i in range(M):
  kari = list(map(int, input().split()))
  k.append(kari.pop(0))
  s.append(kari)
p = list(map(int, input().split()))

ans = 2**N
for n in range(2**N):
  # 2**N通りのケースをすべて試す
  # nは0から2**N-1まで（10進法）
  
  for i in range(M):
    # M個のスイッチ（i）がすべて点灯しているかチェック
    
    hantei = 0
    for j in range(k[i]):
      hantei = hantei + ((n >> (s[i][j]-1))&1)

    if hantei%2 != p[i]:
      ans += -1
      break
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=[[] for i in range(M)]
K=[]
for m in range(M):
     kS=[int(i) for i in input().split()]
     K.append(kS[0])
     for k in range(kS[0]):
         S[m].append(kS[k+1])
P=[int(i) for i in input().split()]

# #スイッチの全通りの状態についてそれぞれの電球が点灯しているか見る
ans=0
for i in range(1<<N):
    on=set()
    for j in range(N):
        if ((i >> j) & 1) == 1:
            on.add(j+1)
    # print(i,on)
    for m in range(M):
        on_num=0
        for k in range(K[m]):
            if S[m][k] in on:
                on_num+=1
        if on_num%2 != P[m]:
            break
        if m ==M-1:
            ans+=1
print(ans)

Submission status: Accepted

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

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

ans = 0
for bit in range(2**N):
    counts = [0] * M
    for i in range(N):
        if bit & 1<<i:
            for m in range(M):
                for s in k[m]:
                    if s-1 == i:
                        counts[m] += 1
    all = True
    for m in range(M):
        if counts[m] % 2 != p[m]:
            all = False
    if all:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
k = [input().split() for _ in range(M)]
p = list(map(int, input().split()))
ans = 0
for n in range(2 ** N):
    is_mismatch = False
    for i in range(M):
        cnt = 0
        for si in k[i][1:]:
            if (n >> (int(si) - 1)) & 1:
                cnt = (cnt + 1) % 2
        if cnt != p[i]:
            is_mismatch = True
            break
    if not is_mismatch:
        ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ks = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int,input().split()))
switch = [ [0] * m for i in range(n)]
ans = 0
for i in range(m):
         for j in range(1,len(ks[i])):
                  switch[ks[i][j]-1][i] += 1
for i in range(2 ** n):
         lampcount = [ 0 ] * m
         for j in range(n):
                  if ((i >> j) & 1):
                           for k in range(m):
                                    if switch[j][k] == 1:
                                             lampcount[k] += 1
         for l in range(m):
                  lampcount[l] = lampcount[l] % 2
         if lampcount == p:
                  ans += 1
print(ans)

Submission status: Accepted

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

ans = 0

for i in range(2 ** n):
    b = bin(i)
    sb = str(b)[2:].zfill(n)
    onoff = list(sb)

    cnt = [0] * m

    for j in range(m):
        for k in lss[j][1:]:
            if onoff[k - 1] == '1':
                cnt[j] += 1
    
    for l in range(m):
        if cnt[l] % 2 == lsp[l]:
            if l == m - 1:
                ans += 1
        elif cnt[l] % 2 != lsp[l]:
            break

print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n, m = MAP()
ks = [LIST() for _ in range(m)]
p = LIST()
ans = 0
for i in range(2 ** n):
    bit = format(i, 'b').zfill(n)
    flag = True
    for j in range(m):
        k = ks[j][0]
        s = ks[j][1:]
        tmp = 0
        for l in s:
            tmp += int(bit[l - 1])
        if tmp % 2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(lambda x: int(x), input().split())
mask_list = []
for i in range(M):
    ks = list(map(lambda x: int(x), input().split()))
    k, s = ks[0], ks[1:]
    mask = 0
    for j in s:
        mask += (1 << (j - 1))
    mask_list.append(mask)
p_list = list(map(lambda x: int(x), input().split()))

count = 0
for i in range(2 ** N):
    tmp = 1
    for j in range(M):
        def count_bit(val):
            result = 0
            while val > 0:
                result += val & 1
                val = val >> 1
            return result
        if count_bit(i & mask_list[j]) % 2 != p_list[j]:
            tmp = 0
            break
    count += tmp
print(count)

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))
N, M = inpl()
L = [0]*M
for i in range(M):
    for s in inpl()[1:]:
        L[i] += pow(2, s-1)
P = inpl()
print(sum([sum([bin(L[j]&i).count("1")%2 == P[j] for j in range(M)]) == M for i in range(pow(2, N))]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
X=[]
for i in range(m):
    x=list(map(int,input().split()))
    X.append(x)
P=list(map(int,input().split()))

ans=0

for i in range(2**n):
    B=[]
    b=format(i,'b')
    b=b.zfill(n)
    for j in range(n):
        B.append(int(b[j]))
    flag=True
    for k in range(m):
        cnt=0
        for l in range(X[k][0]):
            cnt+=B[X[k][l+1]-1]
        if cnt%2!=P[k]:
            flag=False
    if flag:
        ans+=1
        
print(ans)

Submission status: Accepted

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

Solution code:
def main():
    N, M = map(int, input().split())
    S = [list(map(lambda x: int(x) - 1, input().split()))[1:] for _ in range(M)]
    P = list(map(int, input().split()))

    ans = 0
    for bit in range(1 << N):
        for i in range(M):
            on = 0
            for j in S[i]:
                if bit & (1 << j):
                    on += 1
            if on % 2 != P[i]:
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    S = []
    for i in range(M):
        S.append(list(map(lambda x: int(x) - 1, input().split()))[1:])
    P = list(map(int, input().split()))

    ans = 0
    for bit in range(1 << N):
        for i in range(M):
            on = 0
            for j in S[i]:
                if bit & (1 << j):
                    on += 1
            if on % 2 != P[i]:
                break
        else:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def ma():
  import sys
  input = sys.stdin.readline
  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"}
    for j in range(1,m+1):
      if len(e[j-1]&l)%2!=f[j-1]:break
    else:ans+=1
  print(ans)

if __name__=="__main__":
  ma()

Submission status: Accepted

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

if __name__=="__main__":
  ma()

Submission status: Accepted

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)})==0:ans+=1
  print(ans)

if __name__=="__main__":
  ma()

Submission status: Accepted

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)])==0:ans+=1
  print(ans)

if __name__=="__main__":
  ma()

Submission status: Accepted

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"}
    for j in range(1,m+1):
      if len(e[j-1]&l)%2!=f[j-1]:break
    else:ans+=1
  print(ans)

if __name__=="__main__":
  ma()

Submission status: Accepted

Solution code:
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"}
  for j in range(1,m+1):
    if len(e[j-1]&l)%2!=f[j-1]:break
  else:ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
list_data = [ list(map(int,input().split(" "))) for i in range(m)]
list_condition = list(map(int, input().split()))

for i in range(m):
    a = list_data[i]
    a.pop(0)

ans = 0

for i in range(2**n):
    list_ans = [0] * m
    for l in range(m):
        for j in range(n):
            if ((i >> j) & 1):
                if j+1 in list_data[l]:
                    list_ans[l] += 1
    a = list(map(lambda x:x % 2, list_ans))
    if a == list_condition:
        ans += 1

print(ans)

Submission status: Accepted

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

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

ans = 0
for x in itertools.product([0, 1], repeat=N):
    total = 0
    for i in range(M):
        count = 0
        for j in range(k[i]):
            if x[s[i][j]-1]:
                count += 1
        if p[i] == count % 2:
            total += 1
    if total == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    N, M = map(int, input().split())

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

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

    cnt = 0

    for i in range(2 ** N):
        bin_i = '{:010b}'.format(i)[::-1]

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

            sum_s = 0

            for j in range(k):
                sum_s += int(bin_i[s[j] - 1])

            if sum_s % 2 != P[i]:
                break
        else:
            cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
n,m = map(int, input().split())
switch = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int, input().split()))
count = 0
for j in range(2**n):#スイッチ

    flag = True
    for i in range(m):
        on = 0
        for k in switch[i][1:]:
            if (j >> k-1) & 1:
                on += 1
        if on % 2 != p[i]:
            flag = False
            #break
    if flag:
        count +=1
print(count)

Submission status: Accepted

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

switches = []
for i in range(m):
    tmp_list = list(map(int, input().split()))
    switches.append(tmp_list[1:])
values = list(map(int, input().split()))

on_offs = [i for i in range(2 ** n)]

count = 0
for i in range(2 ** n):
    ng = False
    for p, s_list in zip(values, switches):
        # print(f'i = {i}')
        on_count = 0
        # print(s_list)
        for s in s_list:
            if (i >> (s - 1)) & 1:
                # print(i, s - 1)
                on_count += 1
        # print(i, on_count)
        if on_count % 2 != p:
            ng = True
            break
    if not ng:
        # print(i)
        count += 1

print(count)

Submission status: Accepted

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

res = 0

for i in range(2**N):
    sw = []
    for j in range(N):
        if (i>>j) & 1:
            sw.append(True)
        else:
            sw.append(False)
    for j in range(M):
        c = 0
        for y in s[j]:
            if sw[y-1]:
                c += 1
        if c%2 != p[j]:
            break
    else:
        res += 1

print(res)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
list_data = [ list(map(int,input().split(" "))) for i in range(m)]
list_condition = list(map(int, input().split()))

for i in range(m):
    a = list_data[i]
    a.pop(0)

ans = 0

for i in range(2**n):
    list_ans = [0] * m
    for l in range(m):
        for j in range(n):
            if ((i >> j) & 1):
                if j+1 in list_data[l]:
                    list_ans[l] += 1
    a = list(map(lambda x:x % 2, list_ans))
    if a == list_condition:
        ans += 1

print(ans)

Submission status: Accepted

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

for bit in range(2 ** n):
	ans = []
	for i in range(n):
		if (bit >> i) & 1:
			ans.append(1)
		else:
			ans.append(0)
	
	f = [0] * m
	for j in range(len(ks)):
		b = 0
		for i in ks[j][1:]:
			if ans[i-1] == 1:
				b += 1

		if b % 2 == p[j]:
			f[j] = 1

	if f.count(1) == len(ks):
		c += 1
	
print(c)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
switches = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
ans = 0
for i in range(2 ** N):
    tmp = [0]*N
    for k in range(N):
        if 1 & i>>k:
            tmp[k] = 1
    flg = True
    for k in range(M):
        count = 0
        for l in range(1,switches[k][0]+1):
            if tmp[switches[k][l]-1] == 1:
                count += 1
        if count % 2 != p[k]:
            flg = False
    if flg:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
b = [None] * m
for i in range(m):
    _, *b[i] = map(lambda x: int(x)-1, input().split())
p = list(map(int, input().split()))
ans = 0
for x in range(2**n):
    light = 0
    for i, j in enumerate(b):
        switch = 0
        for k in j:
            switch += x >> k & 1
        if switch % 2 == p[i]:
            light += 1
    if light == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
tmp = [0 for i in range(N)]
S = []
for _ in range(M):
    k = list(map(int,input().split()))
    s = list(tmp)
    for i in k[1:]:
        s[i-1] = 1
    S.append(s)
P = list(map(int,input().split()))
#print(S)
x = [0,1]
Y = list(itertools.product(x,repeat=N))
#print(Y)
ans = 0
for i in Y:
    on = []
    for j in range(M):
        count = 0 
        for n in range(N):
            if i[n] == 1 and S[j][n] == 1:
                count += 1
        if count % 2 == P[j]:
            on.append(1)
        else:
            on.append(0)
    #print(on)
    if 0 not in on:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import itertools
from pprint import pprint
N,M = map(int,input().split())
K =[]
S = []
for i in range(M):
	ki, *s = map(int,input().split())
	K.append(ki)
	S.append(s)
C = list(map(int,input().split()))
status = [(0, 1) for _ in range(N)]
state = list(itertools.product(*status))  # 直積を求める
ans = 0
for i in state:
	flg = True
	for kidx,ki in enumerate(K):
		ci = 0
		for si in range(ki):
#			print("kidx:",kidx,", si:",si,", ki:",ki,", S[kidx][si]:",S[kidx][si],", state[S[kidx][si]]:",state[S[kidx][si]])
			ci += i[S[kidx][si]-1]
		if ci%2 != C[kidx]:
			flg = False
	if flg:
		ans += 1
print(ans)

Submission status: Accepted

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

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

# print(f"N: {N}, M: {M}")
# print(f"k: {k}")
# print(f"s: {s}")
# print(f"p: {p}")

res = 0
for bit in range(2 ** N):
    # print(f"bit: {bin(bit)}")
    num_on = 0
    for i_light in range(M):
        # print(f"# check light {i_light} is on")
        count = 0
        for k_switch in range(k[i_light]):
            # s[i, k_i]番目のswitchがonかどうか
            if bit & (1 << s[i_light][k_switch]-1):
                # print(f"### switch {s[i_light][k_switch]} is on")
                count += 1
            # else:
                # print(f"### switch {s[i_light][k_switch]} is NOT on")
        # i番目のlightが点灯しているとき
        # print(f"# count % 2 == p[i]: {count%2} == {p[i_light]}")
        if count % 2 == p[i_light]:
            # print(f"## light {i_light} is on")
            num_on += 1
        # else:
            # print(f"## light {i_light} is NOT on")
    # M個のlight全てが点灯しているとき
    if num_on == M:
        # print(f"all light is on")
        res += 1

print(res)

Submission status: Accepted

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

N,M = list(map(int, input().rstrip().split()))
ks_list = [list(map(int, input().rstrip().split())) for i in range(M)]
p_list = list(map(int, input().rstrip().split()))
#-----

total_count=0
for sw in range(2**N):
    bin_str = format(sw, 'b').zfill(N)
    
    for i in range(M):
        k = ks_list[i][0]
        s_list = ks_list[i][1:]
        
        cnt_on=0
        for j in s_list:
            if bin_str[j-1] == "1":
                cnt_on += 1
        
        if cnt_on % 2 != p_list[i]:
            break
    
    else:
        total_count += 1    

print(total_count)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]#2次元配列
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):#全てのスイッチの場合に対して
    check = True#全点灯かどうか調べる
    for j in range(m):#電球ごと
        light = 0#スイッチオンの数
        for k in range(1,len(l[j])):
            if((i>>l[j][k] -1) &1):#j番目の電球のk個目のスイッチが入ってるなら
                light +=1#スイッチオンの数+1
        if light%2 != p[j]:
            check = False#スイッチオフならfalse
    if check:
        ans +=1
print(ans)

Submission status: Accepted

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

def Bit(x,N):
    bit = [0 for _ in range(N)]
    for i in range(N):
        if x - 2**(N-i-1) >= 0:
            bit[i] = 1
            x -= 2**(N-i-1)
    return bit

def judge(a,N):
    bit = Bit(a,N)
    LB= [P[i] for i in range(M)]
    for i in range(N):
        if bit[i] == 1:
            for j in range(M):
                if i+1 in KS[j][1:len(KS[j])]:
                    LB[j] += 1
                    LB[j] %= 2
    if sum(LB) == 0:
        return True
    else:
        return False

count = 0
for i in range(2**N):
    if judge(i,N):
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, m = map(int, input().split())
ks = [[0]*(m+1) for _ in range(m)]
ans = 0
for i in range(m):
    ks[i] = list(map(int, input().split()))
p = list( map(int, input().split()))

ans = 0
for i in range(2**n):
    isConflict = False

    for j in range(m):
        tmp = 0
        for k in ks[j][1:]:
            k -= 1
            tmp += (i >> k)
        if tmp%2 != p[j]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, raw_input().split())
ks_s = []
for i in range(M):
    ks_s.append(map(int, raw_input().split()))

ps = map(int, raw_input().split())

ans = 0
for i in range(2**N):
    flag = True
    for j in range(M):
        p = ps[j]
        k = ks_s[j][0]
        num_on = 0
        for l in range(1, k+1):
            s = ks_s[j][l]
#            print i, j, l, s, bin(i), bin(1<<s)                                                       
            if 1 << s-1 & i:
                num_on = num_on + 1
        if num_on % 2 != p:
            flag = False
#            break                                                                                     

    if flag:
        ans = ans + 1

print ans

Submission status: Accepted

Solution code:
import itertools
import numpy as np

N, M = map(int, input().split())
switch = dict()
for i in range(1, M+1):
    in_put = list(map(int, input().split()))
    s = in_put[1:]
    switch[i] = s

mod = list(map(int, input().split()))
A = [0, 1]
comb = itertools.product(A, repeat=N)

switch_list = list()
for i, v in switch.items():
    kari = list()
    for k in range(1, N+1):
        if k in v:
            kari.append(1)
        else:
            kari.append(0)
    switch_list.append(kari)
switch_array = np.array(switch_list)

count = 0
for i in comb:
    check_count = 0
    comb_array = np.array(i)
    for k in range(M):
        check = switch_array[k, :] * comb_array
        check_sum = check.sum()
        #print(i)
        #print(switch_array[k, i])
        #print(check, check_sum)
        if check_sum % 2 != mod[k]:
            check_count = 1
    if check_count == 0:
        count += 1

print(count)