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())
nums = [i+1 for i in range(n)]
cnt = 0
ss = [set(map(int, input().split()[1:])) for i in range(m)]
ps = list(map(int, input().split()))
for i in range(2**n):
    flag = True
    s = bin(i)[2:].zfill(n)
    on_set = set(nums[i] for i in range(n) if int(s[i]))
    for j in range(m):
        if len(on_set & ss[j])%2 == ps[j]:
            continue
        else:
            flag = False
            break
    if flag:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
lights = [lr() for _ in range(M)]
P = lr()
answer = 0
for bit in range(2 ** N):
    bl = True
    for i in range(M):
        p = P[i]
        result = 0
        for s in lights[i][1:]:
            s -= 1
            if (bit >> s) & 1:
                result += 1
        if result % 2 != p:
            bl = False
    if bl:
        answer += 1
print(answer)

Submission status: Accepted

Solution code:
import itertools

N, M = [int(i) for i in input().split(' ')]

switch = []
for _ in range(M):
    tmp = list(map(int,input().split(' ')))
    switch.append(tmp[1::])

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

for onoff in itertools.product([0,1],repeat=N):
    on_count = 0
    on_count = sum(sum(onoff[i-1] for i in s) % 2 == p for s,p in zip(switch,P))
    if on_count == M:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = [0] * M
for i in range(M):
  S[i] =  list(map(int, input().split()))
P = list(map(int, input().split()))
#print(S, P)
ans = 0

for i in range(2 ** N):#bit全探索
  bin_i = bin(i)[2:].zfill(N)#zfillは0埋め
  #print(bin_i)
  m = 0
  for j in range(M):#各電球についてルーブ
    x = 0#ついてるスイッチの数
    for l in range(1,S[j][0] + 1):#各スイッチについてループ
      if bin_i[S[j][l] - 1] == "1":#スイッチがonなら
        x += 1
        
    if x % 2 != P[j]:
      m = 1
      #print(bin_i, j, l, x, P[j])
    
  if m == 0:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
KS = [list(map(int,input().split()))[1:] 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: Accepted

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

Solution code:
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)
cnt = 0

#print(bit)

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

    #print(switch[1:])

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

        #print(k, c, P[k])

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

    if ok:
        cnt += 1

print(cnt)

Submission status: Accepted

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]:
      continue
    else:
      ok = 0
  if ok == 1:
    anscnt += 1
      
print(int(anscnt))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
base = [list(map(int,input().split())) for i in range(m)]
judge = list(map(int,input().split()))
ans = 0

for i in range(2**n):
  count = [0] * m
  sign = 0
  for j in range(n):
    if (i >> j) & 1:
      for k in range(m):
        for l in range(base[k][0]):
          if (j+1) == base[k][l+1]:
            count[k] = count[k] + 1
  
  for j in range(m):
    if (count[j]%2 != judge[j]):
      sign = 1
      break

  if sign == 0:
    ans = ans + 1
  
print(ans)

Submission status: Accepted

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

for i in range(2**N):
    for j in range(M):
        tmp = 0
        for s in switch[j][1:]:
            if i & 2**(s-1) == 2**(s-1):
                tmp = 1-tmp
        if tmp != p[j]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import math

from collections import defaultdict
from collections import deque
def load(vtype=int):
    return vtype(input().strip())
def load_list(seplator=" ", vtype=int):
    return [vtype(v) for v in input().strip().split(seplator)]
def exit():
    import sys
    sys.exit(0)
def perm_sub(li, used):
    if len(li) == len(used):
        return [deque()]
    k = []
    for i in range(len(li)):
        if i in used:
            continue
        used.add(i)
        sub_list = perm_sub(li, used)
        for sub in sub_list:
            sub.appendleft(li[i])
        k.extend(sub_list)
        used.discard(i)
    return k
def perm_li(li):
    return perm_sub(li, set())
def perm_n(n):
    return perm_sub(list(range(n)), set())
def join_i(li, sep=""):
    return sep.join([str(e) for e in li])
def li2n(li):
    n, base = 0, 1
    for i in range(len(li)-1, -1, -1):
        n += li[i] * base
        base *= 10
    return n
def sli2ili(li):
    return [int(s) for s in li] 
def prime_list(n):
    li = [i for i in range(2, n+1)]
    for i in range(len(li)):
        if li[i] >= int(math.sqrt(n)):
            break
        if li[i] == -1:
            continue
        for j in range(i+1, len(li)):
            if li[j] % li[i] == 0:
                li[j] = -1
    return [n for n in li if n != -1]
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while True:
        r = a % b
        if r == 0: return b
        a, b = b, r
def lcm(a, b):
    return int(a * b / gcd(a,b))
def all_subset(li):
    s = []
    n = len(li)
    for bit in range(0, (1<<(n+1))):
        ss = set()
        for i in range(0, n):
            if (bit & (1 << i)):
                ss.add(li[i])
        s.append(ss)
    return s
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)
def mCn(m, n):
    def factorial_ntimes(m, n):
        r = 1
        while n:
            r *= m
            m -= 1
            n -= 1
        return r
    return int(factorial_ntimes(m, n) / factorial(n))

n, m = load_list()
S = []
for _ in range(m):
    s = load_list()
    del s[0]
    S.append(s)
p = load_list()

def s2bit(s):
    bit = 0
    for e in s:
        bit |= 2**(e-1)
    return bit

cnt = 0
for bit in range(0, 2**n):
    flag = True
    for i in range(m):
        if not bin(s2bit(S[i]) & bit).count("1") % 2 == p[i]:
            flag = False
            break
    if flag:
        cnt += 1


print(cnt)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

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

    S = []
    for i in range(M):
        k, *tmp = [int(i) for i in readline().split()]
        S.append(tmp)
    
    p = list(map(int, readline().split()))

    # bit
    ans = 0
    for i in range(2**N):
        select = []
        for j in range(N):
            if (i>>j) & 1:
                select.append(j+1)
        
        for m in range(M):
            flag = 1
            if sum([1 for x in S[m] if x in select])%2 != p[m]:
                flag = 0
                break
        if flag  == 1:
            ans += 1
        
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import itertools
import math
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
INF = 1 << 60
sys.setrecursionlimit(10 ** 6)

#ここから書き始める
n, m = map(int, input().split())
k = [0] * m
s = []
for i in range(m):
    a = list(map(int, input().split()))    
    k[i] = a[0]
    s.append(a[1:])
p = list(map(int, input().split()))
ans = 0
for i in range(1 << n):
    bit = format(i, "01024b")[::-1]
    on = True
    for j in range(m):
        cnt = 0
        for k in s[j]:
            if bit[k - 1] == "1":
                cnt += 1
        if cnt % 2 != p[j]:
            on = False
            break
    if on:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# library
# -------------------------------------------------------------



# -------------------------------------------------------------
# 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

i = 0
while i < 2**N:
    bit = bin(i)[2:].zfill(N)
    check = True
    for j in range(M):
        swlist = KS[j][1:]
        cnt = 0
        for sw in swlist:
            if bit[sw-1] == "1":
                cnt += 1
        if cnt%2 != P[j]:
            check = False
            break
    if check:
        ans += 1
    i += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    k = [None] * M
    s = [None] * M
    for i in range(M):
        line = tuple(map(int, input().split()))
        k[i], s[i] = line[0], line[1:]
    p = tuple(map(int, input().split()))

    ans = 0
    for bit in range(2 ** N):
        light_all = True
        # on/off on switches
        sw = [None] * N
        for i in range(N):
            if bit & (1 << i):
                sw[i] = True
            else:
                sw[i] = False
        for i in range(M):
            n_on = 0
            for j in s[i]:
                n_on += sw[j - 1]
            if n_on % 2 == p[i]:
                pass
            else:
                light_all = False
        ans += light_all

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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()
    for shift in range(n):
        if (bits >> shift) & 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)

Submission status: Accepted

Solution code:
N,M = (int(x) for x in input().split())
ks = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split())) 
switchstate = [False for i in range(1, N+1)]
count = 0
for i in range(2 ** (N)):
    broke = False
    for j in range(N):
        if i >> j & 1:
            switchstate[j] = True
        else:
            switchstate[j] = False
    for j in range(M):
        temp = []
        for k in range(len(ks[j])-1):
            temp.append(switchstate[ks[j][k+1]-1])
        if temp.count(True) % 2 != p[j]:
            broke = True
            break
    if broke == False:
        count += 1
print(count)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
S = [0]*M
for i in range(M):
    S[i] = list(map(int, input().split()))
P = list(map(int, input().split()))


def check(bit):
    f = True
    for i in range(M):
        cnt = 0
        for si in range(len(S[i])):
            if si == 0:
                pass
            else:
                cnt += int(bit[S[i][si]-1])
        if cnt%2 != P[i]:
            f = False
    return f    
    

ans = 0
for i in range(2**N):
    bit = bin(i)[2:].zfill(N)
    if check(bit):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

n, m = list(map(int, input().split()))
swi = []
for _ in range(m):
    k, *sss = list(map(int, input().split()))
    t = 0
    for s in sss:
        t += 1 << (s - 1)
    swi.append(t)
ppp = list(map(int, input().split()))

ans = 0
for i in range(1 << n):
    for s, p in zip(swi, ppp):
        t = i & s
        c = bin(t).count('1') % 2
        if c != p:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
idx = lambda x: x-1
n, m = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    b = bin(i)[2:].rjust(n, "0")
    light = True
    for i, di in enumerate(d):
        sw = 0
        for j in di[1:]:
            sw += int(b[idx(j)])
        if sw % 2 != p[i]:
            light = False
            break
    if light:
        ans += 1
print(ans)

Submission status: Accepted

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

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

ans = 0

for i in range(1 << N):
    for r in range(M):
        on_sum = 0
        for j in range(N):
            if (i >> j)&1 and j in lamps[r]:
                on_sum += 1
        if on_sum % 2 != p[r]:
            break
    else:
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n, m = map(int, readline().split())
  sw = [[] for _ in range(m)]
  for i in range(m):
    sw[i] = list(map(int, readline().split()[1:]))
  p = [int(x) for x in input().split()] # 不要
  answer = 0
  
  for jotai in product([0,1], repeat=n):
    bl = True
    for i in range(m):
      s = sum([jotai[s-1] for s in sw[i]])
      if (s-p[i])%2 != 0:
        bl = False
        break
    if bl:
      answer += 1
  print(answer)
  
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def solve():
    N, M = map(int, input().split())
    k = []
    s = []
    for i in range(M):
        tmp = list(map(int, input().split()))
        tmpk = tmp[0]
        tmps = list(map(lambda x:x-1,tmp[1:]))
        k.append(tmpk)
        s.append(tmps)
    
    p = list(map(int, input().split()))

    ans = 0
    for bit in range(1 << N):
        on_switches = set() 
        for j in range(N):
            if (1 << j) & bit:
                on_switches.add(j)
        
        for i in range(M):
            cnt = 0
            for j in range(k[i]):
                if s[i][j] in on_switches:
                    cnt += 1
            
            if cnt % 2 != p[i]:
                break
        else:
            ans += 1
    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
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 i in range(2**n):
    flag = True
    for j in range(m):
        on = 0
        for k in switch[j][1:]:
            if (i>>k-1)&1:
                on +=1
        if on%2 != p[j]:
            flag = False
    if flag:
        count +=1
print(count)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    N, M = input_nums()
    lights = {}
    for i in range(M):
        s = input_nums()[1:]
        lights[i] = s
    p = input_nums()
    cnt = 0
    for bit in range(1<<N):
        on = True
        # M個の電球について調べていく
        for l in range(M):
            ll = lights[l]
            cnt_each = 0
            # N個のスイッチの状態において、電球lが点灯するか調べる
            for i in range(N):
                if bit & (1<<i):
                    # そもそもスイッチがつながってない場合はスキップ
                    if not (i+1) in ll:
                        continue
                    cnt_each += 1
            if cnt_each%2 == p[l]:
                continue
            else:
                on = False
                break
        if on:
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from fractions import gcd                    # for Python3.4.3


def main():
    mod = 10000007                  # 10^9+7
    inf = float('inf')
    input = sys.stdin.readline      # 改行文字が残ることに注意
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def ii():  return int(input())
    def mi():  return map(int, input().rstrip().split())
    def lmi(): return list(map(int, input().rstrip().split()))
    def li():  return list(input().rstrip())
    

    def illuminate_p(state, bulb, L, P):
        connected_count = 0
        mask = 0b1
        for switch in L[bulb]:
            if state & (mask << switch):
                connected_count += 1
        return connected_count % 2 == P[bulb]
    

    n, m = mi()
    L = [None] * m
    # L[i] に電球 i のつながっているスイッチのリストが入る
    for i in range(m):
        line = list(map(lambda x: int(x)-1, input().rstrip().split()))
        L[i] = line[1:]
    P = lmi()

    ans = 0
    # state の下位 [j] bit が [j] 番目の switch が on かどうかのフラグとなる
    for state in range(2**n):
        for bulb in range(m):
            if not illuminate_p(state, bulb, L, P):
                break
        else:
            ans += 1
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
k = [list(map(int,input().split()))[1:] for _ in range(M)]
p = list(map(int,input().split()))
cnt = 0
for i in range(2**N):
    switch = bin(i)[2:].zfill(N)
    flag = True
    for j in range(M):
        on = 0
        for index in k[j]:
            if switch[index-1] == '1':
                on += 1
        if on % 2 != p[j]:
            flag = False
            break
    if flag:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
K = [[] for i in range(M)]
for i in range(M):
    k = list(map(int, input().split()))
    K[i] = k[1:]
 
P = list(map(int, input().split()))

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

Submission status: Accepted

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


K = [[0]*N for i in range(M)]


for i in range(M):
    tmp = list(map(int, input().split()))
    for j in tmp[1:]:
        K[i][j-1] = 1
p = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    tmp = [0]*M
    for j in range(N):
        if (i >> j) % 2 == 1:
            for k in range(M):
                tmp[k] += K[k][j]
    for j in range(M):
        if tmp[j] % 2 != p[j]:
            break
    else:
        ans += 1


print(ans)

Submission status: Accepted

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

@author: liang
"""

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = [[] for i in range(m)]
for i in range(m):
    s[i] = list(map(int, input().split()))[1:]
p = list(map(int, input().split()))
count = 0
for i in range(2**n):
    light = bin(i)[2:].zfill(n)
    flag = True
    for j in range(m):
        work = 0
        for el in s[j]:
            if light[el-1] == '1':
                work += 1
        if work%2 != p[j]:
            flag = False
            break
    if flag:
        count += 1
print(count)

Submission status: Accepted

Solution code:
# C
n, m = map(int, input().split())
k =[0]*m
s = [0]*m
for i in range(m):
    lst=input().split()
    k[i] = int(lst[0])
    s[i] = [int(x) - 1 for x in lst[1:]]
p = [int(x) for x in input().split()]
# print(s, p)
ans=0
for i in range(2 ** n):
    all_on = True
    for j in range(m):
        light = 0
        for k in s[j]:
            tmp = i >> k & 1
            #iをkだけ左にシフトし1とのANDをとる
            #>>iのk番目が1の時１を返す
            light = (light + tmp) % 2
            # print(tmp,light)
        if light != p[j]:
            all_on = False
            # print(light,p[j])
            break
    ans += int(all_on)
print(ans)

Submission status: Accepted

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

X = []
for _ in range(M):
    t = list(map(int, input().split()))
    X.append(t[1:])

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

r = 0
for i in range(2**N):
    j = i
    c = 1
    cs = set()
    while j:
        if j % 2:
            cs.add(c)
        j //= 2
        c += 1

    for i in range(M):
        t = 0
        for x in X[i]:
            if x in cs:
                t += 1
        if t%2 != P[i]:
            break
    else:
        r += 1

print(r)

Submission status: Accepted

Solution code:
from collections import deque

N, M = [int(x) for x in input().split()]
k = [None] * M
s = [None] * M
for i in range(M):
    lst = input().split()
    k[i] = int(lst[0])
    s[i] = [int(x) - 1 for x in lst[1:]]  # index調整
p = [int(x) for x in input().split()]

ans = 0
# すべてのスイッチの状態を試す
for sw in range(2 ** N):
    all_on = True
    for i in range(M):  # 各電球がONしているか確認
        light = 0
        for j in s[i]:  # 各スイッチの値の和
            light = (light + (sw >> j) & 1 ) % 2
        if light != p[i]:
            all_on = False
            break
    ans += int(all_on)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
K=[]
S=[]
for i in range(m):
    x=list(map(int,input().split()))
    K.append(x[0])
    S.append(list(x[1:]))
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    flg=True
    for j in range(m):
        tmp=0
        for k in S[j]:
            if i>>(k-1) & 1:
                tmp+=1
        if tmp%2==p[j]:
            continue
        else:
            flg=False
    if flg:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = []
for _ in range(M):
    ipt = [int(i) for i in input().split()]
    S.append([True if i in ipt[1:] else False for i in range(1, N+1)])
P = [int(p) for p in input().split()]

ans = 0
for cmb in range(0, 2**N):
    b = list(str(bin(cmb)))[2:]
    cmb_b = ["0"]*(N-len(b)) + b
    cur_cnd = [0]*M
    for s_cnd, i in zip(reversed(cmb_b), range(N)):
        for s, j in zip(S, range(M)):
            if s_cnd == "1" and s[i]:
                cur_cnd[j] = (cur_cnd[j]+1) % 2
    if P == cur_cnd:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M = map(int, input().split())
k = [list(map(int, input().split()))[1:] for _ in range(M)]
p = list(map(int, input().split()))
print(sum([all([sum([s[j-1] for j in v])%2==t  for v,t in zip(k, p)]) for s in itertools.product([0,1],repeat=N)]))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
K=[]
S=[]
ans=0
for i in range(M):
    tmp=list(map(int,input().split()))
    k,s=tmp[0],tmp[1:]
    K.append(k)
    S.append(s)
p=list(map(int,input().split()))
for s in range(2**N):
    cnt=[0]*M
    f=1
    for i in range(M):
        k=S[i]
        for j in k:
            if (s>>(j-1)&1):
                cnt[i]+=1
        if cnt[i]%2!=p[i]:
            f=0
            break
    if f==1:
        ans+=1
print(ans)