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:
from itertools import product

N, M = map(int, input().split())

ks = [[int(i) for i in input().split()] for _ in range(M)]
p = [int(i) for i in input().split()]

res = 0

for i in product(range(2), repeat=N) :
    flag = True
    for j in range(M) :
        tmp = 0
        for s in ks[j][1:] :
            tmp += i[s-1]
        
        if tmp % 2 != p[j] :
            flag = False
            break
    if flag :
        res += 1

print(res)

Submission status: Accepted

Solution code:
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

n,m = map(int,input().split())
kss=[]
ans = 0
for i in range(m):
    ks = list(map(int,input().split()))
    kss.append(ks)
p = list(map(int,input().split()))
for i in range(2**n):
    switch = set()
    for j in range(n):
        if (i>>j)&1:
            switch.add(j+1)

    bool = True
    for k in range(m):
        if len(set(kss[k][1:])&switch)%2 == p[k]:
            continue
        else:
            bool = False
    if bool:
        ans += 1
print(ans)

Submission status: Accepted

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

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

total = 0
import itertools
for p in itertools.product([0, 1], repeat=N):
    good = True
    for i, switch in enumerate(switches):
        ons = 0
        for si in switch:
            ons += p[si-1]
        if ons % 2 != mods[i]:
            good = False
            break
    if good:
        total += 1

print(total)

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
kss = []

for mm in range(m):
  ks = list(map(int, input().split()))
  k = ks[0]
  s = ks[1:]
  kss.append(s)
ps = list(map(int, input().split()))

ok_count = 0
combs = [[0,1]]*n
for state in itertools.product(*combs):
  ok = True
  for mm in range(m):
    sm = 0
    for s in kss[mm]:
      sm += state[s-1]
    if sm % 2 != ps[mm]:
      ok = False
      break
  if ok:
    ok_count += 1
print(ok_count)

Submission status: Accepted

Solution code:
import sys
# gcd
from fractions import gcd
# 切り上げ，切り捨て
# from math import ceil, floor
# リストの真のコピー（変更が伝播しない）
# from copy import deepcopy
# 累積和。list(accumulate(A))としてAの累積和
from itertools import accumulate
# l = ['a', 'b', 'b', 'c', 'b', 'a', 'c', 'c', 'b', 'c', 'b', 'a']
# S = Counter(l)  # カウンタークラスが作られる。S=Counter({'b': 5, 'c': 4, 'a': 3})
# print(S.most_common(2))  # [('b', 5), ('c', 4)]
# print(S.keys())  # dict_keys(['a', 'b', 'c'])
# print(S.values())  # dict_values([3, 5, 4])
# print(S.items())  # dict_items([('a', 3), ('b', 5), ('c', 4)])
# from collections import Counter
# import math
# from functools import reduce
#
# input関係の定義
# fin = open('in_3.txt', 'r')
# sys.stdin = fin
input = sys.stdin.readline
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())
# template


MOD = 2  # type: int


if __name__ == '__main__':
    N, M = mi()
    s = []
    k = [0]*M
    for i in range(M):
        k[i], *tmp = lmi()
        # print(tmp)
        s.append(tmp)
    # print(s)
    p = lmi()
    cnt = 0
    for i in range(2 ** N):
        flag = True
        for num in range(M):
            tmp_cnt = 0
            for sw in s[num]:
                if ((i >> sw - 1) & 1):
                    tmp_cnt += 1
            if tmp_cnt % 2 == p[num]:
                continue
            else:
                flag = False
                break
        if flag:
            cnt += 1
    print(cnt)

Submission status: Accepted

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



"""
import sys


from itertools import product

def solve(N, M, lights, P):
    ans = 0
    for p in product([0, 1], repeat=N):
        on_light = 0
        for i, l in enumerate(lights, start=1):
            on = 0
            for ll in l[1:]:
                if p[ll-1]:
                    on += 1
            if on % 2 == P[i-1]:
                on_light += 1
        if on_light == M:
            ans += 1
    return ans



def main(args):
    N, M = map(int, input().split())
    lights = [[int(i) for i in input().split()] for _ in range(M)]
    P = [int(p) for p in input().split()]
    ans = solve(N, M, lights, P)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc128/abc128_c
import itertools as it

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

iterable = it.product([0, 1], repeat=N)
cnt = 0
for switches in iterable:
    res = True
    for xs, p in zip(xss, ps):
        selected = [switches[x - 1] for x in xs]
        is_on = (sum(selected) % 2) == p
        res = res and is_on

    if res:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()

ks = [LIST() for _ in range(M)]

p = LIST()

ans = 0
for i in range(1<<N):  # スイッチの状態を全探索
	i = list("{:b}".format(i).zfill(N))
	flag = True
	for j, lis in enumerate(ks):
		lis = lis[1:]
		tmp = 0
		for l in lis:
			if i[l-1] == '1':
				tmp += 1
		if tmp % 2 != p[j]:
			flag = False
			break
	if flag:
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))

def main():
    N,M = ints_raw()
    SS =[0]*(N+1)
    for midx in range(M):
        ks = ints_raw()
        for j in ks[1:]:
            SS[j-1] += 1<<midx
    p = 0
    pis = ints_raw()
    for midx in range(M):
        pi = pis[midx]
        if pi>=2:
            return 0
        if pi ==1:
            p+=1<<midx
    ans = 0
    for dbit in range(2**N):
        tmp = 0
        for j in range(N):
            if (dbit & (1<<j)):
                tmp = tmp^SS[j]
        if tmp == p:
            ans+=1
    return ans

print(main())

Submission status: Accepted

Solution code:

def main():
    nn, m = map(int, raw_input().split())
    ss = []
    for _ in xrange(m):
        n = 0
        for s in map(int, raw_input().split()[1:]):
            n |= 1 << (s - 1)
        ss.append(n)
    pp = map(int, raw_input().split())
    ans = 0
    for sw in xrange(2 ** nn):
        for s, p in zip(ss, pp):
            if bin((sw & s)).count('1') % 2 != p:
                break
        else:
            ans += 1
    print ans


if __name__ == '__main__':
    main()

Submission status: Accepted

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

light_num = [0] * (m+1)
for i in range(2**n):
    light = 0
    for j in range(m):
        val = 0
        for k in ks[j]:
            if i & 1 << (k-1):
                val += 1
        if val % 2 == p[j]:
            light += 1
    light_num[light] += 1
print(light_num[m])

Submission status: Accepted

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

ans = 0
s = []
for i in range(m):
    S = list(map(int, input().split()))
    s.append(S[1:])

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

for i in range(2**n):
    flag = 0
    for j in range(m):
        count = 0
        for sj in s[j]:
            if (1 << (sj-1)) & i:
                count += 1
        if count % 2 != p[j]:
            flag = 1
            break
    if flag:
        continue
    ans += 1

print(ans)

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()))
ans=0
for i in range(2**n):
  s=bin(i)[2:].zfill(n)
  f=True
  for j in range(m):
    x=k[j]
    c=0
    for h in x:
      if s[h-1]=="0":c+=1
    if c%2!=p[j]:f=False
  if f:ans+=1
print(ans)

Submission status: Accepted

Solution code:
def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g

n,m = map(int,input().split())
bulb = []

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

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

# print(bulb)
# print(p)

ans = 0

for i in range(2**n):
    sw = bin(i)[2:].zfill(n)
    sw = list(map(int,list(sw)))
    #print(sw)
    on = 0
    for j in range(m):
        temp = 0
        for b in bulb[j]:
            if sw[b-1] == 1:
                temp += 1
        if temp % 2 == p[j]:
            on += 1
    if on == m:
        ans += 1

print(ans)

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()))
li = [[] for _ in range(N)]
for i in range(M):
    for ma in s[i]:
        li[ma - 1].append(i)
ans = 0
for i in range(2 ** N):
    l = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            for r in li[j]:
                l[r] ^= 1
    if l == p:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n,m=map(int,input().split())
a=[]
for i in range(m):
     a.append(list(map(int,input().split()))[1:])
p=list(map(int,input().split()))
x=[0,1]
x=list(product(x,repeat=n))
c=0
for k in x:
     f=True
     for i in range(m):
          a_=a[i]
          cnt=0
          for j in a_:
               cnt+=k[j-1]
          cnt%=2
          if cnt!=p[i]:
               f=False
               break
     c+=f
print(c)

Submission status: Accepted

Solution code:
# switchが10個以下


N,M = map(int,input().split())

sw = [[] for _ in range(M)]
for i in range(M):
  sw[i] = list(map(int,input().split()[1:]))
  

p = [int(x) for x in input().split()] # 不要

import itertools


answer = 0
for tpl in itertools.product([0,1],repeat=N):
  bl = True
  for i in range(M):
    # 電球iを計算
    s = sum([tpl[s-1] for s in sw[i]])
    if (s-p[i])%2 != 0:
      bl = False
      break
  if bl:
    answer += 1
print(answer)

Submission status: Accepted

Solution code:
def bi(x,n):
    o = [0]*n
    c = 0
    while x > 0:
        o[c] = x % 2
        c += 1
        x //= 2
    return o

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

c = 0
for j in range(2**N):
    o = bi(j,N)
    a = True
    for i in range(M):
        a = a and sum([o[x-1] for x in s[i]])%2 == p[i]
    c += a

print(c)

Submission status: Accepted

Solution code:
import itertools
N,M=map(int,input().split())
L=[list(map(int,input().split())) for i in range(M)]
P=list(map(int,input().split()))
ans=0
for item in itertools.product(range(2),repeat=N):
  if all(sum(item[x-1] for x in L[i][1:])%2==P[i] for i in range(M)):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N, M = map(int, input().split())
S = []
for i in range(M):
    inp = list(map(int, input().split()))
    S.append(inp[1:])
P = list(map(int, input().split()))

ans = 0
for perm in product([0, 1], repeat=(N + 1)):
    on_light = 0
    for i, s in enumerate(S):
        on_switch = 0
        for si in s:
            if perm[si] == 1:
                on_switch += 1

        if on_switch % 2 == P[i]:
            on_light += 1

    if on_light == M:
        ans += 1

print(ans // 2)

Submission status: Accepted

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

flag_list = []
for i in range(M):
    l=list(map(int,input().split()))
    flag = [False for s in range(N)]
    for j in l[1:]:
        flag[j-1]=True
    flag_list.append(flag)

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

count = 0
for i in range(2**N):
    
    flg=True
    for k in range(M):
        parit=0
        val = i
        for j in range(N):
            decode=val%2
            if flag_list[k][j]:
                parit+=decode
            val = val//2
        if parit%2!=p[k]:
            flg=False
            break
    if flg:
        count+=1

print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split(" "))
lines = []
for i in range(M):
    line = list(map(int, input().split(" ")))
    lines.append(set(line[1:]))

P = list(map(int, 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)

    flag = True
    for k, switches in enumerate(lines):
        if len(on & switches) % 2 == P[k]:
            pass
        else:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

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

def getMN():
    return list(map(int, input().split()))

def getlist():
    return list(map(int, input().split()))

n, m = getMN()

sws = []
for i in range(m):
    sw = getlist()
    sws.append(sw[1:])
ans = 0
mods = getlist()
# パターンごと
for i in range(2**n):
    flags = bin(i)[2:]
    flags = "0"*(n-len(flags)) + flags

    # 電球ごと
    right = 0
    for idx, sw in enumerate(sws):
        tmp = 0
        # スイッチごと
        for s in sw:
            if flags[s-1] == "1":
                tmp +=1

        if tmp % 2 == mods[idx]:
            right += 1

        if right == m:
            ans += 1
print(ans)

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()))
ret = 0
for b in range(1 << n):
    if all(sum((b >> (i - 1)) & 1 for i in s[j]) % 2 == p[j] for j in range(m)):
        ret += 1
print(ret)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split(" ")))
sws = []
for i in range(M):
    tmp = list(map(int, input().split(" ")))[1:]
    sws.append(sum(2 ** (i - 1) for i in tmp))
p = list(map(int, input().split(" ")))

count = 0
for i in range(2 ** N):
    for j in range(M):
        if bin(i & sws[j]).count("1") % 2 != p[j]:
            break
    else:
        count += 1
print(count)

Submission status: Accepted

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

def to_b(arr):
    ret = 0
    for i in arr:
        ret |= (1<<(i-1))
    return ret

def bc(num):
    return bin(num).count("1")

def main():
    N,M = [int(a) for a in input().split()]
    KS = [[int(a) for a in input().split()] for i in range(M)]
    P = [int(a) for a in input().split()]
    
    masks = [to_b(ks[1:]) for ks in KS]
    ans = 0
    for i in range(2**N):
        if all([bc(i&mask)%2==p for mask, p in zip(masks, P)]):
            ans+=1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = (int(x) for x in input().split())

S_arr_arr = []
for _ in range(M):
    S_arr = [int(x) for x in input().split()][1:]
    S_arr_arr.append(S_arr)
P_arr = [int(x) for x in input().split()]

ans = 0
for i in range(1 << N):
    success_flag = True
    for S_arr, P in zip(S_arr_arr, P_arr):
        s_count = 0
        for S in S_arr:
            if i & (1 << (S-1)) != 0:
                s_count += 1
        if s_count % 2 != P:
            success_flag = False
            break
    if success_flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s = []
for i in range(M):
    s.append([int(i) for i in input().split()])
p = [int(i) for i in input().split()]
ans = 0
for i in range(2 ** N):
    sw = [(i >> j) & 1 for j in range(N)]
    for k, e in enumerate(s):
        c = 0
        for l in e[1:]:
            c += sw[l - 1]
        if c % 2 != p[k]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for b in range(1<<N):
  ok = True
  for i in range(M):
    c = 0
    for t in s[i]:
      if b>>t&1:
        c += 1
    if c%2!=p[i]:
      ok = False
  if ok:
    ans += 1
print ans

Submission status: Accepted

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

kl = []
sl = []
for _ in range(m):
    line = list(map(int, input().split()))
    k = line[0]
    s = line[1:]
    kl.append(k)
    sl.append(s)
p = list(map(int, input().split()))

res = 0

for i in range(2**n):
    s = []
    for j in range(n):
        if i>>j&1==1:
            s.append(j+1)
    flag = True
    for mi in range(m):
        cnt = 0
        for si in s:
            if si in sl[mi]:
                cnt += 1
        if cnt%2!=p[mi]:
            flag = False
        if not flag:
            break
    if flag:
        res += 1

print(res)

Submission status: Accepted

Solution code:
import itertools


def main():
    N, M = map(int, input().split())
    connect = [set() for _ in range(N)]
    for i in range(M):
        tmp = list(map(int, input().split()))
        for s in tmp[1:]:
            connect[s-1].add(i)
    P = list(map(int, input().split()))
    ans = 0
    for x in itertools.product([True, False], repeat=N):
        cnt = [0] * M
        for i in range(N):
            if x[i]:
                for c in connect[i]:
                    cnt[c] += 1
        ok = True
        for i in range(M):
            if cnt[i] % 2 != P[i]:
                ok = False
        if ok:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,m = [int(i) for i in input().split()]
sw = []
for j in range(m):
    k,*l = [int(i)-1 for i in input().split()]
    sw.append(l)
p = [int(i) for i in input().split()]

#print(sw,p)
ans = 0
for i in range(2**n):
    ok=1
    for j in range(m): # スイッチ番号
        a=0
        for c in sw[j]:
                a += (1 if i&(2**c) else 0)
#        print(i,j,a)
        if a%2 != p[j]:
            ok=0
            break

    if ok:
        ans += 1
#        print(i)
            
print(ans)

Submission status: Accepted

Solution code:
def count(state: int, ss: list):
    res = 0
    for s in ss:
        res += ((state >> s) & 1)
    return res


assert count(0b011, [0, 1]) == 2
assert count(0b011, [2]) == 0


def is_on(state: int, p: int, ss: list):
    return count(state, ss) % 2 == p


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

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

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

    cnt = 0
    for state in range(0, 2**N):
        cnt += all(map(lambda x: is_on(state, x[0], x[1]), zip(ps, sss)))
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd
readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(' ')]

MOD = 2  # type: int


def main():
    N, M = readIntN()
    ks = []
    ss = []
    for i in range(M):
        tmp = readIntN()
        ks.append(tmp[0])
        ss.append(tmp[1:])
    ps = readIntN()

    qs = [] 
    for s in ss:
        q = 0
        for c in s:
            q |= (1 << (c - 1))
        qs.append(q)

    ret = 0
    for i in range(1 << N):
        ok = True
        for q, p in zip(qs, ps):
            ok &= (bin(i & q).count('1') % MOD) == p
        if ok:
            ret += 1
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# from sys import exit
N, M = [int(n) for n in input().split()]
ss = [0 for i in range(M)]
for i in range(M):
    ss[i] = set([int(n)-1 for n in input().split()][1:])
p = [int(n) for n in input().split()]
ans = 0
for pt in range((1 << N)):#1 == 線あり 0 == 線なし　とする
    each = [0]*M
    for i in range(N):
        if (1 << i) & pt:
            for iss in range(len(ss)):
                if i in ss[iss]:
                    each[iss] +=1
    OK = True

    for i in range(len(each)):
        if each[i]%2 != p[i]:
            OK = False
    if OK:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    N, M = map(int, line_input())
    ks = [[int(i) for i in line_input()] for j in range(M)]
    p = [int(i) for i in line_input()]
    ans = 0
    for i in range(2 ** N):
        onoff = str(format(i, "b").zfill(N))
        for m in range(M):
            onnum = 0
            for k in ks[m][1:]:
                if onoff[k-1] == "1": onnum += 1
            if onnum % 2 != p[m]: break
        else: ans += 1
    print(ans)
        
    return 0
  
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

sws = []

for _ in range(M):
	items = list(map(int, input().split(" ")))
	sws.append([items[i + 1] - 1 for i in range(items[0])])

plist = list(map(int, input().split(" ")))

def check(sw):
	for i in range(M):
		items = sws[i]
		c = 0
		for j in items:
			c += sw[j]
		if c % 2 != plist[i]:
			return False
	return True

f = "{:0" + str(N) + "b}"
count = 0
for i in range(2 ** N):
	sw = [s == "1" for s in f.format(i)]
	if check(sw):
		count += 1
print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ks = [list(map(int,input().split())) for _ in [0]*M]
*p,= map(int,input().split())
ans = 0
for i in range(1<<N):
    S = [(i&(1<<j))>0 for j in range(N)]
    tmp = 0
    for j,ks1 in enumerate(ks):
        k,*s = ks1
        tmp = sum(S[c-1] for c in s)
        if tmp%2 != p[j]:break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append([int(i) for i in input().split()[1:]])
p=[int(i)*(-2)+1 for i in input().split()]
ans=0
for state in range(2**n):
    chk=True
    for j in range(m):
        ll=l[j]
        test=1
        for i in ll:
            test*=-2*((state>>(i-1))&1)+1
        if test!=p[j]:
            chk=False
    if chk:
        ans+=1
print(ans)

Submission status: Accepted

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

from itertools import product

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

ans = 0

for ss in product((0, 1), repeat=n):
    for st, par in zip(s, p):
        if (sum(ss[sti] for sti in st) & 1) != par:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = [0]*N

for i in range(M):
    s = list(map(int, input().split()))[1:]
    for s_ in s:
        S[s_-1] ^= 1 << i
P_ = list(map(int, input().split()))
P = 0
for i, p in enumerate(P_):
    P ^= p << i
#print(list(map(bin,S)))
#print(P)
ans = 0
for i in range(1<<N):
    a = P
    for j, s in enumerate(S):
        if i>>j & 1:
            a^=s
    if a==0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
d=[[0 for i in range(n)]for i in range(m)]
for i in range(m):
    x=list(map(int,input().split()))
    for j in range(1,x[0]+1):
        d[i][x[j]-1]=1
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    for j in range(m):
        tmp=0
        for k in range(n):
            if (1<<k)&i:
                tmp+=d[j][k]
        if tmp%2!=p[j]:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N, M = map(int, input().split())
S = []
for _ in range(M):
    _, *s = map(int, input().split())
    S.append(s)
P = [int(s) for s in input().split()]

cnt = 0
for ss in product([0, 1], repeat=N):
    for i in range(M):
        if sum(ss[sj - 1] for sj in S[i]) % 2 != P[i]:
            break
    else:
        cnt += 1

print(cnt)

Submission status: Accepted

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

KS = [list(map(int, input().split())) for _ in range(M)]
S = [[KS[m][i]-1  for i in range(1, len(KS[m]))] for m in range(M)]
p = list(map(int, input().split()))

def check(l):
    for m in range(M): # denkyu
        tmp_sum = 0
        for switch in S[m]:
            if l[switch]:
                tmp_sum +=1
        if tmp_sum%2 != p[m]:
            return False
    return True



ans = 0
for l in itertools.product([0,1],repeat=N):
    if check(l):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

n, m = list(map(int, input().split()))
stl = [[] for _ in range(n)]

for i in range(m):
    a = input().split()
    for x in a[1:]:
        stl[int(x)-1].append(i)

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

count = 0
for comb in itertools.product([True, False], repeat=n):
    cs = [0 for _ in range(m)]
    for i, t in enumerate(comb):
        if t:
            for l in stl[i]:
                cs[l] += 1

    if all([cs[i] % 2 == ps[i] % 2 for i in range(m)]):
        count += 1

print(count)

Submission status: Accepted

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

#import numpy as np
#import scipy, scipy.special

# Python 3 modules: https://docs.python.org/3/library/

import math, itertools, operator
from math import *
from math import factorial as fact
from operator import itemgetter, attrgetter
from itertools import permutations, combinations
from functools import reduce
# Use scipy for stats: https://docs.scipy.org/doc/scipy/reference/stats.html
# Before Python 3.5
from fractions import gcd

inf = float('inf')

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

def perm(a, b):
    import scipy.special
    return scipy.special.perm(a, b, exact = True)

def comb(a, b):
    import scipy.special
    return scipy.special.comb(a, b, exact = True)

def dfact(n):
    import scipy.special
    return scipy.special.factorial2(n, exact = True)

def prod(l):
    return reduce(operator.mul, l)

def input_ints(inp = input, sep = ' ', conv = int):
    return list(map(conv, inp().split(sep = sep)))

################################################################################

N, M = input_ints()
Smask = []
for i in range(M):
    l = input_ints()
    m = 0
    for j in l[1:]:
        m |= (1 << (j - 1))
    Smask.append(m)
P = input_ints()

def popcount(x):
    return bin(x).count('1')

cnt = 0
for i in range(1 << N):
    flag = True
    for j in range(M):
        mask = Smask[j]
        if popcount(i & mask) % 2 != P[j]:
            flag = False
            break
    if flag:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))

N, M = inpl()
T = [[] for _ in range(N)]
for i in range(M):
    _, *S = inpl()
    for s in S:
        T[s-1].append(i)
P = inpl()

ans = 0
for x in range(2**N):
    Q = [0]*M
    for i in range(N):
        if (x >> i) & 1:
            for t in T[i]:
                Q[t] += 1
    ans += P == [q%2 for q in Q]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, KS, P):

    ans = 0
    for s in product((0, 1), repeat=N):
        for j, ks in enumerate(KS):
            k = ks[0]
            c = 0
            for i in range(1, k+1):
                c += s[ks[i]-1]
            if c % 2 != P[j]:
                break
        else:
            ans += 1
    return ans


def main():
    N, M = read_int_n()
    KS = [read_int_n() for _ in range(M)]
    P = read_int_n()
    print(slv(N, M, KS, P))


if __name__ == '__main__':
    main()