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:
def main():
    n, m = map(int,input().split())
    s = []
    k = []
    for i in range(m):
        tmp = list(map(int,input().split()))
        k.append(tmp.pop(0))
        s.append(tmp)
    p = list(map(int,input().split()))
    ans = 0

    f = True
    for i in range(2**n):
        tmp = [0] * n
        b = i
        keta = 0
        while b > 0:
            # print(b,bin(b))
            # print(bin(1&b))
            if bin(b & 1)==bin(1):
                tmp[keta] = 1
            b >>= 1
            keta += 1
        # print(tmp)
        for j, ss in enumerate(s):
            tmp_sum=0
            for l, sss in enumerate(ss):
                 if tmp[sss-1] == 1:
                    tmp_sum += 1
            if tmp_sum % 2 == p[j]:
                continue
            else:
                f = False
                break
        if f == True:
            ans += 1
        f = True
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

K_ary = []
for _ in range(M):
  k = list(map(int, input().split()))
  K_ary.append(k)
P = list(map(int, input().split()))

count_n = 0
for n in range(2 ** N):
  count_k = 0
  for i, k in enumerate(K_ary):
    s_k = k[1:]
    count_s = 0
    for s in s_k:
      shift_num = s - 1
      if ((n >> shift_num) & 1):
        count_s += 1
    
    if (count_s % 2 == P[i]):
      count_k += 1

  if (count_k == M):
    count_n += 1

print(count_n)

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
lamp=[]
for i in range(m):
  tmp=list(map(int,input().split()))
  lamp.append(tmp[1:])
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
  d={}
  for x in range(m):
    d[x]=0
  for j in range(n):
    if (i>>j)&1:
      I=0
      while I<m:
        if j+1 in lamp[I]:
          d[I]+=1
        I+=1
  judge=0
  for INDEX in range(m):
    if d[INDEX]%2==p[INDEX]:
      pass
    else:
      judge+=1
  if judge==0:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
# スイッチのon/offの状態による全探索を実行する。
n, m = map(int, input().split(" "))
relation = []
for _ in range(m):
    relation.append(list(map(int, input().split(" "))))
P = list(map(int, input().split(" ")))

count = 0
for i in range(2**n):
    flag = True
    for j in range(m):
        switch_set = relation[j]
        on_count = 0
        for k in range(1, len(switch_set)):
            tmp = i
            shifted = tmp >> (switch_set[k]-1)
            if shifted & 1:
                on_count += 1
        if on_count % 2 != P[j]:
            # このパターンにおいてこの電球がついていない場合
            flag = False
            break
    if flag:
        count += 1

print(count)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
k = []
s = []
for _ in range(m):
    tmp = list(map(int,input().split()))
    k.append(tmp[0])
    s.append(tmp[1:])
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    b = format(i, '0'+str(n)+'b')
    for j in range(m):
        cnt = 0
        for l in range(k[j]):
            cnt += int(b[s[j][l]-1])
        if cnt%2 != p[j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, m = map(int, input().strip().split())
  ss = []
  for im in range(m):
    x = 0
    for s in map(int, input().strip().split()[1:]):
      x += 2**(s-1)
    ss.append(x)
  ps = list(map(int, input().strip().split()))
      
  count = 0
  for i in range(2**n):
    flag = True
    for j in range(m):
      if bin(i & ss[j]).count('1')%2 != ps[j]:
        flag = False
        break
      
    if flag:
      count += 1
  print(count)

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
d=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
kk=[]
hantei=0
ans=0
ans2=0
for i in range(2**n):
  z=[]
  ans=0
  for j in range(n):
    if (i>>j&1):
      z.append(1)
    else:
      z.append(0)
  for k in range(len(d)):
    hantei=0
    for l in range(len(d[k])-1):
      hantei+=z[d[k][l+1]-1]
    if hantei%2==p[k]:
      ans+=1
  if ans==m:
    ans2+=1
print(ans2)

Submission status: Accepted

Solution code:
def inp():
    return input()
def iinp():
    return int(input())
def inps():
    return input().split()
def miinps():
    return map(int,input().split())
def linps():
    return list(input().split())
def lmiinps():
    return list(map(int,input().split()))
def lmiinpsf(n):
    return [list(map(int,input().split()))for _ in range(n)]


n,m = miinps()
k = lmiinpsf(m)
a = lmiinps()

ans = 0

for i in range(2**n):
  d = []
  p = len(bin(i))
  q = bin(i)
  for j in range(p-2):
    q = bin(i>>j)
    if int(q[len(q)-1]) == 1:
      d.append(j)
    
  count2 = 0 #点灯している電球の数
  
  for j in range(m):
    count1 = 0 #電球に接続されているスイッチの内onになっている数
    for l in range(len(k[j])-1):
      if (k[j][l+1]-1) in d:
        count1 += 1
    count1 %= 2
    if count1 == a[j]:
      count2 += 1
    else:
      break;
  if count2 == m:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


def solve(n, m, sx, p):
    ans = 0
    temp_c_list = []
    for i in range(1 << (n)):
        for si in sx:
            sum_si = sum(si)
            c = Counter(bin(i & sum_si)[2:])['1']
            temp_c_list.append(c % 2)
        if px == temp_c_list:
            ans += 1
        temp_c_list = []

    return ans


if __name__ == '__main__':
    n, m = map(int, input().split())
    sx = [[0]*n for _ in range(m)]

    for i in range(m):
        tx = list(map(int, input().split()))[1:]
        for ti in tx:
            sx[i][n-ti] = 1 << ti-1

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

    print(solve(n, m, sx, px))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
routing = [set([int(x) for x in input().split()][1:]) for _ in range(m)]
p = [int(x) for x in input().split()]
fail=0
for i in range(2**n):
    for k,x in enumerate(routing):
        num=0
        for j in range(n):
            if (i>>j)&1:
                if (j+1) in x:
                    num+=1
        if p[k]!=num%2:
            fail+=1
            break
print(2**n - fail)

Submission status: Accepted

Solution code:

def main():

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

    lights = []
    for _ in range(M):
        ary = [int(v) - 1 for v in input().split()]
        lights.append(ary[1:])

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

    def is_on(state):
        for i, sw in enumerate(lights):
            on = 0
            for j in sw:
                if state & (1 << j) != 0:
                    on += 1
            if (on % 2) != P[i]:
                return False
        return True

    def search(i, state):
        if i == N:
            ok = 1 if is_on(state) else 0
            return ok

        c = 0
        c += search(i+1, state)
        c += search(i+1, state | (1 << i))
        return c

    print(search(0, 0))


main()

Submission status: Accepted

Solution code:
import itertools

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

sw = [[] for _ in range(m)]
for i in range(m):
    sw[i] = list(map(int,input().split()[1:])) #k不要
     
p = list(map(int,input().split()))

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

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):
    switch=[False]*N

    for j in range(N):
        if ((i>>j) & 1):
            switch[N-j-1]=True

    light=True
    for m in range(M):
        cnt=0
        for o in range(k[m][0]):
            if switch[k[m][o+1]-1]==True:
                cnt+=1

        if not (cnt%2==p[m]):
            light=False

    if light==True:
        ans+=1
      
            
print(ans)

#パクリ元　https://www.planeta.tokyo/entry/3963/

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):
    switch=[False]*N

    for j in range(N):
        if ((i>>j) & 1):
            switch[N-j-1]=True

    light=True
    for m in range(M):
        cnt=0
        for o in range(k[m][0]):
            if switch[k[m][o+1]-1]==True:
                cnt+=1

        if not (cnt%2==p[m]):
            light=False

    if light==True:
        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)]  #sの各要素のはじめはk
p = list(map(int, input().split()))
ans = 0

# 0をoffとして2進数でパターンを表現

for i in range(2 ** N):
	ptn = bin(i)[2:].rjust(N, "0")  # N桁の2進表現にする
	light = True  # 着目している電球が点灯していないときはこれがFalseになる
	for j in range(M):
		tmp = 0  # 着目している電球について、スイッチのonの個数をカウントする
		for n in range(1, s[j][0] + 1):
			if ptn[s[j][n] - 1] == "1":
				tmp += 1
		if tmp % 2 != p[j] % 2:
			light = False
	if light:
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

######
# URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_A&lang=ja
######

def main():
    N, M = l_inpl()

    d = {}
    for i in range(M):
        k = [int(j)-1 for j in input().split(" ")]
        d[i] = k[1:]

    p = [int(i) for i in input().split(" ")]
    ans = 0

    for i in range(2 ** N):
        tmp = []
        for j in range(N):
            if ((i >> j) & 1):
                tmp.append(j)
        flag = True
        for idx, k in d.items():
            cnt = 0
            for ki in k:
                if ki in tmp:
                    cnt += 1
            
            if cnt % 2 != p[idx]:
                flag = False
                break
        
        if flag:
            ans += 1
    
    print(ans)

if __name__ == "__main__":
    main()

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()))
total = 0
flag = 1
for i in range(2 ** N):
  now = format(i, "0{}b".format(N))
  for k in range(M):
    tmp = 0
    for l in range(s[k][0]):
      if now[s[k][l+1]-1] == '1':
        tmp += 1
    if tmp % 2 == p[k]:
      continue
    else:
      flag = 0
      break
  if flag == 1:
    total += 1
  flag = 1
print(total)

Submission status: Accepted

Solution code:
def f(i):
    global ans
    if i == n:
        c = [0] * m
        for i in range(n):
            if t[i] == 1:
                for j in range(m):
                    if i + 1 in S[j]:
                        if c[j] == 0:
                            c[j] = 1
                        else:
                            c[j] = 0
        if c == p:
            ans += 1
        return
    f(i + 1)
    t[i] = 1
    f(i + 1)
    t[i] = 0

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

f(0)
print(ans)

Submission status: Accepted

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

ans = 0;
for i in range(2**n):
  flag = True
  for j in range(m):
    c = 0
    for k in km[j][1:]:
      if i & 2**(k-1):
        c += 1
    if (c%2 != p[j]):
      flag = False
  if flag:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
import queue
import copy


#X = str(input()).split()
#a = [int(x) for x in input().split()]


NM = str(input()).split()
N = int(NM[0])
M = int(NM[1])
KS = []
ans = 0
count = [0]*M
count2 = 0


for i in range(M):
  KS.append([int(x) for x in input().split()])

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

for i in range(2**N):
  for j in range(M):
    for k in range(KS[j][0]):
      if((i >> KS[j][k+1]-1) & 1):
        #print(i)
        #print(j)
        count[j]+=1
    if(count[j]%2==P[j]):
      count2+=1
    count[j]= 0
  if(count2==M):
    ans+=1
  count2=0









print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    switch_list = [list(map(int, input().split())) for _ in range(m)]
    p = list(map(int, input().split()))
    ret = 0
    for j in range(2**n):
        for i in range(m):
            total = 0
            flag = 1
            for k in switch_list[i][1:]:
                if j & 2**(k-1):
                    total += 1
            if not total%2 == p[i]:
                flag = 0
                break
        if flag:
            ret += 1
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
https://atcoder.jp/contests/abc128/tasks/abc128_c
'''
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque

    #mod = 1000000007

    n, m = map(int, input().split())
    switch_list = [list(map(int, input().split())) for _ in range(m)]
    p = list(map(int, input().split()))
    ret = 0
    for j in range(2**n):
        cnt = 0
        for i in range(m):
            total = 0
            for k in switch_list[i][1:]:
                if j & 2**(k-1):
                    total += 1
            if total%2 == p[i]:
                cnt += 1
            else:
                break
        if cnt == m:
            ret += 1
    print(ret)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()
s=[]
k=[]
for i in range(m):
    temp=limii()
    k0=temp[0]
    s0=temp[1:]
    s.append(s0)
    k.append(k0)

p=limii()
ans=0
#bit全探索
#print(p)
for i in product([0,1], repeat=n):
    #点灯している電球の数
    temp=0

    #全ての電球で探索
    for j in range(m):
        #対象の電球のonになっている個数
        cnt=0
        for x in s[j]:
            
            if i[x-1]==1:
                cnt+=1
            
        if cnt%2==p[j]:
            temp+=1
        #print(i,j,cnt)
    if temp==m:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
#ABC 128 C Switches
import numpy as np 
N,M = map(int,input().split())
# switch_matrix = np.ones((M,N))
switch_list = []
for m in range(M):
    inputs = list(map(int,input().split()))
    k = inputs[0]
    s_list = inputs[1:]
    p = 0
    for s in s_list:
        p= p | pow(2,s-1)

    switch_list.append(p)
p_list = list(map(int,input().split()))

ans=0
for i in range(pow(2,N)):
    num = 0
    for m in range(M):
        a = bin(i & switch_list[m]).count("1")
        if a%2 == p_list[m]:
            num+=1
    if num==M:
        ans+=1
print(ans)

Submission status: Accepted

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

# 調整
for L in s:
    for i in range(len(L)):
        L[i] -= 1

res = 0
for bit in range(1<<N):
    ok = True
    for i in range(M):
        con = 0
        for v in s[i]:
            if bit & (1<<v):
                con += 1
        if con % 2 != p[i]:
            ok = False
    if ok:
        res += 1
print(res)

Submission status: Accepted

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

ans = 0
for i in range(2**n):
    i = format(i, "0{}b".format(n))
    flag = 1
    for j in range(m):
        count = 0
        for k in range(switch[j][0]):
            if i[switch[j][k+1]-1] == "1":
                count += 1
        if count % 2 == p[j]:
            continue
        else:
            flag = 0
            break
    if flag == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

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

P = list(map(int, input().split(" ")))
F = "{:0" + str(N) + "b}"
ans = 0

for i in range(2**N):
    switch = F.format(i)
    if all(sum([int(switch[b-1]) for b in bulb]) % 2 == P[m]
           for m, bulb in enumerate(bulbs)):
        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):
    flag = 1
    s_lst = []
    for j in range(n):
        if i >> j & 1:
            s_lst.append(1)
        else:
            s_lst.append(0)
    for j, k in zip(ks, p):
        if k == 1:
            tmp = 0
            for l in j[1:]:
                tmp += s_lst[l-1]
            if tmp % 2 != 1:
                flag = 0
        if k == 0:
            tmp = 0
            for l in j[1:]:
                tmp += s_lst[l-1]
            if tmp % 2 != 0:
                flag = 0
        #print(j, k)
    if flag == 1:
        ans += 1
    #print(bin(i), s_lst, flag)
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)
    S.append(s)
p = list(map(int, input().split()))

ans = 0
for i in range(1<<n):
    onoff = [None] * m
    for j in range(m):
        cnt = 0
        for s in S[j]:
            if (i >> (s-1)) & 1:
                cnt += 1
        if cnt % 2 == p[j]:
            onoff[j] = True
    if all(onoff):
        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)]
ps=list(map(int,input().split()))
ans=0
for i in range(2**n):
  cnt=0
  os=[0]*n
  pos=0
  while i!=0:
    if i%2==1:
      os[pos]=1
      i-=1
    i=i//2
    pos+=1
  for j in range(m):
    tmp=0
    for k in range(ks[j][0]):
      if os[ks[j][1+k]-1]==1:
        tmp+=1
    if tmp%2==ps[j]:
      cnt+=1
  if cnt==m:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split(' '))
s = [list(map(int,input().split(' ')))[1:] for i in range(M)]
p = list(map(int,input().split(' ')))
s_bit = []
ans = 0
for i in s:
    tmp = 0
    for j in i:
        tmp += 2**(j-1)
    s_bit.append(bin(tmp))
for i in range(2**N):
    tmp = True
    for n,j in enumerate(s_bit):
        on_swich=bin(int(bin(i),0)&int(j,0))
        tmp = tmp and on_swich.count('1')%2==p[n]
    if tmp:
        ans += 1
print(ans)

Submission status: Accepted

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

param = []
for i in range(M):
    ks = [int(s)-1 for s in input().split()]

    x = 0
    for i in range(1, len(ks)):
        x += pow(2, ks[i])
    param.append(x)


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


ans = 0
for x in range(pow(2, N)):
    check = True
    for i in range(M):
        if bin(param[i] & x).count("1") % 2 != P[i]:
            check = False
            break

    if check:
        ans += 1

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

N, M = map(int, sys.stdin.readline().split(" "))

k = []
for i in range(M):
    tmp = list(map(int, sys.stdin.readline().split(" ")))
    k.append(tmp[1:])

p = list(map(int, sys.stdin.readline().split(" ")))

ans = 0
for i in range(2**N):
    switches = []
    for j in range(N):
        switches.append(i >> j & 1)
    # print(switches)
    for i, k_i in enumerate(k):
        on = 0
        for switch_i in k_i:
            # print(switch_i - 1)
            on += switches[switch_i - 1]
        if p[i] != on % 2:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
swi = []
for i in range(m):
    lis = list(map(int,input().split()))
    swi.append(lis[1:])
p = list(map(int,input().split()))
cnt = 0

for bit in range(2**n):
    lis = []
    for i in range(n):
        if ((bit >> i) & 1):
            lis.append(i+1)
            
    for j in range(m):
        if len(set(swi[j]) & set(lis)) % 2 == p[j]:
            ans = True
        else:
            ans = False
            break
    if ans:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
switch = [(i+1) for i in range(n)]
ks = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
pattern = [bin(i)[2:].zfill(n) for i in range(2**n)]

ans = 0

for i in pattern:
    on = []
    light = 0
    for j in range(n):
        if i[j] == '1':
            on.append(switch[j])
    for k in range(m):
        count = 0
        for l in range(1,ks[k][0]+1):
            if ks[k][l] in on:
                count += 1
        if count % 2 == p[k]:
            light += 1
    if light == m:
        ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ls = []
switch = [(i+1) for i in range(n)]
ls = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))

pattern = [bin(i)[2:].zfill(n) for i in range(2**n)]

ans = 0

for i in pattern:
    turn = []
    on = 0
    for j in range(n):
        if i[j] == '1':
            turn.append(switch[j])
    for k in range(m):
        count = 0
        for l in range(1,ls[k][0]+1):
            if ls[k][l] in turn:
                count += 1
        if count % 2 == p[k]:
            on += 1
    if on == m:
        ans += 1
            
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N,M = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
P = list(map(int,input().split()))
cnt = 0
for x in product((0,1),repeat=N):
    flag = 1
    for i in range(M):
        k = A[i][0]
        B = A[i][1:]
        B = [b-1 for b in B]
        c = 0
        for b in B:
            if x[b]==1:
                c += 1
        if c%2==P[i]:continue
        else:
            flag=0
            break
    if flag==1:
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

ans = 0
N,M = map(int,readline().split())
L = []

for i in range(M):
    k,*S = map(int,readline().split())
    L.append(S)

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

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

for i in A:
    sw = [False] * M
    for j in range(M):
        count = 0
        for k in L[j]:
            count += i[k-1]

        if count % 2 == P[j]:
            sw[j] = True
            
    if sum(sw) == M:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import itertools
import copy
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()
ans = 0
N, M = map(int, input().split())
ks = [tuple(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
t = []
for i in range(N):
    tt = list(itertools.combinations(range(1, N+1), i+1))
    for l in tt:
        t.append(l)
t.append(tuple())
for i in range(len(t)):
    pp = 0
    for l in range(M):
        if len(set(ks[l][1:]) & set(t[i])) % 2 == p[l]:
            pp += 1
    if pp == M:
        ans += 1
print(ans)