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:
import sys
input=sys.stdin.readline

switch,denkyu=map(int,input().split())
connect=[]
for i in range(denkyu):
  l=list(map(int,input().split()))
  connect.append(l)
amari=list(map(int,input().split()))
okcombcounter=0
for i in range(2**switch):
  state=format(i,'b').zfill(switch)
  tentoucounter=0
  for j in range(denkyu):
    oncounter=0
    for k in range(connect[j][0]):
      if state[connect[j][k+1]-1]=='1':
        oncounter+=1
    if oncounter%2==amari[j]:
      tentoucounter+=1
  if tentoucounter==denkyu:
    okcombcounter+=1
print(okcombcounter)

Submission status: Accepted

Solution code:
from itertools import product
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()))

pro = product([0,1],repeat=N)
ans = 0
for pr in pro:
#    print(pr)
    flag = True
    for i in range(M):
        tmp = 0
        for p in S[i]:
            tmp += pr[p-1]
        if tmp % 2 != P[i]:
            flag = False
            break
    if flag: ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=[int(x) for x in input().split()]
SSS=[]#二次元配列
for _ in range(M):
    SSS.append([int(x) for x in input().split()][1:])
    
ps=[int(x) for x in input().split()]

def dfs(L,num):
    if len(L)==N:
        bol=True
        for m,SS in enumerate(SSS):
            r=0
            for s in SS: 
                r+=L[s-1]
            if r%2!=ps[m]:
                bol=False
                break
        if bol:
            return num+1
        else:
            return num
    else:
        num=dfs(L+[1],num)
        num=dfs(L+[0],num)
        return num

result=0
result=dfs([1],result)
result=dfs([0],result)
print(result)

Submission status: Accepted

Solution code:
from itertools import product

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

ans = 0
for l in product([False, True], repeat=n):
    sat = 0
    for si, pi in zip(s, p):
        cnt = 0
        for ssi in si:
            if l[ssi - 1]:
                cnt += 1

        if cnt % 2 != pi:
            break
        else:
            sat += 1
    if sat == m:
        ans += 1

print(ans)

Submission status: Accepted

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

ls = []
st = { i+1 for i in range(N) }
for i in range(M):
    inl = list(map(int, input().split()))
    switches = inl[1:]
    ls.append(switches)

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

res = [0]
def check(inpu = st, mp = {}, res_ = res):
    if len(inpu):
        val = inpu.pop()
        mp0 = mp.copy()
        mp0[val] = 0
        mp1 = mp.copy()
        mp1[val] = 1
        check(inpu.copy(), mp0)
        check(inpu.copy(), mp1)
    else:
        # print(mp)
        all_ = True
        for key, sws in enumerate(ls):
            summed = 0
            for sw in sws:
                summed += mp[sw]
            summed %= 2
            if summed != checker[key]:
                all_ = False
        if all_:
            res[0] += 1

check()
print(res[0])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
switch = [[] for i in range(n)]
for j in range(m):
    a = [(int(i) - 1) for i in input().split()]
    for aa in a[1:]:
        switch[aa].append(j)
p = [int(i) for i in input().split()]
ans = 0
for i in range(2 ** n):
    calc = [0 for _ in range(m)]
    k = bin(i)[2:]
    k = (n - len(k)) * ["0"] + list(k)
    for j, kk in enumerate(k):
        if kk == "1":
            for s in switch[j]:
                if calc[s] == 0:
                    calc[s] = 1
                else:                    
                    calc[s] = 0
    if calc == p:
        ans += 1
print(ans)

Submission status: Accepted

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

s_lists = []
for i in range(M):
  ss = list(map(int,input().split()))
  s_lists+= [ss[1:]]
  
P = list(map(int,input().split()))

def check(number,s_list,p):
    string = list(map(int,reversed("{:010b}".format(number))))
    cnt = 0
    for s in s_list:
        if string[s-1] == 1:
            cnt += 1
    if cnt % 2 == p:
        return True
    else:
        return False

cnt= 0
for i in range(2**N):
  if   all([check(i, s_lists[j],P[j]) for j in range(M)]):
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import itertools
n,m=map(int,input().split())
sw_list=[]
for i in range(m):
    num,*sw=map(int,input().split())
    sw_list.append(sw)
p_list=[int(i) for i in input().split()]

count=0

for pat in itertools.product(range(2), repeat=n):
    blnOK=True
    for i in range(m):
        sump=0
        for sw in sw_list[i]:
            if pat[sw-1]==1:
                sump+=1
        if sump%2!=p_list[i]:
            blnOK=False
    if blnOK:
        count+=1  

print(count)

Submission status: Accepted

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

res = 0
for i in range(2**n):
    x = bin(i)[2:][-n:].zfill(n)
    if all([sum([int(x[ii-1]) for ii in l[i]]) % 2 == p[i] for i in range(len(l))]):
        res += 1
print(res)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
swi = [[]for i in range(N)]
for i in range(M):
    tmp = list(map(int,input().split()))
    for j in tmp[1:]:
        swi[j-1].append(i)
p = list(map(int,input().split()))
ans = 0
for i in range(2**N,2**(N+1)):
    ramp = [0]*M
    i = bin(i)
    for j in range(N):
        if i[j+3] == "1":
            for k in swi[j]:
                ramp[k] += 1
    for i in range(M):
        ramp[i] = ramp[i]%2
    if ramp == p:
        ans += 1
print(ans)

Submission status: Accepted

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

ks = []
sss = []
for _ in range(M):
  inp = [int(i) for i in input().split()]
  ks.append(inp[0])
  sss.append(inp[1:])
  
ps = [int(i) for i in input().split()]

count = 0
for i in range(2**N):
  pattern = [(i >> j) & 1 for j in range(N)]
  ok = True
  for m in range(M):
    p = ps[m]
    ss = sss[m]
    
    if sum([int(pattern[s-1]) for s in ss]) % 2 == p:
      ok = True
    else:
      ok = False
      break
  if ok:
    count += 1
    
print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = []
for i in range(m):
    k.append(list(map(int, input().split())))
p = list(map(int, input().split()))
count = 0
for i in range(2**n):
    flag = True
    for q_idx, query in enumerate(k):
        count_p = 0
        for q in query[1:]:
            if (i & 2**(q-1)) > 0:
                count_p += 1
        if count_p % 2 != p[q_idx]:
            flag = False
    if flag:
        count += 1
print(count)

Submission status: Accepted

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

for i in range(2 ** n):
    flag = True
    for j in range(m):
        bit = 0
        for l in range(s[j][0]):
            bit += (i >> (s[j][l + 1] - 1)) & 1
        if not(bit % 2 == p[j]):
            flag = False
    if flag:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def dfs(N, M, Bulb, P, switches, cur):
  if cur == N:
    for i, b in enumerate(Bulb):
      s = 0
      for x in b[1:]:
        s += switches[x-1]
      if s % 2 != P[i]:
        return 0
    return 1
  else:
    a = 0
    switches[cur] = 0
    a += dfs(N, M, Bulb, P, switches, cur+1)
    switches[cur] = 1
    a += dfs(N, M, Bulb, P, switches, cur+1)
    return a

N, M = map(int, input().split())
Bulb = [list(map(int, input().split())) for _ in range(M)]
P = list(map(int, input().split()))
print(dfs(N, M, Bulb, P, [0] * N, 0))

Submission status: Accepted

Solution code:
l = raw_input().split()
N = int(l[0])
M = int(l[1])

K = []
S = []
P = []

for i in range(M):
    l = raw_input().split()
    t = [int(x) for x in l]
    K.append(t[0])
    S.append(t[1:])

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

# print(N, M, K, S, P)

def numBits(n):
    count = 0
    while n > 0:
        if n % 2 == 1:
            count += 1
        n /= 2
    return count

def solve(n, S, p):
    # print('nsp', n, S, p)
    count = 0
    for s in S:
        # print(s, n, n >> (s - 1))
        count += (n >> (s - 1)) & 1
    # print('count={}'.format(count))
    return p == (count  & 1)

ans = 0
for j in range(2**N):
    # print(j)
    ret = True
    for i in range(len(S)):
        s = S[i]
        p = P[i]
        # print(i, s, p)
        if not solve(j, s, p):
            ret = False
            break
    if ret:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

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

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

def dfs(sw, depth):
    if depth == N:
        for i in range(M):
            counter = 0
            for j in s[i]:
                if sw[j-1] == 1:
                    counter += 1
            if counter % 2 != p[i]:
                return 0
        return 1
    
    ans = 0
    copy1 = deepcopy(sw)
    copy2 = deepcopy(sw)
    copy1.append(0)
    copy2.append(1)
    ans += dfs(copy1, depth + 1)
    ans += dfs(copy2, depth + 1)
    return ans

print(dfs([], 0))

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappush, heappop, heapify, heapreplace

class Solution:
    def main(self):
        N, M = map(int, input().split())
        K = []
        S = []
        for i in range(M):
            line = list(map(int, input().split()))
            k = line[0]
            s = line[1:]
            K.append(k)
            S.append(s)
        P = list(map(int, input().split()))
        on = [0] * N
        #print(on)
        #print(S)
        res = 0
        for _ in range(2**N):
            # print(on)
            for i in range(M):
                if sum([on[idx-1] for idx in S[i]]) % 2 != P[i]:
                    break
            else:
                res += 1
            self.increment(on, 0)
        print(res)

    def increment(self, array, i):
        if len(array) <= i:
            return array
        elif array[i] == 0:
            array[i] = 1
            return array
        else:
            array[i] = 0
            return self.increment(array, i+1)


if __name__ == '__main__':
    Solution().main()

Submission status: Accepted

Solution code:
import itertools

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

K = []
S = []

for _ in range(M):
    i = [int(x) for x in input().split()]
    S.append([x-1 for x in i[1:]])

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

ans = 0
for pool in itertools.product(range(2), repeat=N):
    t = [0 for _ in range(M)]
    for i in range(M):
        for j in S[i]:
            if pool[j] == 1:
                t[i] += 1
    if all([x%2==P[i] for i, x in enumerate(t)]):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
import itertools

# n = int(input())
# a, b = map(int, input().split())
# int_list = list(map(int, input().split()))
# l = list(input().split())

def solve():
    k_list = []
    n, m = map(int, input().split())
    for i in range(m):
        row = list(map(int, input().split()))
        k = row[0]
        k_list.append(row[1:])
    p_list = list(map(int, input().split()))

    # print(n, m)
    # print(k_list)
    # print(p_list)

    # 全通り
    n_all_on = 0

    comb = [[0, 1]] * n
    for pattern in itertools.product(*comb):
        pat_on = True
        for iden in range(m):
            p = p_list[iden]
            on_s_iden = 0
            for isw in k_list[iden]:
                on_s_iden += pattern[isw-1]
            if p != on_s_iden % 2:
                pat_on = False
                break

        if pat_on == True:
            n_all_on += 1

    print(n_all_on)


solve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
s2m = [[]for n in range(N)]
for m in range(M):
    line = list(map(int, input().split()))
    for s in line[1:]:
        s2m[s-1].append(m)
p = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    msc = [0 for m in range(M)]
    bit = str(bin(i))[2:].zfill(N)
    for j, b in enumerate(bit):
        if b == '1':
            for m in s2m[j]:
                msc[m] += 1
    count = 0
    for k, sc in enumerate(msc):
        if sc % 2 == p[k]:
            count += 1
    if count == M:
        ans += 1

print(ans)

Submission status: Accepted

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

k = 0
count = 0
for i in range(2**n):
    ans = 1
    for j in range(m):
        ons = sum([int(format(i,'b').zfill(n)[-k]) for k in st[j]])
        # print(j," gg ", ons,"#",ons%2==p[j])
        if not ons%2==p[j]:
            ans=0
    if ans:
        count +=1

print(count)

Submission status: Accepted

Solution code:
import math
import fractions
import copy
#以下てんぷら
def j(q):
    if q==1: print("YES")
    elif q == 0:print("NO")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


#n = ip()                                     #入力整数1つ
n,m= (int(i) for i in input().split())       #入力整数横2つ以上
#a = [int(i) for i in input().split()]        #入力整数配列
#a = input()                                  #入力文字列
#a = input().split()                          #入力文字配列
#n = ip()                      #入力セット(整数改行あり)(1/2)
#a=[ip() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#a=[input() for i in range(n)]    #入力セット(整数改行あり)(2/2)
#jの変数はしようできないので注意
#全足しにsum変数使用はsum関数使用できないので注意
a =[]
for i in range(m):
    adder = [int(i)-1 for i in input().split()]
    adder.pop(0)
    a.append(adder)
sw =  [int(i) for i in input().split()]
ctsw = [0 for i in range(n)]
ctsw[0] = -1
suc = 0
while sum(ctsw)<n:
    p = 0
    ctsw[0]+=1
    if ctsw[p]==2:
        while ctsw[p] == 2:
            ctsw[p] = 0
            p+=1
            ctsw[p]+=1
    for i in range(m):
        use = a[i]
        total = 0
        for k in range(len(use)):
            d = use[k]
            total+=ctsw[d]
        if total%2 != sw[i]: break
        if total%2 == sw[i] and i == m-1:suc+=1
print(suc)

Submission status: Accepted

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

ans = 0
for i in range(2 ** n):
#  print("i=", i)
  flag = 1
  for j in range(m):
#    print("j=", j)
    cnt = 0
    for k in S[j]:
      cnt += (i >> (k - 1)) & 1
#    print(cnt)
    if cnt % 2 != P[j]:
      flag = 0
      break
  if flag == 1:
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
import sys


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

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

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

ans=0
for i in range(2**N):
    tmp=[p[i] for i in range(M)]
    s=bin(i)[2:].zfill(N)
    state=[int(s[i]) for i in range(N)]

    for j in range(M):
            for k in range(1,sw[j][0]+1):
                if state[sw[j][k]-1]==1:
                    tmp[j]=(tmp[j]+1)%2
    
    if max(tmp)==0: ans+=1

print(ans)

Submission status: Accepted

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

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

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

import itertools
cnt = 0
for tpl in itertools.product([0,1], repeat=N):
    f = True
    for m in range(M):
        c = 0
        for s in S[m]:
            c += tpl[s-1]
        # print(m, tpl, P[m], c)
        if (c%2+P[m])%2 != 0:
            f = False
            break
    if f:
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
den = [0 for i in range(M)]
for i in range(M):
    inputlist = list(map(int, input().split()))
    newlist = [k-1 for k in inputlist]
    den[i] = newlist[1:]
p = list(map(int, input().split()))
#print(den)
count = 0
for i in range(2** N):
    sinsu = bin(i)[2:].zfill(N)
    num = np.array([int(k) for k in list(sinsu)])
    now = True
    for j in range(M):
        sumnum = sum(num[den[j]])
        if sumnum % 2 != p[j]:
            now = False
            break
    if now:
        count += 1
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import itertools
MOD = 2  # type: int


def solve(N, M, k, s, p):
    count = 0
    bluteforce = list(itertools.product([0, 1], repeat = N))

    for b in range(len(bluteforce)):
        for i in range(M):
            temp = [bluteforce[b][x-1] for x in s[i]]
            if sum(temp) % 2 == p[i]:
                success = 1
                pass
            else:
                success = 0
                break
        if success == 1:
            count += 1
    print(count)

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N, M = map(int, input().split())
    k = []
    s = []
    for i in range(M):
        k_temp, s_temp = input().split(' ', 1)
        k.append(int(k_temp))
        s.append(list(map(int, s_temp.split())))
    p = list(map(int, input().split()))

    solve(N, M, k, s, p)
    pass


if __name__ == '__main__':
    main()

Submission status: Accepted

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

k = [list(map(int, input().split()))[1::] for i in range(M)]
p = list(map(int, input().split()))
switches = [format(i, "b").zfill(N) for i in range(2**N)]

ans = 0
for sw in switches:
    allt = True
    for i in range(M):
        sum = 0
        for s in k[i]:
            if(sw[s-1]=="1"):
                sum += 1
        if(sum%2!=p[i]):
            allt = False
            break
    if(allt):
        ans+=1

print(ans)

Submission status: Accepted

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

switch = []
for i in range(M):
  ks = input().split()
  k = int(ks[0])
  for j in range(k):
    if j == 0:
      switch.append([int(ks[j + 1]) - 1])
    else:
      switch[-1].append(int(ks[j + 1]) - 1)

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

com = 2 ** N
ans = 0
for i in range(com):
  cnt = 0
  for j in range(M):
    sw_cnt = 0
    for s in switch[j]:
      sw_cnt += int((i % (2 ** (s + 1))) / (2 ** s))
    if sw_cnt % 2 == p[j]:
      cnt += 1
  if cnt == M:
    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(" ")))

s = [set(ks[1:]) for ks in KS]
# l = [set() for _ in range(N)]
# for i, ks in enumerate(KS):
#     s = ks[1:]
#     for s_i in s:
#         l[s_i-1].add(i)
# print(l)

count = 0
for i in range(1<<N):
    t = set()
    for j in range(N):
        if (i>>j)%2:
            t.add(j+1)
            # print(j, end="_")
    # print(t, [len(s_i & t)%2==0 for s_i in s], s)
    if all(len(s_i & t)%2==P[k] for k, s_i in enumerate(s)):
        count += 1
            

print(count)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

n,m = m()

a = []

for i in range(m):
	a.append(l())

p = l()

su = 0
kk = []
for i in range(2**n):
	kk = []
	for j in range(m):
		co = 0
		for k in range(a[j][0]):
			if (i >> (n -(a[j][k+1])) & 1):
				co += 1
		kk.append(co)
	if all(kk[i] % 2 == p[i] for i in range(m)):
		su += 1
print(su)

Submission status: Accepted

Solution code:

import itertools

N, M = map(int, input().split())
k, s = [], []

for i in range(M):
    tmp = [int(j) for j in input().split()]
    k.append(tmp[0])
    s.append(tmp[1:])
p = [int(j) for j in input().split()]

ans = 0

for switch in itertools.product(range(2), repeat=N):
    flg = True
    for i in range(M):
        snum = 0
        for j in range(k[i]):
            if switch[s[i][j]-1]:
                snum += 1
        if snum % 2 == p[i]:
            continue
        else:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

Submission status: Accepted

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

ks = []
switch_to_light = [[] for _ in range(N)]

for i in range(M):
    t = list(map(int, input().split()))
    ks.append(list(map(lambda x: x - 1, t[1:])))
for i, k in enumerate(ks):
    for ss in k:
        switch_to_light[ss].append(i)

# print(ks)
# print(switch_to_light)

p = tuple(map(int, input().split()))
# print(p)

ans = 0
for i in range(1 << N):
    # print(bin(i).zfill(N))
    cnt = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            # スイッチjがON
            for light_idx in switch_to_light[j]:
                # print(light_idx, j, cnt)
                cnt[light_idx] += 1
    flg = True
    for j in range(M):
        if cnt[j] % 2 != p[j]:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ks_list = [list(map(int, input().split())) for _ in range(m)]
p_list = list(map(int, input().split()))
odd_list = []
even_list = []
for i in range(m):
    k = ks_list[i][0]
    s_list = ks_list[i][1:]
    p = p_list[i]

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

Submission status: Accepted

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

ans = 0
for i in range(2**N):
    is_correct = True
    for p in range(M):
        light = 0
        for sw in switches[p]:
            light += 1 if (i>>(sw-1)) & 1 else 0
        if light % 2 != extras[p]:
            is_correct = False
            break
    if is_correct:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split(" "))
masks = []
for _ in range(M):
    mask = 0
    for s in list(map(int, input().split(" ")))[1:]:
        mask += 1 << (s-1)
    masks.append(mask)
p = list(map(int, input().split(" ")))

ans = 0
for d in range(1 << N):
    flg = True
    for i in range(M):
        if bin(d & masks[i]).count("1") % 2 != p[i]:
            flg = False
            break
    if flg: ans += 1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from itertools import chain,combinations

words = lambda t : list(map(t, input().split()))

n,m = words(int)
ks = []
for i in range(m):
  ks.append(words(int))
  ks[i].pop(0)

ms = words(int)

#print(ks,ms)

def powerset(it):
  s = list(it)
  return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

ans = 0
for s in powerset([i+1 for i in range(n)]):
  n_on = 0
  for k,mods in zip(ks,ms):
    n_inc = 0
    for ink in k:
      if ink in s:
        n_inc += 1
    if n_inc % 2 == mods:
      n_on += 1
  if n_on == m:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())  # 複数数値入力
s = list()

for i in range(m):
    tmp = list(map(int, input().split()))  # 複数数値入力(リスト格納)
    s.append(tmp[1:])

p = list(map(int, input().split()))  # 複数数値入力(リスト格納)

# print(s)
ans = 0
# bit全探索
for i in range(2 ** n):
    flg = 0
    onswitchkosuu = [0] * m
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # j番目のスイッチがついているならここに入るよ
            for k in range(m):  # この中で各電球についてj番目のスイッチと接続されているかを確認
                if j+1 in s[k]:
                    onswitchkosuu[k] += 1

   # print(onswitchkosuu)    # これには各電球について何個のスイッチが押されているかが書いてある
    # この下で各電球がつくのかどうかを検証

    for j in range(m):
        if onswitchkosuu[j] % 2 != p[j]:
            flg = 1

    if flg == 0:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

s_m = []
for _ in range(M):
    flag = True
    num = 0
    for s in input().split():
        if flag:
            flag = not flag
        else:
            s = int(s)
            num += 2**(s-1)
    s_m.append(num)

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

# print(s_m)

cnt = 0
for i in range(2**N):
    flag = True
    for j in range(len(s_m)):
        n = s_m[j]
        n &= i
        tf = True if p[j] == 0 else False
        # print(i, n)
        for _ in range(N):
            if n & 1 == 1:
                tf = not tf
            n >>= 1
        if not tf:
            flag = False
            break
    if flag:
        cnt += 1

print(cnt)

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

Submission status: Accepted

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

from itertools import product

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 p in product([0,1],repeat=N):
    can = 0
    for i in range(M):
        res = 0
        for s in S[i]:
            if p[s-1] == 1:
                res += 1
        res %= 2
        if res == P[i]:
            can += 1
    if can == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N, M = list(map(int, input().split()))
light_sw = []
for _ in range(M):
    light_sw.append(list(map(lambda x: x-1, map(int, input().split()[1:]))))
P = list(map(int, input().split()))

count = 0
pro = product([0, 1], repeat=N)
for pr in pro:
    for i, sw in enumerate(light_sw):
        sw_sum = 0
        flag = True
        for k in sw:
            sw_sum += pr[k]
        if sw_sum%2 != P[i]:
            flag = False
            break
    if flag:
        count += 1
print(count)

Submission status: Accepted

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

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

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

result = 0
for i in itertools.product([0,1], repeat=N):
  for j in range(M):
    re = 0
    for s in lamp[j]:
      re += i[s-1]
    if re % 2 != P[j]:
      break
  else:
    result += 1
print(result)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
hoge = []
for i in range(M):
    K = input().split()
    hoge.append(K)
P = input().split()
count = 0
for i in range(2**N):
    L = bin(i)[2:]
    leng = len(L)
    for pu in range(leng,N):
        L = "0" + L
    for j in range(M):
        hu = 0
        for a in hoge[j][1:]:
            if L[int(a)-1] == "1":
                hu += 1
        if hu % 2 != int(P[j]):
            break
        if j == M-1:
            count += 1
print(count)

Submission status: Accepted

Solution code:
import itertools as it

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

s = []

for i in range(m):

    k, *temp = map(int, input().split())

    s.append(set(temp))

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

ans = 0

if all([temp == 0 for temp in p]):
    ans += 1

for i in range(1, n + 1):

    for comb in it.combinations(list(range(1, n + 1)), i):

        flag = [False] * m

        for j in range(m):

            count = 0

            for k in range(i):

                if comb[k] in s[j]:
                    count += 1

            if count % 2 == p[j]:
                flag[j] = True

        if all(flag):
            ans += 1

print(ans)

Submission status: Accepted

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

K, S_list = list(), list()
for i in range(M):
  k, *S = map(int, input().split())
  # K.append(K)
  S_list.append(set(S))
P = list(map(int, input().split()))


def search(N, status=set()):
  if N == 0:
    yield status
  else:
    yield from search(N-1, status=status | {N})
    yield from search(N-1, status=status)


ans = 0
for status in search(N):
  for p, S in zip(P, S_list):
    if len(S & status) % 2 != p:
      break
  else:
    ans += 1
print(ans)