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())
l=[]
for i in range(m):
    x=list(map(int,input().split()))
    l.append(x)
p=list(map(int,input().split()))

sum=0
for i in range(2**n):
    sum1=0
    ll = [0] * (n)
    for j in range(n+1):
        if i >> j & 1:
            ll[j] = 1
    for h in range(m):
        k=l[h][0]
        total=0
        for x in range(1,k+1):
            total+=ll[l[h][x]-1]
        if total%2==p[h]:
            sum1+=1
    if sum1==m:
        sum+=1
print(sum)

Submission status: Accepted

Solution code:
from itertools import combinations
def is_lighted(re):
    for i in range(m):
        total = 0
        for each in ls[i]:
            if each in re:
                total+=1
        if total%2 != p[i]:
            return 0
    return 1

n,m = [int(x) for x in input().split()]
ls = []
ans = 0
for i in range(m):
    ki = [int(x) for x in input().split()]
    ls.append(ki[1:])
p = [int(x) for x in input().split()]

t = [i for i in range(1,n+1)]
for i in range(n+1):
    for each in combinations(t,i):
        if is_lighted(each):
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(M)]
P = list(map(int,input().split()))

res = 0
for i in range(2**N):
    s = bin(i)[2:].zfill(N)
    l_count = 0
    for p,x in zip(P,X):
        s_count = 0
        for si in x[1:]:
            if s[si-1]=='1':
                s_count += 1
        if s_count%2 == p:
            l_count += 1
    if l_count == M:
        res += 1
print(res)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

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

def main():
  n,m=LI()
  l2=[]
  for _ in range(m):
    l2.append(LI())

  l3=LI()

  l=[]
  a=len(bin(1<<n))-3
  for i in range(1<<n):
    l.append(str(bin(i))[2:].zfill(a))

  cnt=0
  for x in l:
    x=list(x)

    f=True
    for i in range(len(l2)):

      y=l2[i]
      c=0

      for a in y[1:]:
        c+=int(x[a-1])

      # print(c,l3[i])
      if c%2==l3[i]:
        pass
      else:
        f=False
        break

    if f:
      cnt+=1

  return cnt

print(main())

Submission status: Accepted

Solution code:
import itertools
N,M = map(int, input().strip().split(' '))
sw = [[0 for _ in range(M)] for __ in range(N)]
for m in range(M):
  col = list(map(int, input().strip().split(' ')))[1:]
  for i in col:
    sw[i-1][m] = 1
p = list(map(int, input().strip().split(' ')))

ok_count = 0
for c in itertools.product([0,1], repeat=N):
  lamp = [0 for _ in range(M)]
  for i in range(N):
    if c[i]:
      lamp = [l+s for l,s in zip(lamp, sw[i])]
  lamp = [l%2 for l in lamp]
  if lamp == p:
    ok_count += 1
print(ok_count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=[]
ans=0
for i in range(m):
    l=list(map(int,input().split()))
    x.append(l)
p=list(map(int,input().split()))
for i in range(2**n):
    frag=True
    for j in range(m):
        count=0
        for a in range(1,x[j][0]+1):
            s=x[j][a]
            count+=(i>>(s-1))&1
        if count%2!=p[j]:
            frag=False
    if frag:
        ans+=1
print(ans)

Submission status: Accepted

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


def count1(n):
    return bin(n).count("1")


def tobin(ns):
    rv = 0
    for n in ns:
        rv += 1 << (n-1)
    return rv


def solv(n, m, ss, z1s):
    ss = list(map(tobin, ss))
    ans = 0
    for on in range(2**n):
        # print('on=', on)
        ok = 1
        for i in range(m):
            # print('ss[i], on, z1s', ss[i], on, z1s[i])
            if count1(ss[i] & on) % 2 != z1s[i]:
                ok = 0
                break
        ans += ok
    return ans


if __name__ == '__main__':

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

    ss = []
    for _ in range(m):
        s = list(map(int, input().split()))
        s = s[1:]
        ss.append(s)

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

    ans = solv(n, m, ss, z1s)
    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()))

# print(N, M)
# print(KS)
# print(P)

ans = 0
for i in range(pow(2, N)):
    bin_i = str(bin(i))[2:]
    if len(bin_i) != N:
        bin_i = '0' * (N - len(bin_i)) + bin_i
    # print(bin_i)

    # bin_i はi番目のスイッチの状態

    flg = True
    # 各電球でループする
    for i, ks in enumerate(KS):
        # print(ks)
        cnt = 0
        for j in ks:
            if bin_i[j-1] == '1':
                cnt += 1
        if cnt % 2 != P[i]:
            flg = False
            break

    if flg:
        ans += 1


print(ans)

Submission status: Accepted

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

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

S = [list(map(int, input().split())) for i in range(M)]
P = list(map(int, input().split()))

def check_S(state, S, P):
    for s, p in zip(S, P):
        count = 0
        for si in s[1:]:
            if state[si-1] == '1':
                count += 1 
        if count%2 != p:
            return False
    return True

ans = 0
for i in range(2**N):
    state = list(format(i, '0'+format(N)+'b'))
    if check_S(state, S, P):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import *
from functools import *
from itertools import *
import operator as op

def main():
    #n = int(input())
    n, m = map(int, input().split())
    #xs = list(map(int, input().split()))
    #xs = [ input().split() for _ in range(n) ]
    xs = [ list(map(int, input().split()))[1:] for _ in range(m) ]
    ps = list(map(int, input().split()))
    def pick(i, ofst):
        return (i >> ofst) & 1
    ans = 0
    for i in range(2**n):
        if any([ p ^ reduce(op.xor, [ pick(i, x-1) for x in xs[j]]) for j, p in enumerate(ps) ]):
            pass
        else:
            ans += 1
            pass
        pass
    print(ans)
    pass


if __name__ == "__main__":
    main()
    pass

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
A = []
for i in range(m):
    B = list(map(int, input().split()))
    A.append(B[1:])
P = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    Q = []
    u = i
    for j in range(n):
        Q.append(u%2)
        u//=2
    pop = True
    for j in range(m):
        u = 0 
        for k in A[j]:
            if (Q[-k]==1):
                u+=1
        if ((u%2) != (P[j])):
            pop = False
            #print("!", u, P[j], j, i)
            break
    if (pop):
        ans+=1
print(ans)

Submission status: Accepted

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

for h in range(0,2**n):
    c = [0]*n
    for s in range(0,n):
        if (h >> s)% 2 == 1:
            c[s] = 1
    for i in range(0,m):
        check = 0
        for j in range(1,k[i][0]+1):
            if c[k[i][j]-1] == 1:
                check += 1
        if check%2 != p[i]:
            break
    else:
        counter += 1

print(counter)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m= map(int, input().split())
ks=[]
for i in range(m):
  ks.append(list(map(int, input().split())))
p= list(map(int, input().split()))
k=[0]*n
count=0
for i in range(2**n):
  for j in range(n):
    k[j]=i%2
    i=i//2
  for a in range(m):
    sm=0
    for j in range(ks[a][0]):
      sm = sm + k[ks[a][j+1]-1]
    if sm%2 != p[a]:
      break
  else:
    count = count + 1
print(count)

Submission status: Accepted

Solution code:
# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

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

S = [[0] * N for _ in range(M)]
for m in range(M):
    s = [int(x) for x in input().split()]
    for s1 in s[1:]:
        S[m][s1 - 1] = 1

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

cnt = 0
for i in range(2 ** N):
    tmp = True
    for j in range(M):
        c = 0
        for k in range(N):
            if i & (1 << k):
                c += S[j][k]

        if c % 2 != P[j]:
            tmp = False

        # bit = format(i, "08b")
        # print("i(bit):{}, j:{}, c:{},c%2:{}, P[j]:{}".format(bit, j, c, c % 2, P[j]))
    # print("---")

    if tmp == True:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
#!venv/bin/python
 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 

N, M = [ int(x) for x in input().split() ]
KS = []
for _i in range(M):
    KS.append([ int(x) for x in input().split() ])
P = [ int(x) for x in input().split() ]

all = [[0,],[1,]]

def add_right(list):
    list0 = [ l + [0,] for l in list ]
    list1 = [ l + [1,] for l in list ]
    list0.extend(list1)
    return list0

for _i in range(N-1):
    all = add_right(all)

ans = 0
d_ans = []
for state in all:
    l_num = -1
    for ks in KS:
        l_num += 1
        switches = ks[1:]
        on = 0
        for s in switches:
            if state[s-1] == 1:
                on += 1
        if on % 2 != P[l_num]:
            break
    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product

N, M = map(int, input().split())
lights = []
for _ in range(M):
    t = list(map(int, input().split()))
    lights.append(t[1:])
cond = list(map(int, input().split()))
ans = 0
for pat in product([True, False], repeat=N):
    flag = True
    for c, l in zip(cond, lights):
        if sum([pat[idx - 1] for idx in l]) % 2 != c:
            flag = False
    if flag:
        ans += 1
print(ans)

Submission status: Accepted

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

last_bin = (2 ** N)
switches = [[int(i) for i in input().split()][1:] for _ in range(M)]
ps = [int(i) for i in input().split()]

# print('{:010b}'.format(last_bin))

counter = 0
score = 0
while last_bin != counter:
    state = '{:010b}'.format(counter)
    # print(state)
    okFlag = True
    for i in range(len(switches)):
        # print(switches[i])
        states = [state[-1 * x] for x in switches[i]]
        # print(states)
        if states.count('1') % 2 == ps[i]:
            pass
        else:
            okFlag = False
            break
    if okFlag:
        score += 1
    counter += 1

print(score)

Submission status: Accepted

Solution code:
n, m = (int(v) for v in input().split())
lamps = [tuple([int(e) for e in input().split()[1:]]) for _ in range(m)]
conds = [int(v) for v in input().split()]

count = 0
for state in range(2**n):
    flag = True
    for cond, lamp in zip(conds, lamps):
        mask = 0
        for sw in lamp:
            mask += 2**(sw-1)
        masked = state & mask
        bit = 0
        for _ in range(n):
            bit += masked % 2
            masked >>= 1
        if (bit + cond) % 2 != 0:
            flag = False
            break
    if flag:
        count += 1
print(count)

Submission status: Accepted

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, M = read_ints()
# グラフ構造が与えられたとき
from collections import defaultdict
light = []
for i in range(M):
    S = read_ints()
    light.append([s-1 for s in S[1:]])
P = read_ints()

# print(light)
n = N

ans = 0  # すべての電球がつくパターン
for i in range(1 << n):
    # スイッチの付き方のパターンを2進数で全探索
    for l_idx, l in enumerate(light):
        # 個々のlightについて探索
        ltmp = 0  # ついているスイッチの数
        for j in l:
            if (i >> j) % 2:
                # もしビットが1だったらswitch on
                ltmp += 1
        if ltmp % 2 != P[l_idx]:
            # 電球がつかなかった
            break
    else:
        ans += 1


print(ans)

Submission status: Accepted

Solution code:
# 問題C
n, m = map(int, input().split())

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

ok_list = list(map(int, input().split()))
counter = 0
for i in range(2**n):
    tmp_counter = 0
    for light_num in range(len(switch_list)):
        light_status = ok_list[light_num]
        for switch in switch_list[light_num]:
            light_status += int(i&(1<<(switch-1))>0)
        if(light_status % 2 == 0):
            tmp_counter += 1
    if(tmp_counter == m):
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
N, M = [int(_) for _ in input().split()]
KS = [[int(_) for _ in input().split()] for _ in range(M)]
P = [int(_) for _ in input().split()]
ans = 0
for s_bit in range(1 << N):
    S = []
    while s_bit:
        S += [s_bit % 2]
        s_bit //= 2
    S = [0] + S + [0] * (N - len(S))
    ok = True
    for i in range(M):
        if sum([S[_] for _ in KS[i][1:]]) % 2 != P[i]:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

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

c = 0
for i in range(2**N):
    num = format(i, 'b')
    num = num.rjust(N, '0')
    for m_switch in range(M):
        box = 0
        for j in switch[m_switch]:
            box += int(num[j-1])
        if box%2 != P[m_switch]:
            break
        elif m_switch == M-1:
            c += 1
print(c)

Submission status: Accepted

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

switches = [[] for _ in range(m)]

for i in range(m):
    switches[i] = list(map(lambda x:int(x) - 1, input().split()))[1:]

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

cnt = 0

for condition in range(1 << n):
    light = True
    for i in range(m):
        oncnt = 0
        for switch in switches[i]:
            if (condition & (1 << switch)) != 0:
                oncnt += 1
        if oncnt % 2 != p[i]:
            light = False
    if light:
        cnt += 1

print(cnt)

Submission status: Accepted

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

k = []
s = []

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

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

ans = 0

for i in range(2 ** n):
    bin_i = bin(i)[2:].zfill(n)
    flag = True
    for j in range(m):
        cnt = 0
        for _k in range(k[j]):
            if bin_i[s[j][_k] - 1] == "1":
                cnt += 1
        if cnt % 2 != p[j]:
            flag = False
            break
    if flag:
        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):
  switch = []
  for j in range(N):
    switch.append((i >> j) & 1)
  lights = 0
  for u in range(M):
    connect = 0
    for v in range(KS[u][0]):
      if switch[KS[u][v+1]-1] == True:
        connect += 1
    if connect % 2 == P[u]:
      lights += 1
  if lights == M:
    ans += 1
  #print(switch, connect, lights)
    
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(1<<N):
    flag = True
    for j in range(M):
        k = KS[j][0]
        s = sorted(list(map(lambda x: x-1, KS[j][1:])))
        p = P[j]
        count = 0
        comb = 0
        for si in s:
            comb = comb | (1<<si)
        res = i & comb
        for l in range(N):
            if (res>>l)&1:
                count += 1
        if (count%2 == p):
            continue
        else:
            flag = False
    if (flag):
        ans += 1


print(ans)

Submission status: Accepted

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

for i in range(2 ** N):
	x = bin(i)[2:].rjust(N, "0")
	flag = True
	for j in range(M):
		tmp = 0
		for k in range(1, s[j][0] + 1):
			index = s[j][k]
			if x[index - 1] == "1":
				tmp += 1
		if tmp % 2 != p[j] % 2:
			flag = False
	if flag:
		ans += 1
print(ans)

Submission status: Accepted

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

ans = 0
for si in itertools.product([0, 1], repeat=n):
    ok = True
    for mi in range(m):
        s_on = 0
        for k in range(ks[mi][0]):
            s_on += si[ks[mi][1 + k] - 1]
        if s_on % 2 != p[mi]:
            ok = False
            break
    if ok:
        ans += 1

print(ans)

Submission status: Accepted

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


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

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

ans = 0
for i in range(2 ** N):
    tmp = []
    den_count = 0
    for j in reversed(range(N)):
        if (i & (1 << j)):
            #スイッチがonの場合
            tmp.append(1)
        else:
            #スイッチがoffの場合
            tmp.append(0)
    for k in range(len(den)):
        #つながっているスイッチの配列が降りてくる
        switch_count = 0
        for z in den[k]:
            if tmp[z-1] == 1:
                switch_count += 1
        if switch_count % 2 == p[k]:
            den_count += 1
        else:
            break
    if den_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):
    lia = list(map(int,input().split()))
    li.append(lia[1:])

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

switch = []

def onoff(count):
    global ans
    if count == n:
        for i in range(m):
            sum = 0
            for j in li[i]:
                sum += switch[j-1]
            if sum % 2 != lip[i]:
                break
            if i == m-1:
                ans += 1
    else:
        switch.append(0)
        onoff(count+1)
        switch.pop(-1)
        switch.append(1)
        onoff(count+1)
        switch.pop(-1)

onoff(0)

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
s_info = [[] for j in range(M)]
for i in range(M):
	l = list(map(int,input().split()))
	n_l = [x-1 for x in l]
	s_info[i] = n_l[1:]
cond = list(map(int,input().split()))


def dec2bin(n, d):
	ret = []
	for i in range(d):
		ret.append(n%2)
		n = n // 2
	return ret

ans = 0
for i in range(2**N):
	switch = dec2bin(i, N)
	flg = True
	for m in range(M):
		if sum([1 for n in range(N) if switch[n] == 1 and n in s_info[m]]) % 2 != cond[m]:
			flg = False

		
	if flg:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
def solve():
    n, m = map(int, input().split())
    M = [0] * m
    for i in range(m):
        _, *S = map(int, input().split())
        for s in S:
            M[i] |= (1 << (s - 1))
    P = list(map(int, input().split()))
    ans = 0
    for i in range(1 << n):
        for j in range(m):
            if bin(i & M[j])[2:].count('1') % 2 != P[j]:
                break
        else:
            ans += 1
    print(ans)
solve()

Submission status: Accepted

Solution code:
import itertools
n, m = map(int, input().split())
data = []
for i in range(m):
    tmp = list(map(int, input().split()))
    data.append([i, tmp[0], tmp[1:]])
ps = list(map(int, input().split()))
situ = list(itertools.product("01", repeat=n))
ans = 0
for one in situ:
    tmp1 = 0
    # 各ライトについて検査
    for light in data:
        tmp2 = 0
        # スイッチ入り確認
        for index in light[2]:
            if one[index - 1] == "1":
                tmp2 += 1
        if tmp2 % 2 == ps[light[0]]:
            tmp1 += 1
    if tmp1 == m:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
K = []
S = []
for i in range(M):
    k,*s = map(int, input().split())
    K.append(k)
    tmp = 0
    for j in s:
        tmp += 1<<(j-1)
    S.append(tmp)
P = list(map(int, input().split()))

result = 0
for i in range(1<<(N)):
    cnt = 0
    # print(i)
    for j in range(M):
        tmp = S[j] & i
        val = str(bin(tmp)).count('1')
        #print(bin(i), bin(tmp), val % 2)
        if val % 2 == P[j]:
            cnt += 1
    #print(cnt, 'cnt')
    if cnt == M:
        result += 1

print(result)
#print(K,S, P)
#print(1<<N)

Submission status: Accepted

Solution code:
def all_lightsup(A, switches, k, p):
    for i in range(M):
        light = 0
        elements = k[i]
        for j in range(elements):
            if A[switches[i][j]-1] == 1:
                light += 1
        if light % 2 != p[i]:
            return False
    return True

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

num_of_state = 2**N
for i in range(num_of_state):
    val = i
    temp = []
    for j in range(N):
        temp.append(val%2)
        val //= 2
    if all_lightsup(temp, switches, k, p):
        ans += 1
print(str(ans))

Submission status: Accepted

Solution code:
n,m=[int(x) for x in input().split()]
k,s=[],[]
for _ in [0]*m:
    val=[int(x) for x in input().split()]
    k.append(val[0])
    s.append(val[1:])
p=[int(x) for x in input().split()]
ans=0
for i in range(1<<n):
    for j in range(m):
        on_switch_num=0
        for l in range(n):
            if l+1 in s[j] and (i>>l & 1) == 1:
                on_switch_num+=1
        if on_switch_num%2==p[j]:
            continue
        else:
            break
    else:
        ans+=1
print(ans)

Submission status: Accepted

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

  K = [0] * M
  for i in range(M):
    s = [int(i) for i in input().split()]
    s.pop(0)
    v = 0
    for j in s: v += 2 ** (j - 1)
    K[i] = v

  P = [int(i) for i in input().split()]

  def check(v):
    for i in range(M):
      f = v & K[i]
      count = bin(f).count('1')
      if P[i] != (count % 2): return False
    return True

  ans = 0
  for i in range(2 ** N):
    if check(i): ans += 1

  return ans

print(solve())

Submission status: Accepted

Solution code:
from itertools import product
N, M = map(int, input().split())
K = []
S = []
for i in range(M):
    tmp1 = list(map(int, input().split()))
    K.append(tmp1[0])
    tmp2 = []
    for j in tmp1[1:]:
        tmp2.append(j-1)
    S.append(tmp2)

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

ans = 0
for v in product([0, 1], repeat=N):
    flag = False
    cnt_M = 0
    for j in range(M):
        cnt_light = 0
        for i in range(N):
            for k in range(K[j]):
                if v[i] == 1 and i == S[j][k]:
                    cnt_light += 1
        if cnt_light % 2 == P[j]:
            cnt_M += 1
        else:
            break
        if cnt_M == M:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
def IntToState(X, N):
    ret = []
    bina = bin(X)
    for i in range(2, len(bina)):
        ret.append(int(bina[i]))
    while len(ret) <= N:
        ret.insert(0,0)
    return ret

def solve():
    N, M = [int(_) for _ in raw_input().split()]
    SK = []
    for i in range(M):
        SKi = [int(_) for _ in raw_input().split()]
        SK.append(SKi)
    p = [int(_) for _ in raw_input().split()]
    ans = 0
    MAX_CASE = 1<<N
    for i in range (MAX_CASE):
        state = IntToState(i, N)
        satisfi = True
        for j in range(M):
            tmp_sum = 0
            for k in range(1, SK[j][0] + 1):
                tmp_sum += state[SK[j][k]]
            if tmp_sum % 2 != p[j]:
                satisfi = False
                break
        if satisfi:
            ans += 1
    print ans

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    n, m = get_li()
    K2S = defaultdict(set)
    S2K = defaultdict(set)
    for i in range(m):
        ks = get_li()
        S = ks[1:]
        for s in S:
            K2S[i+1].add(s)
            S2K[s].add(i+1)
    P = get_li()
    ans = 0
    for x in its.product([0, 1], repeat=n):
        valid = True
        for i in range(m):
            on = 0
            for j in K2S[i+1]:
                on += x[j-1]
            if on % 2 != P[i]:
                valid = False
                break
        if valid:
            ans += 1
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


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


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
list=input().split(" ")
n=int(list[0])
m=int(list[1])

denkyu=[]

for i in range(m):
    info=input().split(" ")
    for j in range(len(info)):
        info[j]=int(info[j])
    list=[]
    for i in range(n):
        list.append(0)
    
    #print(info)
    for j in range(len(info)-1):
        list[info[j+1]-1]=1
    denkyu.append(list)

#print(denkyu)

shogo=[]

for x in range(2**n):
    shinsu=[]
    for y in range(n):
        if x%2==1:
            shinsu.append(1)
            x=int((x-1)/2)
        else:
            shinsu.append(0)
            x=int((x)/2)
    shogo.append(shinsu)

#print(shogo)

plist=input().split(" ")
for j in range(len(plist)):
    plist[j]=int(plist[j])

#print(plist)

#print("")
kosu=0
for s in shogo:
    switch=1
    now=0
    complete=0
    while switch==1:
        match=0
        for i in range(n):
            if s[i]==denkyu[now][i] and s[i]==1:
                #print("X", s[i], denkyu[now][i], s, denkyu[now])
                match+=1
        if match%2==plist[now]:
            now+=1
        else:
            switch=0
        if now==(m):
            if switch==1:
                complete=1
                switch=0
                #print(s)
    if complete==1:
        kosu+=1
        #print("y", s)
print(kosu)

Submission status: Accepted

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

KS = []
for _ in range(M):
    ks = list(map(int, input().split()))
    KS.append(ks)
    
P = list(map(int, input().split()))
def checker(on_off):
    for i, ks, in enumerate(KS):
        sum_s = sum([ on_off[s-1] for s in  ks[1:]])
        if sum_s % 2 != P[i]:
            return 0
    return 1
        

def dfs(i, on_off):
    if i == 0:
        #print(on_off)
        return checker(on_off)
    
    a = dfs(i-1, on_off[:] + [0])
    b = dfs(i-1, on_off[:] + [1])
    return a + b
        
    
ans = dfs(K, [])
print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n, m = map(int, input().split())
ans = 0
S = [list(map(int, input().split())) for i in range(m)]
P = list(map(int, input().split()))
for combi in product([True, False], repeat=n):
    result = True
    for i in range(len(S)):
        p = sum([int(combi[s - 1]) for s in S[i][1:]])
        if p % 2 != P[i]:
            result = False
            break
    if result:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
lis = []
for i in range(m):
  l = list(map(int,input().split()))
  l.remove(l[0])
  lis.append(l)
ch = list(map(int,input().split()))
ans = 0
for i in range(2 ** n):
  key = 1
  s = str(format(i,"b").zfill(n))
  for j in range(m):
    num = 0
    for nu in lis[j]:
      if s[nu-1] == "1":
        num += 1
    if num % 2 != ch[j]:
      key = 0
  if key == 1:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools as it
import sys
sys.setrecursionlimit(10**9)
"""
N=int(input())
D=[]
for i in range(N):
  s,p=input().split()
  D.append((s, int(p), i+1))
D.sort(key=lambda d: (d[0], -d[1], d[2]))

for d in D:
  print(d[2])
"""
N,M=map(int, input().split())
K=[]
S=[]
for i in range(M):
  k,*si=map(int, input().split())
  K.append(k)
  S.append(list(sorted(si)))
P=list(map(int, input().split()))

L=it.product([0,1], repeat=N)
cnt=0
#print(S)
for l in L:
  ok=True
  for i,si in enumerate(S):
    pi=P[i]
    sumS=len(list(filter(lambda it: l[it-1]==1, si)))
    #print(l, sumS)
    if sumS%2 != pi: ok=False
  if ok: cnt += 1
print(cnt)