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())
switch = []
for _ in range(M):
  tmp = list(map(int, input().split()))
  switch.append(tmp[1:])
p = list(map(int, input().split()))

from itertools import product
candidate = list(product([0,1], repeat=N))

ans = 0
for cand in candidate:
  flag = True
  for idx, snum in enumerate(switch):
    tmp = 0
    for s in snum:
      tmp += cand[s-1]
    if p[idx] != tmp%2:
      flag = False
      break
  if flag:
    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()))
ans=0
for i in range(2**n):
    tmp=[]
    for j in range(n):
        if (i>>j)&1:
            tmp.append(j+1)
    for k in range(m):
        if len(set(tmp)&set(s[k]))%2!=p[k]:
            break
    else:
        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()))
ans=0

for i in range(2**n):
    tmp=[]
    cnt=[0]*n
    for j in range(n):
        if (i>>j)&1:
            tmp.append(j+1)
    for k in range(m):
        if len(set(tmp)&set(s[k]))%2!=p[k]:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
n, m = list(map(int, input().split()))
s = [list(map(int, input().split())) for i in range(m)]
pl = list(map(int, input().split()))
ans = 0
for bits in product([0, 1], repeat=n):
    flag = True
    for i, ss in enumerate(s):
        cnt = 0
        for sss in ss[1:]:
            if bits[sss-1] == 1:
                cnt += 1
        if not cnt % 2 == pl[i]:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l = []
for i in range(1 << n):
    tmp = str(bin(i))[2:]
    l.append(tmp.zfill(n))
K = [list(map(int,input().split())) for _ in range(m)]
P = list(map(int,input().split()))
#print(P)
ans = 0
#print("----")
for i in range(len(l)):
    #スイッチの状態l[i]
    #付いている電球のリストO
    O = []
    for j in range(m):
        #電球のきになるすいっちの数K[j][0]
        ON = 0
        for ii in range(K[j][0]): #スイッチのリスト
            if l[i][K[j][ii+1] - 1] == "1":
                ON += 1
        if ON % 2 == P[j]:
            O.append(1)
        else:
            O.append(0)
    if sum(O) == m:
        #print(l[i])
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    onoffs = [int(j) for j in list(bin(i)[2:].zfill(n))]
    Flag = True
    for lamp in range(m):
        k = a[lamp][0]
        info = [l - 1 for l in  a[lamp][1:]]
        tmp = 0
        for index in info:
            if onoffs[index]:
                tmp += 1
        if tmp % 2 != p[lamp]:
            Flag = False
            break
    if Flag:
        ans += 1
print(ans)

Submission status: Accepted

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

ans=0
for i in range(1<<n):
  for k in range(m):
    sw=0
    for j in range(n):
      if (i>>j)&1 and j+1 in S[k]:
        sw+=1
    if sw % 2 != p[k]:
      break
  else:
    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()))

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(int, input().split())
switches = []
for _ in range(m):
    x = list(map(int, input().split()))[1:]
    temp = []
    for i in range(n):
        if i + 1 in x:
            temp.append(1)
        else:
            temp.append(0)
    switches.append(temp)
p = list(map(int, input().split()))

ans = 0
for on_off in product([1, 0], repeat=n):
    flag = 1
    for i, switch in enumerate(switches):
        cnt = 0
        for x, y in zip(on_off, switch):
            if x == 1 and y == 1:
                cnt += 1
        if cnt % 2 != p[i]:
            flag = 0
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

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

ans=0
for i in range(2**N):
    isOK=True

    for j in range(M):
        sum=0
        for x in s[j]:
            sum+=(i>>x)&1
        
        if sum%2!=p[j]:
            isOK=False
    
    if isOK:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,M = MI()
S = [LI() for _ in range(M)]
P = LI()

ans = 0
for i in range(1 << N):
    d = defaultdict(int)
    for j in range(N):
        if (i >> j) & 1:
            d[j] = 1
    for k in range(M):
        if sum(d[l-1] for l in S[k][1:]) % 2 != P[k]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[]
for i in range(m):
  inp=list(map(lambda x:int(x)-1,input().split()))
  s.append(inp[1:])
p=list(map(int,input().split()))
c=0
for i in range(2**n):
  st=[]
  for j in range(m):
    t=0
    for k in s[j]:
      if i&(2**k):
        t^=1
    st.append(t)
  if p==st:
    c+=1
print(c)

Submission status: Accepted

Solution code:
import copy

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

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


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

# 全bit探索
for i in range(2**(n)):
    lst = copy.deepcopy(s) # list のコピーにはcopy.copy()を用いる(2重配列以上はdeepcopy()を用いる)
    flag = True
    for j in range(n):
        if i >> j & 1 == 1:
            for k in lst:
                for l in range(2, k[1]+2):
                    if k[l]-1 == j:
                        k[0] += 1
    # 偶数奇数が合えば ans+=1
    for b in range(len(p)):
        if p[b] != lst[b][0]%2:
            flag = False
    if flag == True:
        ans +=1

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

for j in range(2**N):
    j=bin(j)
    j=str(j)
    j=j[2:]
    while len(j)!=N:
        j="0"+j
    flash=0
    for k in range(M):
        temp=0
        for l in range(li[k][0]):
            if j[li[k][l+1]-1]=="1":
                temp+=1
        if temp%2==p[k]:
            flash+=1
    if flash==M:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x):
        self.setdefault(x,0)
        self[x] += 1
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]

N,M = mint()
S = [lint() for _ in range(M)]
P = lint()
ans = 0
for k in range(1<<N):
    tmp = [(k>>i)&1 for i in range(N)]
    now = True
    for s,p in zip(S,P):
        on = 0
        for i in s[1:]:
            on += tmp[i-1]
        if on%2!=p:
            now = False
            break
    ans = ans+1 if now else ans
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()))


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

print(ans)

Submission status: Accepted

Solution code:
# 与えられた数値の桁数と桁値の総和を計算する.
def calc_digit_sum(num):
    digits = sums = 0
    while num > 0:
        digits += 1
        sums += num % 10
        num //= 10
    return digits, sums


n, m = map(int, input().split())
arr = []
for _ in range(m):
    tmp = list(map(int, input().split()))
    arr.append(tmp[1:])
prr = list(map(int, input().split()))

answer = 0
for switches in range(2 ** n):
    light_up = 0
    for light in range(m):
        on = 0
        for shift in range(n):
            if (switches >> shift) & 1 and (shift + 1) in arr[light]:
                on += 1

        if on % 2 == prr[light]:
            light_up += 1

    if light_up == m:
        answer += 1

print(answer)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import copy

def dfs(i,lst):
    global ans
    if i==n:
        ans.append(lst)
        return
    tmp1 = copy.copy(lst)
    tmp1.append(0)
    dfs(i+1,tmp1)
    tmp2 = copy.copy(lst)
    tmp2.append(1)
    dfs(i+1,tmp2)

n,m = map(int,input().split())
ans = []
tmp = [0]
dfs(0,tmp)
#print(ans)
s = []
k = []
for i in range(m):
    tmp = list(map(int,input().split()))
    k.append(tmp[0])
    s.append(tmp[1:])
p = list(map(int,input().split()))
#print(k)
#print(s)
#print(p)
cnt = 0
for i in range(len(ans)):
    cnt_i = 0
    for mi in range(m):
        sum_s = 0
        for ki in range(len(s[mi])):
            sum_s += ans[i][s[mi][ki]]
        if sum_s%2==p[mi]:
            cnt_i += 1
    if cnt_i==m:
        cnt += 1
print(cnt)

Submission status: Accepted

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

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

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

    ans = 0

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

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

    print(ans)

if __name__ == '__main__':
    abc128_c()

Submission status: Accepted

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

s_list = []
for i in range(M):
    s_list.append(list(map(int, input().split())))
P_list = list(map(int, input().split()))

ans = 0
for i in range(1 << N):
    S = ["OFF" for _ in range(N)]
    for j in range(N):
        if (i >> j) & 1 == 1:
            S[j] = "ON"
    m = 0
    while True:
        cnt = 0
        for s in range(1, len(s_list[m])):
            if S[s_list[m][s]-1] == "ON":
                cnt += 1
        if cnt % 2 != P_list[m]:
            break
        m += 1
        if m == M:
            break
    if m == M:
        ans += 1
print(ans)

Submission status: Accepted

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

X = [[0]*N for _ in range(M)]
for i in range(M):
    u = [int(x) for x in input().split()]
    k = u[0]
    for j in range(1, k + 1):
        X[i][u[j] - 1] = 1

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

ans = 0
for b in range(2**N):
    q = [0]*M
    for i in range(M):
        for j in range(N):
            if (b >> j) & 1:
                q[i] = (q[i] + X[i][j]) % 2
    if q == p:
        ans += 1

print(ans)

Submission status: Accepted

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

def get_connected_switches():
    # k s1 s2 .. sn
    lst = list(map(int, input().split()))
    lst.pop(0) # k is not use
    return list(map(lambda d: 1<<(d-1), lst ))

# cs: connected switches
cs = [get_connected_switches() for _ in range(m)]
ps = list(map(int, input().split()))

# bit全探索(0: すべてoffは不要)
ans = 0
# on: 0:消えてる、1:点いてる
# 10: 1 2  3   4 
# 0b: 1 10 11, 100..
for on in range(2**n):
    ok = True
    for i in range(m):
        ct = 0
        for s in cs[i]:
            if s&on: ct += 1
        if ct%2 != ps[i]:
            ok = False
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
bulbs = []
ans = 0
for i in range(m):
    c = tuple(map(int, input().split()))
    bulbs.append(c[1:])
p = list(map(int, input().split()))
for i in range(2 ** n):
    cnt = 0
    for j, bulbs_sub in enumerate(bulbs):
        switch_on = 0
        for l in bulbs_sub:
            if i >> (l-1) & 1:
                switch_on += 1
        if switch_on % 2 == p[j]:
                cnt += 1
    if cnt == m:
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

# cs: connected switches
cs = [list(map(int, input().split())) for _ in range(m)]
ps = list(map(int, input().split()))

# bit全探索(0: すべてoffは不要)
ans = 0
# on: 0:消えてる、1:点いてる
# 10: 1 2  3   4 
# 0b: 1 10 11, 100..
for on in range(2**n):
    # bin: バイナリ文字列に変換
    # 3 -> '0b11'
    # rust で右0埋め
    patern = bin(on)[2:].rjust(n, '0')
    ok = True

    for i in range(m):
        ct = 0
        for j in range(cs[i][0]):
            if patern[cs[i][j+1] - 1] == '1':
                ct += 1
        if ct%2 != ps[i]:
            ok = False
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M = map(int, input().split())

connection = {}
for i in range(M):
    line = list(map(int, input().split()))
    s = line[1:]
    connection[i] = s

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

ans = 0
for i in range(2**N):
    isSwitchOn = [0 for _ in range(N)]
    for j in range(N):
        if (i >> j) & 1:
            isSwitchOn[j] = 1

    onBulbs = 0
    for j in range(M):
        count = 0
        for switch in connection[j]:
            if isSwitchOn[switch-1]:
                count += 1

        if count % 2 == P[j]:
            onBulbs += 1

    if onBulbs == M:
        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()))
ans = 0

for i in range(2**n):
    judge = True
    switch = [('off') for _ in range(n)]
    for j in range(len(switch)):
        if (i >> j) & 1:
            switch[j] = 'on'
    for k in range(m):
        count = 0
        for l in range(ks[k][0]):
            if switch[ks[k][l+1]-1] == 'on':
                count += 1
        if count % 2 != p[k]:
            judge = False
            break
    if judge == True:
        ans += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = None
M = None
S = []
P = []

if __name__ == "__main__":
    N, M = map(int, input().split())
    for _ in range(M):
        row = list(map(int, input().split()))[1:]
        S.append(row)
    P = list(map(int, input().split()))
    ans = 0
    for bit in range(1<<N):
        on_switches = []
        light = 0
        for i in range(N):
            if bit>>i&1:
                on_switches.append(i)
        for i in range(M):
            cnt = 0
            for s in S[i]:
                for on_switch in on_switches:
                    if s==on_switch+1:
                        cnt += 1
            if cnt%2==P[i]:
                light += 1
        if light==M:
            ans += 1
    print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2 ** n):
    t = ['off'] * n
    x = i
    j = 0
    while x > 0:
        if x % 2 != 0:
            t[j] = 'on'
        x = x // 2
        j += 1
    flg = True
    for j in range(m):
        z = 0
        for k in range(1,s[j][0]+1):
            if t[s[j][k]-1] == 'on':
                z += 1
        if z % 2 != p[j]:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
bulbs = []
for _ in range(M):
    b = tuple(map(int, input().split()))
    bulbs.append(b[1:])
P = list(map(int, input().split()))

ans = 0
for switch in range(2**N):
    check = [False] * M
    for i ,bulb in enumerate(bulbs):
        count = 0
        for b in bulb:
            if switch >> (b-1) & 1:
                count += 1
        if count % 2 ==P[i]:
            check[i] = True
        else:
            check[i] = False
    if all(check):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
K = []
S = []
for i in range(M):
    k = 0
    s = []
    k, *s = map(int,input().split())
    K.append(k)
    S.append(s)
P = list(map(int,input().split()))
res = 0
for bit in range(1 << N):
    judge = True
    for i in range(M):
        cnt = 0
        for s in S[i]:
            cnt += (bit >> s-1) & 1
        if cnt % 2 != P[i]:
            judge = False
            break
    if judge:
        res += 1
print(res)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
K = []
S = []
for i in range(M):
    k = 0
    s = []
    k, *s = map(int,input().split())
    K.append(k)
    S.append(s)
P = list(map(int,input().split()))
res = 0
for bit in range(1 << N):
    judge = True
    for i in range(M):
        cnt = 0
        for s in S[i]:
            cnt += (bit >> s-1) & 1
        if cnt % 2 != P[i]:
            judge = False
    if judge:
        res += 1
print(res)

Submission status: Accepted

Solution code:
N, M = list(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):
  for j in range(M):
    t = 0
    for k in range(1, ks[j][0] + 1):
      if i >> (ks[j][k] - 1) & 1:
        t += 1
    if t % 2 != p[j]:
      break
  else:
    ans += 1

print(ans)

Submission status: Accepted

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

#ON/OFFのパターン
for i in range(2 ** n) :
    lis = []
    for j in range(len(bin(2 ** n)) - 3) :
        if (i >> j) & 1 :
            lis.append(1)
        else:
            lis.append(0)
    
    s_lis.append(lis)

#各電球の接続
b_lis = []
for k in range(m) :
    b_lis.append(list(map(int, input().split())))

#点灯条件
light = list(map(int, input().split()))

#各電球の合計
cnt = 0
for s in s_lis :
    c_lis = []
    for b in b_lis :
        c = 0
        for x in range(b[0]) :
            c += s[b[x + 1] - 1]
        c_lis.append(c)
    
    c_lis = list(map(lambda y : y % 2, c_lis))
    if c_lis == light :
        cnt += 1

print(cnt)

Submission status: Accepted

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

for i in range(M):
  K_list.append(tuple(map(int,input().split())))

p_list = list(map(int,input().split()))
################################################
count = 0
for i in range(2**N):
  switch_list = ["OFF" for _ in range(N)]
  for j in range(N):
    if i>>j & 1:
      switch_list[N-1-j] = "ON"
  #print("switch_list",switch_list)
  
  light_ON = 0
  for k in range(M):
    ON_switch = 0
    for sw in range(K_list[k][0]):
      #print(K_list[k][sw+1])
      if switch_list[K_list[k][sw+1] - 1] == "ON":
        #print("switch work") 
        ON_switch += 1
    #print("ONswitch",ON_switch)
    if ON_switch % 2 == p_list[k]:
      #print("lightON")
      light_ON += 1
  
  if light_ON == M:
    #print("all lamp light on in situation",switch_list)
    count += 1
    
print(count)

Submission status: Accepted

Solution code:
from itertools import product


n,m = map(int, input().split())

switch = []

for i in range(m):
  k, *s = map(int, input().split())
  s = list(s)
  switch.append(s)

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

for i in product(range(2), repeat=n):
  flag = True
  for s in range(m):
    cnt = 0
    for t in switch[s]:
      if i[t-1] == 1:
        cnt += 1
    if cnt % 2 != p[s]:
      flag = False
      break
  if flag == True:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

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

Submission status: Accepted

Solution code:
def abc128c_switches():
    import itertools
    n, m = map(int, input().split())
    s = []
    for _ in range(m):
        v = list(map(int, input().split()))
        v = v[1:]
        s.append(v)
    p = list(map(int, input().split()))
    pattern = itertools.product([0,1], repeat=n)
    result = 0
    for pat in pattern:
        cnt = 0
        for i in range(m):
            total = 0
            for j in s[i]:
                if pat[j-1] == 1:
                    total += 1
            if total %2==p[i]:
                cnt +=1
        if cnt == m:
            result += 1
    print(result)

abc128c_switches()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[[0]*10 for _ in range(m)]
for i in range(m):
    k=list(map(int,input().split()))
    for j in range(1,k[0]+1):
        s[i][10-k[j]]=1
import numpy as np
s=np.asarray(s)
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    binst=format(i,'010b')
    l=list(map(int,list(binst)))
    l=np.asarray(l)
    on=s&l
    onsum=np.sum(on,axis=1)%2
    err=0
    for j in range(m):
        if onsum[j]!=p[j]:
            err=1
            break
    if err==0:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

onoff = list(product([0, 1], repeat = N))

ans = 0
for i in onoff:
    cnt = 0
    for ind, s in enumerate(S):
        state = 0
        for o in s:
            state += i[o-1]
        if state % 2 == p[ind]:
            cnt += 1
    if cnt == M:
        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()))
    s.append(tmp[1:])
p = list(map(int,input().split()))

ans = 0
for i in range(2**n):
    for j in range(m):
        count = 0
        check = True
        for k in s[j]:
            if (i >> (k-1)) & 1:
                count += 1
        if count % 2 != p[j]:
            check = False
            break
    if check:
        ans += 1
print(ans)

Submission status: Accepted

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