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

Solution (Python):

n, m = [ int(v) for v in input().split() ]
switch_list = []
for i in range(m):
	switch_list.append([ int(v)-1 for v in input().split() ][1:])
p_list = [ int(v) for v in input().split() ]


def switch_check(inlist):
	ans = 0
	p_list2 = [ [inlist[j] for j in switch_list[i] ].count("1")%2  for i in range(m) ]
	if  p_list2 == p_list:
		ans = 1
	return ans

sumans = 0

for i in range(2**n):
	s = (n-len(bin(i))+2)*"0" +bin(i)[2:]
	sumans  += switch_check(s)

print(sumans)

Solution (Python):
import numpy as np

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

ks = []
ss = []
for i in range(m):
    row = list(map(int, input().split()))
    k = row.pop(0)
    ss.append(row)


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

ks = np.array(ks, dtype=np.int64)
ps = np.array(ps, dtype=np.int64)

masks = []
for s in ss:
    mask = sum([2 ** (a - 1)for a in s])
    masks.append(mask)



def calc_switch_state(i, switch_state):
    num_on = 0
    mask = masks[i]
    switch_state = switch_state & mask
    while switch_state > 0:
        num_on += switch_state % 2
        switch_state //= 2

    return num_on % 2


def is_light_on(i, switch_state):
    return calc_switch_state(i, switch_state) == ps[i]


total = 0
for state in range(2**n):
    if all([is_light_on(i, state) for i in range(m)]):
        total += 1

print(total)

Solution (Python):
n, m = map(int, input().split())
k = [0] * m
s = [[] for _ in range(m)]
for i in range(m):
    l = list(map(int, input().split()))
    k[i] = l[0]
    s[i] = l[1:]
p = list(map(int, input().split()))

ans = 0
for i in range(1 << n):
    s_num = [0] * m
    for j in range(n):
        if i >> j & 1:
            for k in range(m):
                if j + 1 in s[k]:
                    s_num[k] += 1
    s_num = [x % 2 for x in s_num]
    if s_num == p:
        ans += 1
print(ans)

Solution (Python):
import itertools

import numpy as np

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

light = []

for i in range(m):
    light.append(list(map(int, input().split())))

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

result = 0
for i in itertools.product([0, 1], repeat=n):
    i = np.array(i)
    s = 0
    for l in light:
        sel = np.array(l[1:]) - 1
        chk = np.sum(i[sel])
        if chk % 2 != p_list[s]:
            break
        s += 1
    
    if s == m:
        result += 1
            

print(result)

Solution (Python):
import numpy as np

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

ks = []
switch_list = [[0 for j in range(10)] for i in range(M)]
for i in range(M):
    ks.append(list(map(int, input().split())))
    for j in range(ks[i][0]):
        switch_list[i][10-ks[i][j+1]] = 1
p = list(map(int, input().split()))

ans = 0
for i in range(2**N):
    flg = True
    binary = format(i, 'b').zfill(10)
    binary = list(map(int, binary))
    for j in range(M):
        on = np.logical_and(switch_list[j], binary)
        total_on = sum(on)
        if total_on%2 != p[j]:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Solution (Python):
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()))
count = 0
sw = [0] * N

def depth(index):
    global count
    for j in range(M):
        a = 0
        for k in range(ks[j][0]):
            if sw[ks[j][k + 1] - 1] == 1: a += 1
        if a % 2 == P[j]:
            if j + 1 == M: count += 1
        else: break

    for i in range(index, N):
        sw[i] = 1
        depth(i + 1)
        sw[i] = 0

depth(0)
print(count)

Solution (Python):
def makelist2(n, m):
    return [[0 for k in range(m)] for i in range(n)]

n, m = map(int, input().split())
switches = makelist2(n,m)
for i in range(m):
    tmp = list(map(int, input().split()))
    for j in range(len(tmp)-1):
        switches[tmp[j+1]-1][i] = 1

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

ans = 0
for i in range(pow(2,n)):
    frag = True
    target = "{:0>{}b}".format(i, n)
    for j in range(m):
        kosuu = 0
        for k in range(n):
            if(target[k]=="1"):
                if(switches[k][j]==1):
                    kosuu += 1
        if(kosuu%2 != p[j]):
            frag = False
    if(frag):
        ans += 1

print(ans)

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

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

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


cnt = 0
for L in range(pow(2, N)):

    for pi, s in zip(p, Ss):
        x = pi
        for si in s:
            x ^= ((L & (1 << (si - 1))) != 0) * 1
        if x != 0:
            break
    else:
        cnt += 1

print(cnt)

Solution (Python):
N,M = map(int,input().split())
Ss = []
for m in range(M):
    S = list(map(int,input().split()))
    Ss.append(S[1:])
ps = list(map(int,input().split()))
output= []
for i in range(1 << N):
    nums = []
    for j in range(N):
        if ((i >> j) & 1) == 1:
            nums.append(1)
        else:
            nums.append(0)
    output.append(nums)
ans = 0
for out in output:
    num = 0
    for (s,p) in zip(Ss,ps):
        count = 0
        for ss in s:
            if out[ss-1]==1:
                count+=1
        if count%2==p:
            num+=1
    if num==len(ps):
        ans+=1
print(ans)

Solution (Python):
from itertools import combinations

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

ANS = [i for i in range(2**N)]
for p, s in zip(P, S):
    for r in range(p ^ 1, len(s) + 1, 2):
        for selected in combinations(s, r):
            others = set(s) - set(selected)
            n = 0
            for i in selected:
                n += 2**(i - 1)
            m = 0
            for i in others:
                m += 2**(i - 1)
            ANS = [ans for ans in ANS if not (ans & n == n and ans & m == 0)]
print(len(ANS))

Solution (Python):
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x) - 1, input().split()))


def convert(nums):
    
    return sum([2**i for i in nums])


def is_on(ons, bulb, p):
    return bin(ons & bulb).count('1') % 2 == p

def is_all_on(ons, bulbs, ps):
    res = True
    for bulb, p in zip(bulbs, ps):
        
        res &= is_on(ons, bulb, p)
    return res


n, m = LI()
k, s = [], []
for _ in range(m):
    _input = LI_()
    s.append(convert(_input[1:]))
    

p = LI()

res = 0
for ons in range(2**n):
    res += is_all_on(ons, s, p)

print(res)

Solution (Python):
import itertools

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

k = [list(map(int,input().split())) for i in range(m)]

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

switch = [1,0]
comb = []

for x in itertools.product([1,0], repeat=n):
    comb.append(x)
    
c = 0

for i in range(len(comb)):
    light = 0
    
    for j in range(m):
        temp = 0
        for r in range(k[j][0]):
            if comb[i][k[j][r+1]-1] == 1:
                temp += 1
        
        if temp%2 == p[j]:
            light += 1
    
    if light == m:
        c += 1

print(c)

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

def base(X, a):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%a)+out
        X_dumy = int(X_dumy/a)
    return str(out).rjust(n,'0')
ans=0
for x in range(2**n):
    s=[0 for _ in range(m)]
    b=base(x,2)
    for i in range(m):
        for j in range(ks[i][0]):
            if b[ks[i][j+1]-1]=="0":
                if s[i]==0:
                    s[i]=1
                else:
                    s[i]=0
    if s==p:
        ans+=1

print(ans)

Solution (Python):
def hantei(n,m,s,k,p):
  b = 0
  for l in range(m):
    a = 0
    for x in range(k[l][0]):
      a += s[k[l][x+1]-1]
    if a%2 != p[l]:
      b = 1
  if b == 0:
    return True
  else:
    return False

n,m = map(int,input().split())
k = []
for _ in range(m):
  k.append(list(map(int,input().split())))
p = list(map(int,input().split()))
c = 0
for _ in range(2**n):
  s = [0] * n
  ll = len(bin(_))
  for i in range(ll):
    if i >= 2:
      s[n-ll+i] = int(bin(_)[i])
  if hantei(n,m,s,k,p):
    c += 1
print(c)

Solution (Python):
import numpy as np
N, M = map(int, input().split())
taiou = np.zeros((N,M))
for i in range(M):
    val =  input().split()
    for j in range(int(val[0])):
        v = int(val[j+1])
        taiou[v-1][i] = 1
p = np.array([int(v) for v in input().split()])
cnt = 0
for val in range(2**N):
    v = taiou*np.array([[int(i)] for i in bin(val)[2:].zfill(N)])
    if np.sum(np.sum(v,axis=0)%2==p)==M:
        cnt+=1
    
print(cnt)

Solution (Python):
n,m = map(int, input().split())
import numpy as np
KS = [np.array(list(map(int, input().split()))) for _ in range(m)]
P = list(map(int, input().split()))

import itertools
cond = np.array([np.array(i) for i in itertools.product([0,1],repeat=n)])

light = 0
for ks,p in zip(KS,P):
  cond = [i for i in cond if sum(i[ks[1:]-1])%2 == p]
  
print(len(cond))

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

isAffectedSwitch=[[False for _ in range(n)] for _ in range(m)]
for i in range(m):
    for j in range(1,s[i][0]+1):
        isAffectedSwitch[i][s[i][j]-1]=True

onoff=[[(i%(2**(n-j)))>>(n-j-1) for j in range(n)]for i in range(2**n)]

ans=0
for i in range(2**n):
    cnt=[0 for _ in range(m)]
    for j in range(n):
        for k in range(m):
            if onoff[i][j]==1:
                if isAffectedSwitch[k][j]==True:
                    cnt[k]+=1
    isOK=True
    for k in range(m):
        if cnt[k]%2!=p[k]:
            isOK=False
    if isOK:
        ans+=1
print(ans)

Solution (Python):
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint

import bisect
import copy
import fractions
import math
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
def unite(x, y):
    
    x = root(x)
    y = root(y)
    if x == y:
        return
    
    node[x] = y
def same(x,y): return bool(root(x) == root(y))
def root(x):
    if node[x] == x:  
        return x
    else:
        node[x] = root(node[x])  
        return node[x]
def dfs(v):
    
    visited[v] = True
    for v2 in range(n):
        if graph[v][v2] == False:  
            continue
        if visited[v2] == True:  
            continue
        dfs(v2)


n, m = MI()
a = [LI() for _ in range(m)]
p = LI()
index = 0
cnt = 0
for i in range(2 ** n):
    
    tento = [0] * n
    for j in range(n):
        if ((i >> j) & 1):
            tento[n-1-j] = 1
    index = 0
    for k in a:
        tmp = 0
        for i, num in enumerate(k[1:]):
            if tento[num-1] == 1:
                tmp += 1
        
        if tmp % 2 == p[index]:
            index += 1
            if index == m:
                cnt += 1
        else:
            break
print(cnt)

Solution (Python):
import numpy as np
N,M = list(map(int, input().split()))
dat=[]
for i in range(M):
  dat.append(list(map(int, input().split())))
p = list(map(int, input().split()))

A=np.zeros((M,N))
for i in range(M):
  for j in range(len(dat[i])-1):
    A[i,dat[i][j+1]-1]=1

res=0

v = np.zeros((N,1))
for i in range(2**N):
  for j in range(N):
    v[j,0] = int(i / (2**j)) % 2
  w=(np.dot(A,v) % 2)

  flg=True
  for j in range(len(p)):
    if p[j] != int(w[j]):flg=False
  if flg:
    res=res+1
print(res)

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

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


count = 0
for i in range(2**n):
  b = format(i, '0%db' % n)
  
  judge = True
  for j in range(m):
    if not judge:
      break
    t = 0
    for k in range(1, 1+ks[j][0]):
      idx = ks[j][k] - 1
      if b[idx] == '1':
        t += 1
    if t % 2 != p[j]:
      judge = False
  if judge:
    count += 1
print(count)

Solution (Python):

def main():
    N, M = map(int, input().split())
    K = []
    S = []
    for i in range(M):
        temp = list(map(int, input().split()))
        ki = int(temp[0])
        K.append(ki)
        si = list(temp[1:])
        S.append(si)

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

    ans = 0
    temp = [0] * N
    ans += method(temp, N, M, K, S, P, 0)
    print(ans)


def method(l, N, M, K, S, P, roop):
    ans = 0
    if roop < N:
        l[roop] = 0
        ans += method(l, N, M, K, S, P, roop+1)
        l[roop] = 1
        ans += method(l, N, M, K, S, P, roop+1)

    elif roop == N:
        flag = True
        
        for i in range(M):
            s = 0
            for j in range(K[i]):
                if l[S[i][j]-1] > 0:
                    s += 1
            if s % 2 != P[i]:
                
                flag = False
        if flag == True:
            ans += 1
        return ans
    else:
        
        return -99
    return ans


if __name__ == "__main__":
    main()

Solution (Python):

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
n,m=IL()
S=[]
for i in range(m):
    t=IL()
    S.append(t[1:])
P=IL()
ans=0
for i in range(pow(2,n)):
    ok=True
    sl=bin(i)[2:].zfill(n)
    for i in range(m):
        w=0
        for idx in S[i]:
            if sl[idx-1]=="1":
                w+=1
        if w%2!=P[i]:
            ok=False
    if ok:
        ans+=1
print(ans)

Solution (Python):
def honyaku(i,N):
    ans = []
    tmp = i
    for i in range(1,N+1):
        ans.append(tmp%2)
        tmp = tmp//2
    return ans
def check(s_list,d_list,p):
    tmp = 0
    for i in range(1,len(d_list)):
        if s_list[d_list[i]-1] == 1:
            tmp += 1
    if tmp%2 == p:
        return True
    else:
        return False

[N,M] = list(map(int,input().split()))
s = []
for i in range(M):
    s_tmp = list(map(int,input().split()))
    s.append(s_tmp)
p = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    s_list = honyaku(i,N)
    ans_tmp = 0
    for j in range(M):
        if check(s_list,s[j],p[j]) == True:
            ans_tmp += 1
    if ans_tmp == M:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
tmp = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
L = []
ans = 0
for i in tmp:
    c = 0
    for j in range(1, i[0] + 1):
        c += 2 ** (i[j] - 1)
    L.append(c)

for i in range(2 ** N):
    for j in range(M):
        if not p[j] == bin(L[j] & i).count("1") % 2:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
n,m=map(int,input().split())
ans=0
k=[]
def func(n,s,i):
    global ans
    if n==0:
        c=0
        for j in range(m):
            cnt=0
            for a in range(1,len(k[j])):
                if s[k[j][a]-1]==1:
                    cnt+=1
            if cnt%2==p[j]:
                c+=1
        if c==m:
            ans=ans+1
    else:
        for j in range(2):
            if j==0:
                s[i-1]=0
                func(n-1,s,i+1)
            else:
                s[i-1]=1
                func(n-1,s,i+1)

for i in range(m):
    K=list(map(int,input().split()))
    k.append(K)
p=list(map(int,input().split()))
func(n,[0]*n,0)
print(ans)

Solution (Python):
N, M = list(map(int, input().split()))
s = []

for i in range(M):
    s.append(list(map(int, input().split())))

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

ans = 0
for i in range(2 ** N):
    f = 0
    for j in range(M):
        cc = 0
        for k in range(1, len(s[j])):
            if (i >> (s[j][k] - 1)) % 2 == 1:
                cc += 1
        if cc % 2 != p[j]:
            f = 1
            break
    if f == 0:
        ans += 1

print(ans)

Solution (Python):
N,M = map(int, input().rstrip().split())
k_s = [list(map(int, input().rstrip().split())) for _ in range(M)]
for i in range(M):
    k_s[i].pop(0)
P = list(map(int, input().split()))

count = 0
counter = 0
limit = 2**N
for i in range(2):
    for j in range(2):
        for k in range(2):
            for l in range(2):
                for m in range(2):
                    for n in range(2):
                        for o in range(2):
                            for p in range(2):
                                for q in range(2):
                                    for r in range(2):
                                        counter += 1
                                        stats = [r,q,p,o,n,m,l,k,j,i]
                                        flg = True
                                        index = 0
                                        for s in k_s:
                                            sums = 0
                                            for t in s:
                                                sums += stats[t-1]
                                            rem = sums % 2
                                            if rem != P[index]:
                                                flg = False
                                                break
                                            index += 1
                                        if flg:
                                            count += 1
                                        if limit == counter:
                                            print(count)

Solution (Python):
I=lambda:map(int,input().split())
N,M=I()
sw=[]
for _ in [0]*M:
    _,*s=I()
    sw+=[s]
*p,=I()
r=0
for i in range(2**N):
    k=str(bin(i))[2:].rjust(N,"0")
    f=True
    for j in range(M):
        t=0
        for s in sw[j]:
            if k[s-1]=="1":t+=1
        if t%2!=p[j]:f=False;break
    if f:r+=1
print(r)

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

n = 0
for i in range(2**N):
    nums = [True if n&j != 0 else False for j in [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x100, 0x200]]
    n += 1

    for idx, s_ in enumerate(s):
        x = 0
        for _ in s_[1:]:
            x += nums[_-1]
        if x % 2 != p[idx]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
import copy

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

k_lis = []

for m in range(M):
  sw =  [int(_) - 1 for _ in input().split()][1:]

  k_lis.append(sw)

p_lis = [int(_) for _ in input().split()]

on_off = [[0], [1]]
tmp = []

for j in range(N-1):
  for t in on_off:
    tmp.append(t + [0])
    tmp.append(t + [1])
  on_off = tmp
  tmp = []

solved = 0
  
for t in on_off:
  flag = True
  for m in range(M):
    total = 0
    for k in k_lis[m]:
      total += t[k]
    if not total % 2 == p_lis[m]:
      flag = False
      break
  if flag:
    solved += 1
      
print(solved)

Solution (Python):


import sys
input = sys.stdin.readline



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

S = [[int(x) for i, x in enumerate(input().split()) if i != 0] for _ in range(M)]
P = [int(x) for x in input().split()]

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

        for j, s in enumerate(S):
                tmp = 0

                for ss in s:
                        if (i >> (ss - 1)) & 1:
                                tmp += 1
                                tmp %= 2
                
                if tmp != P[j]:
                        flag = False

        if flag:
                ans += 1

print(ans)

Solution (Python):
import itertools
N,M=map(int,input().split())
ks=list(list(map(int,input().split())) for _ in range(M))
P=list(map(int,input().split()))
L=[0,1]
LL=list(itertools.product(L,repeat=N))
ans=0
sum=[]
msum=0
for I in LL:
    sum=[]
    for J in ks:
        msum=0
        for k in range(1,J[0]+1):
            msum+=I[J[k]-1]
        sum.append(msum)
    if all(sum[i]%2==P[i] for i in range(M)):
        ans+=1
print(ans)

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


k = []
s = []


for i in range(M):
    I = input().split()

    k.append(I.pop(0))
    s.append(list(map(int,I)))


P = list(map(int , input().split()))
status = [0]*N

count = 0

for i in range(2**N):
    flag = True

    binary = i
    for j in range(N):
        status[j] = 1 if (binary % 2 == 1) else 0
        binary = int(binary / 2)

    for j in range(M):
        sum = 0
        for index in s[j]:
            sum = sum + status[index-1]

        if sum % 2 != P[j]:
            flag = False
            break

    if flag:
        count = count + 1


print(count)

Solution (Python):




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

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

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

ans = 0
for i in range(2**n):
    binstr = format(i, "010b")
    binlist = list()
    for j in range(10):
        binlist.append(int(binstr[j]))
    
    
    is_on = True
    for x in range(m):
        subt = 0
        for y in range(1, ks[x][0] + 1):
            subt += binlist[10 - ks[x][y]] * 1
        
        if subt % 2 != p[x]:
            is_on = False
            break

    if is_on == True:
        ans += 1


print(ans)

Solution (Python):
import itertools

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

connection = []

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

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

A = [0,1]
all_pt = list(itertools.product(A,repeat=N))

all_cnt = 0


for pt in all_pt:
    for con, on_pt in zip(connection, light_on):
         
        OK = False
        ON = 0
        for t in con:
            if pt[t-1] == 1:
                ON = ON + 1
        if ON % 2 != on_pt:
            break
        OK = True
    if OK:
        all_cnt += 1

print(all_cnt)

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

ans =0
for i in range(2**N):
    s_state=[]
    for j in range(N):
        s_state.append(i//(2**j)%2)
    all_green=1
    for j in range(M):
        num_on = 0
        for k in s[j]:
            num_on = num_on+s_state[k-1]
        if num_on%2 == p[j]:
            pass
        else:
            all_green=0
            break
    ans = ans + all_green
print(ans)

Solution (Python):
N,M = map(int, input().split())
li = [list(map(int, input().split())) for i in range(M)]
p = list(map(int, input().split()))

ptn = []
for i in range(2 ** N):
    ptn.append(list(str(bin(i))[2:].zfill(N)))

ans = 0
for x in ptn:
    sucflg = True
    for oidx,outval in enumerate(li):
        cnt = 0
        for idx,inval in enumerate(outval):
            if idx == 0:
                continue
            if x[inval - 1] == '1':
                cnt += 1
        else:
            if cnt % 2 != p[oidx]:
                sucflg = False
                break
    else:
        if sucflg:
            ans += 1

print(ans)

Solution (Python):
import numpy as np
N, M = map(int, input().split())
K = [list(map(int, input().split()))[1:] for _ in range(M)]
P = list(map(int, input().split()))
C = 0
for x in range(2**N):
    X = [x// (2**n) % 2 for n in range(N)]
    X = np.array(X)
    c = 0
    for m in range(M):
        l = np.array(K[m])-1
        if sum(X[l]) % 2 == P[m]:
            c += 1
    if c == M:
        C += 1
print(C)

Solution (Python):

import numpy as np
from functools import lru_cache
import time

def main(): 
    if True:
        N,M = list(map(int, input().split()))
        KS = np.zeros((M,N+1),dtype=int)
        for i in range(M):
            tmp = list(map(int, input().split()))
            tmp = tmp + [0]*(N-tmp[0])
            KS[i] = tmp
        P = list(map(int, input().split()))
    else:
        pass
    count = 0
    for i in range(2**N):
        b = "0"*N + bin(i)[2:] 
        tcount = 0
        for j in range(M):
            p = P[j]
            ks = KS[j][1:]
            n = 0
            for tks in ks:
                n += int(b[-tks])
            if n % 2 == p:
                tcount += 1
            else:
                break
        else:
            count += 1
            

    print(count)
if __name__ =='__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
lights = [list(map(int, input().split())) for _ in range(M)]
p_values = list(map(int, input().split()))

switch_conbs = []
for i in range(2 ** N):
    conb = bin(i)[2:].zfill(N)
    switch_conbs.append(list(map(int, list(conb))))

for i, light in enumerate(lights):
    temp = []
    for switch_conb in switch_conbs:
        s = 0
        for v in light[1:]:
            s += switch_conb[v - 1]
        if s % 2 != p_values[i]:
            temp.append(switch_conb)
    
    for l in temp:
        switch_conbs.pop(switch_conbs.index(l))

print(len(switch_conbs))

Solution (Python):
import numpy as np
k = []
s = []
N, M = map(int, input().split())
for i in range(M):
    ki, *si = map(int, input().split())
    k.append(ki)
    s.append(si)
p = list(map(int, input().split()))

switch = []
for i in range(2**N):
    switch.append([0] + list(map(int, format(i, 'b').zfill(N)))[::-1])
switch = np.array(switch)

index = set()
for i, (ki, si) in enumerate(zip(k, s)):
    on = []
    for ind, state in enumerate(switch):
        if sum(state[si]) % 2 == p[i]:
            on.append(ind)
    if i == 0:
        index = set(on)
    else:
        index = index & set(on)
print(len(index))

Solution (Python):
def check(setting, switch, offset):
    output = setting & switch
    count = 0
    while output > 0:
        count += output & 1
        output >>= 1
    return count % 2 == offset


N, M = map(int, input().split())
switch_state_num = 1 << N

lamp_setting = []
lamp_default = []


for _ in range(M):
    lamp_setting_input = (list(map(int, input().split())))[1:]
    lamp_setting_single = 0
    for i in range(N):
        lamp_setting_single |= (1 if (i + 1) in lamp_setting_input else 0) << i
    lamp_setting.append(lamp_setting_single)

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

ans = 0


for switch_state in range(switch_state_num):
    suc = True
    for lamp_index in range(M):
        if not check(lamp_setting[lamp_index], switch_state, lamp_default[lamp_index]):
            suc = False
            break
    if suc:
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
kss = []
for i in range(1, M+1):
    ks = list(map(int, input().split()))
    kss.append(ks)
biases = list(map(int, input().split()))

active_switches = set()
for i in range(0, M):
    
    for j in range(1, kss[i][0] + 1):
        active_switches.add(kss[i][j])

import itertools

def is_lit(m, s, sw, b):
    total = b
    for val in s:
        if val in sw:
            total += 1
    return total%2 == 0


def is_all_lit(sw):
    return all([is_lit(ks[0], ks[1:], sw, biases[idx]) for idx, ks in enumerate(kss)])

answer = 0
for i in range(0, len(active_switches)+1):
    c = itertools.combinations(active_switches, i)
    result = map(is_all_lit, c)
    answer += sum(result)

import math
answer *= int(math.floor(math.pow(2, N - len(active_switches))))

print(answer)

Solution (Python):


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

switch = [[0] * N for _ in range(2 ** N)]
for i in range(2 ** N):
    for j in range(N):
        switch[i][j] = (i & (1 << j)) >> j
counter = 0
for sw in switch:
    ons = 0
    for i in range(M):
        temp = []
        for si in s[i]:
            temp.append(sw[si - 1])
        if sum(temp) % 2 == p[i]:
            ons += 1
    if ons == M:
        counter += 1

print(counter)

Solution (Python):
n, m = map(int, input().split())
l = []
for i in range(m):
    _, *s = [int(x)-1 for x in input().split()]
    l.append(s)
p = [int(x) for x in input().split()]

ans = 0
for i in range(2**n):
    d = 0
    q = i
    r = [0] * m
    while q > 0:
        s = q & 1
        if s == 1:
            for j in range(m):
                if d in l[j]:
                    r[j] += 1
        d += 1
        q >>= 1
    c = 0
    for j in range(m):
        if p[j] == (r[j] % 2):
            c += 1
    if c == m:
        ans += 1
print(ans)

Solution (Python):
N,M=(int(i) for i in input().split())
denkyu=[]
for i in range(M):
    denkyu.append([int(i) for i in input().split()])
p=[int(i) for i in input().split()]
import copy
swi=[[0],[1]]
for _ in range(N-1):
    swi1=copy.deepcopy(swi)
    swi2=copy.deepcopy(swi)
    for i in range(len(swi)):
        swi1[i].append(0)
        swi2[i].append(1)
    swi=swi1
    swi.extend(swi2)


answer=0
for s in swi:
    allon=1
    for i in range(M):
        on=0
        for j in range(1,denkyu[i][0]+1):
            if s[denkyu[i][j]-1]==1:
                on+=1
        if on%2!=p[i]:
            allon=0
            break
    if allon==1:
        answer+=1      
print(answer)