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())
kk = []
ss = []
for i in range(m):
    ks = list(map(int, input().split()))
    k = ks[0]
    s = ks[1:]
    kk.append(k)
    ss.append(s)
p = list(map(int, input().split()))
ans = 0

for i in range(2 ** (n)):
    check = [0 for i in range(m)]
    for j in range(n):
        if i >> j & 1:
            for l in range(m):
                if (j + 1) in ss[l]:
                    check[l] = (check[l] + 1) % 2
    if check == p:
        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()))
count = 0
for i in range(2 ** n):
    on_number = [0] * m
    for j in range(n):
        if i >> j & 1:
            for k in range(m):
                if (j + 1) in s[k][1:]:
                    on_number[k] += 1
    flag = 0
    for k in range(m):
        if on_number[k] % 2 == p[k]:
            flag += 1
        if flag == m:
            count += 1
print(count)

Submission status: Accepted

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

ans = 0
for i in range(2 ** n):
    for j in range(m):
        cnt = 0
        for k in range(n):
            if i >> k & 1 and k + 1 in ks[j]:
                cnt += 1
        if cnt % 2 != p[j]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
Q = []
for _ in range(m):
    q = list(map(int, input().split()))
    Q.append(q)
p = list(map(int, input().split()))
ans = 0
#　全てのスイッチパターンを列挙
for pattern in range(2 ** n):
    #p = bin(p)
    for i in range(len(Q)):
        on_cnt = 0
        for j in range(1, len(Q[i])):
            if ((pattern >> (Q[i][j] - 1)) & 1):
                on_cnt += 1
        if on_cnt % 2 != p[i]:
            break
    else:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
k=[list(map(int,input().split()))for _ in range(M)]
p=list(map(int,input().split()))
import itertools
import operator
import functools
print(sum(1 for i in itertools.product([True,False],repeat=N)if functools.reduce(operator.and_,[functools.reduce(operator.xor,[i[j-1]for j in k[l][1:]])==p[l]for l in range(M)])))

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def bit_search(n):
    res = []
    for i in range(2**n):
        st = set()
        for j in range(n): 
            if ((i >> j) & 1):
                st.add(j)
        res.append(st)
    return res

def main():
    N,M=mi()
    X = {}
    for i in range(M):
        inp = list(mi())
        X[i] = inp[1:]
    
    P = list(mi())

    ans = 0
    for combs in bit_search(N):
        res = 0
        for i in range(M):
            on_count = 0
            for j in range(len(X[i])):
                s = X[i][j] - 1 # 0-index
                if s in combs:
                    on_count += 1
            
            if on_count % 2 == P[i]:
                res += 1

        if res == M:
            ans += 1


    print(ans)
                    





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
s = []
for _ in range(M):
    s.append(list(map(lambda x:int(x)-1,input().split()))[1:])
p = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    fl = True
    for j in range(M):
        cnt = 0
        for sw in s[j]:
            if (i >> sw) & 1:
                cnt += 1
        if cnt % 2 != p[j]:
            fl = False
            break
    if fl:
        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()))
ans,cnt=0,0
for n in range(2**N):
  for m in range(M):
    cnt=0
    for i in range(N):
      if (n>>i)&1 and i+1 in s[m]:
        cnt+=1
    if cnt%2!=p[m]:
      break
  else:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
combiList = []
for i in range (M):
  combiList.append(list(map(int, input().split())))
kakuninList = list(map(int, input().split()))
statusList = [0]*M

for j in range (M):
  combiList[j].pop(0)
res = 0
# 010 なら2番目のみ派閥 
for bits in range(2**N): #k番目のグループ
  flag = True
  statusList = [0]*M
  for j in range(N):
    if((bits>>j) & 1): 
      for k in range(M):
        if j+1 in combiList[k]:
          statusList[k] +=1
  for k in range(M):
    if statusList[k] % 2 != kakuninList[k]:
      flag = False
      break
  if flag:
    res +=1
print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split()) # Nはスイッチの数、Mは電球の数
lights = [[0] * N for _ in range(M)]
for i in range(M): 
    temp = list(map(int, input().split())) # 0番目はスイッチの個数、1番目以降はスイッチを示す
    k = temp[0]
    switches = temp[1:]
    for j in range(k):
        lights[i][switches[j]-1] = 1
P = list(map(int, input().split())) # 個数を2で割ったあまりが要素と等しい場合に点灯する

answer_count = 0
for i in range(2**N):
    flag = True
    for k in range(M):
        count = 0
        for j in range(N):
            if (i >> j) & 1:
                count += lights[k][j]
        if count % 2 != P[k]:
            flag = False
            break
    if flag:
        answer_count += 1

print(answer_count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
k = [0] * M
s = [0] * M
for i in range(M):
    s[i] = list(map(int, input().split()))
    k[i] = s[i].pop(0)
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):
        if sum([int(b[x-1]) for x in s[j]]) % 2 != p[j]:
            break
        if j == M - 1:
            ans += 1

print(ans)

Submission status: Accepted

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

    ans = 0
    for i in range(2**n):
        ls = [0]*m
        for j in range(n):
            if i & (1 << j):
                for k in range(m):
                    if j+1 in ks[k][1:]:
                        ls[k] += 1
        cnt = 0
        for l in range(m):
            if ls[l] % 2 == p[l]:
                cnt += 1
        if cnt == m:
            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()))[1:] for _ in range(m)]
p = list(map(int, input().split()))
ans = 0

for i in range(2**n):
    status = ['+']*n
    for j in range(n):
        if ((i>>j)&1):
            status[j] = '-'
    num = 0
    for m, k in enumerate(s):
        count = 0
        for l in k:
            if status[l-1] == '+':
                count += 1
        if count%2 != p[m]:
            break
        else:
            num += 1
    if num == m+1:
        ans += 1
print(ans)

Submission status: Accepted

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

Ks = []
for _ in range(M):
  Ks.append(set(list(map(int, input().split()))[1:]))
  
Ps = list(map(int, input().split()))

rlt = 0
pw = 2**N

for b in range(pw):
  lst = [0]*(M)
  tmp = 0
  for i in range(N):
    if b&(1<<i):
      for j in range(M):
        if i+1 in Ks[j]:
          lst[j] += 1
  for j in range(M):
    if lst[j] % 2 == Ps[j]:
      tmp += 1
  if tmp == M:
    rlt += 1
  
print(rlt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    N, M = map(int, input().split())
    k, s = [], []
    for _ in range(M):
        lst = [int(x) - 1 for x in input().split()]
        k.append(lst.pop(0) + 1)
        s.append(set(lst))
    p = [int(x) for x in input().split()]

    ans = 0
    for bit in range(1 << N):
        now_on_switch = []
        for i in range(N):
            if bit & (1 << i):
                now_on_switch.append(i)
        lights = 0
        for i in range(M):
            cnt = 0
            for j in now_on_switch:
                cnt += 1 if j in s[i] else 0
            lights += 1 if cnt % 2 == p[i] else 0
        ans += 1 if lights == M else 0
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0

for i in range(2 ** N):
    flg = 1
    for j in range(M):
        o = 0
        for k in range(1, I[j][0]+1):
            if (i >> (I[j][k]-1)) & 1:
                o += 1
        if o % 2 != p[j]:
            flg = 0
            break
    if flg == 1:
        ans += 1
print(ans)

Submission status: Accepted

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

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

# calc
# bit full search
ans = 0 
for i in range(2**n):
    tmp = i 
    sw = []
    if i == 0:
        sw = [0] 
    while tmp > 0:
        sw.append(tmp&1)
        tmp = tmp>>1
    while len(sw) < n:
        sw.append(0)

    #print('sw =', sw)
    
    # check whether current sw satisfies the condision.
    ok = True
    # light bulb j
    for j in range(m):
        tmp = 0 
        for a in range(k[j]):
            tmp += sw[s[j][a]-1]
        if tmp%2 != p[j]:
            ok = False
            break
    if ok: 
        # print('sw =', sw)
        ans += 1

print(ans)

Submission status: Accepted

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

count = 0

for i in range(2**n):

    for j in range(m):
        switch = 0
        for k in range(n):
            if (i >> k) & 1 and k+1 in d[j]:
                switch += 1
        if switch%2 != s[j]:
            break
    else:
        count += 1

print(count)

Submission status: Accepted

Solution code:
N, M = 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 n in range(2 ** N):
  t = [(n >> i) & 1 for i in range(N)]
  f = 0
  for j in range(M):
    c = 0
    for k in S[j][1:]:
      c ^= t[k-1]
    if c != P[j]:
      f = 1
      break
  if f == 0:
    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()))
count = 0
for i in range(1<<N):
    for m in range(M):
        switch=0
        for j in range(N):
            if (i>>j)&1 and j+1 in s[m]:
                switch += 1
        if switch%2!= p[m]:
            break
    else:
        count += 1
print(count)

Submission status: Accepted

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

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

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

for i in range(2 ** N):
    switch = []
    for j in range(N):  # スイッチの押し方を全探索
        if (i >> j) & 1:
            switch.append(j+1)
    bulb_count = M
    for k in range(M):  # M個の電球それぞれがついているか判定
        tmp = bulb[k]  # tmpは電球k につながっているスイッチ
        switch_count = 0
        for num in tmp:  # 電球kのスイッチについて判定
            if num in switch:
                switch_count += 1
        if switch_count % 2 == P[k]:
            bulb_count -= 1
    if bulb_count == 0:
        count += 1

print(count)

Submission status: Accepted

Solution code:
import numpy as np
N,M = map(int, input().split())
S = []
for i in range(M):
    k,*s = map(int, input().split())
    T = [0]*N
    for j in s:
        T[j-1]=1
    S.append(T)
P = list(map(int, input().split()))
ans =0
for x in range(2**N):
    y = format(x,"0{}b".format(N))
    z = list(map(int,y))
    if all(np.dot(den,z)%2==P[nmb] for nmb,den in enumerate(S)):
        ans +=1
            
print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplt(n): return [tuple(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,m = inpm()
S = inpll(m)
P = inpl()

ans = 0
for bi in itertools.product([0,1],repeat=n):
    for i in range(m):
        cnt = 0
        for j in range(S[i][0]):
            if bi[S[i][j+1]-1] == 1:
               cnt += 1
        if cnt%2 != P[i]:
            break
        else:
            continue
        break
    else:
        ans += 1

print(ans)

Submission status: Accepted

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

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

for i in range(m):
	k,*t = map(int,input().split())
	for j in t:
		s[i].append(j-1)

targ = list(map(int,input().split()))
ans = 0
#print(s)

for i in itertools.product(range(2), repeat=n):
	tmpl = [0]*m
	
	for j in range(m):
		for k in s[j]:
			tmpl[j] += i[k]
	
	mode = 1
	
	for j in range(m):
		if tmpl[j]%2 != targ[j]:
			mode = 0
			break
	
	if mode:
		ans += 1

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(1 << n):
    ok = True
    for j in range(m):
        cnt = 0
        for k in range(len(sl[j])):
            if (i >> sl[j][k] - 1)%2 == 0:
                cnt += 1
        if cnt%2 != p[j]:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

Submission status: Accepted

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

Nlen = 2**N
ans = 0

for i in range(Nlen):
    total = 0
    for j in range(M):
        count = 0
        for k in range(1,ks[j][0]+1): 
            if i & 2**(ks[j][k]-1) == 2**(ks[j][k]-1):
                count += 1
        if count % 2 == p[j]:
            total += 1
    if total == M:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m  = map(int, input().split())
lst = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
d = [0]*(n+1)
s = 0
for i in range(2**n):
  for j in range(n):
    if i & (1<<j):
      d[j+1] = 1
    else:
      d[j+1] = 0
  for k in range(m):
    a = 0
    for l in range(1, lst[k][0]+1):
      a = (a+d[lst[k][l]])%2
    if a!=p[k]:
      break
  else:
    s += 1

print(s)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    S = []
    for _ in range(M):
        S.append(set(list(map(int, input().split()))[1:]))
    P = list(map(int, input().split()))

    ans = 0
    for bit in range(1 << N):
        on_switches = set([])
        for i in range(N):
            if bit & (1 << i):
                on_switches.add(i + 1)

        flag = True
        for s, p in zip(S, P):
            if len(s & on_switches) % 2 != p:
                flag = False
        if flag is True:
            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 _ in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    lights = [0]*m
    onoff = [0]*n
    for j in range(n):
        if (i >> j) &  1:
            onoff[j] = 1
    for k in range(m):
        cnt = 0
        for l in s[k][1:]:
            if onoff[l-1] == 1:
                cnt += 1
        if cnt % 2 == p[k]:
            lights[k] = 1
    if all(g == 1 for g in lights):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
	N, M = [int(n) for n in input().split(" ")]
	lights_def = [[0] * (N + 1) for i in range(M)]
	# lights_def[i] = List, i-th light (i = 0 ~ M)
	# lights_def[i][j] = 1 / 0, j-th switch is related (j = 1 ~ N)
	for i in range(M):
		tmp = [int(t) for t in input().split(" ")]
		for j in tmp[1:]:
			lights_def[i][j] = 1
	p = [int(x) for x in input().split(" ")]
	for i in range(len(p)):
		lights_def[i][0] = p[i]

	cnt = 0
	for i in range(2 ** N):
		switch_bit = list(pad_zero(format(i, 'b'), N))
		for j in range(len(lights_def)):
			light = lights_def[j]
			if sum([light[k + 1] for k in range(len(switch_bit)) if switch_bit[k] == "1"]) % 2 != light[0]:
				break
		else:
			cnt += 1

	print(cnt)

def pad_zero(s, n):
	s = str(s)
	return (("0" * n) + s)[-n:]

main()

Submission status: Accepted

Solution code:
#
# abc128 c
#

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2 2
2 1 2
1 2
0 1"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2 3
2 1 2
1 1
1 2
0 0 1"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5 2
3 1 2 5
2 2 3
1 0"""
        output = """8"""
        self.assertIO(input, output)


def resolve():
    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 bit in range(1 << N):
        m = 0
        for i in range(M):
            t = 0
            for j in range(1, S[i][0]+1):
                if bit & (1 << (S[i][j]-1)):
                    t += 1
            if t % 2 != P[i]:
                break
            else:
                m += 1
        if m == M:
            ans += 1
    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
#
# abc128 c
#

import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2 2
2 1 2
1 2
0 1"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2 3
2 1 2
1 1
1 2
0 0 1"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5 2
3 1 2 5
2 2 3
1 0"""
        output = """8"""
        self.assertIO(input, output)


def resolve():
    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 bit in range(1 << N):
        m = 0
        for i in range(M):
            t = 0
            for j in range(1, S[i][0]+1):
                if bit & (1 << (S[i][j]-1)) != 0:
                    t += 1
            if t % 2 != P[i]:
                break
            else:
                m += 1
        if m == M:
            ans += 1
    print(ans)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
def is_all_on(on_switches):
    on_cnt = 0
    for i in range(M):#電球の数
        cnt = 0
        for on in on_switches:
            if on in lights[i]: #i個目の電球と繋がってるスイッチの中にonになってるものがあるか
                cnt += 1
        if cnt % 2 == P[i]:        
            on_cnt += 1
    return True if on_cnt == M else False        
            
N,M = map(int,input().split())
lights = []
for m in range(M):
    lights.append(list(map(lambda x:int(x) - 1,input().split()))[1:])
P = list(map(int,input().split()))
#print(lights)

ans = 0
for i in range(1 << N): #スイッチon/offの全パターン数
    on_switches = []
    for j in range(N): #スイッチの数
        if ((i >> j) & 1) == 1: #１が立ってるスイッチがonのスイッチ
            on_switches.append(j) 
    if is_all_on(on_switches): ans += 1 #全ての電球が点灯しているかをチェック
    #print(i,on_switches)    
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
KS=[list(map(int,input().split())) for _ in range(M)]
p=list(map(int,input().split()))
ans=0
for i in range(1<<N):
  judge=1
  for j in range(M):
    cnt=0
    for k in KS[j][1:]:
      if i>>(k-1)&1:
        cnt+=1
    if (cnt%2)!=p[j]:
      judge=0
  if judge==1:
    ans+=1
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(0,2**N):
    n = format(i,'010b')
    for j in range(M):
        pj = 0
        for k in range(len(s[j])):
            pj += int(n[10-s[j][k]])
        if p[j] != pj%2:
            break
        if j == M-1:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import itertools

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

lis=[]

for _ in range(m):
  lis.append(list(map(int,input().split())))

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

ans=0
for binary in itertools.product([0,1],repeat=n):
  check=0
  for i in range(m):
    numon=0
    ki=lis[i][0]
    for j in range(ki):
      numon+=binary[lis[i][j+1]-1]
    if (numon+p[i])%2!=0:
      check+=1
  if check==0:
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip.split())
def main():
    n,m = LI()
    s = [[] for i in range(n)]
    ans = 0
    for i in range(1,m+1):
        lst = LI()
        for j in lst[1:]:
            s[j-1].append(i)
    p = [0] + LI()
    # print(n,m,s,p)
    bits = itertools.product([0,1],repeat=n)
    for bit in bits:
        lst = [0 for _ in range(m+1)]
        for i in range(n):
            if bit[i] == 1:
                for j in s[i]:
                    lst[j] = not lst[j]
        if lst == p:
            ans+= 1
    print(ans)
main()

Submission status: Accepted

Solution code:
n,m=[int(x) for x in input().split()]
s=[]
for i in range(m):
  k=[int(x) for x in input().split()]
  s.append(k)
p=[int(x) for x in input().split()]

import itertools
l=[]
a=itertools.product(range(2),repeat=n)
for i in a:
  l.append(i)

ans=0
for i in range(2**n):
  ok=[]
  for j in range(m):
    on=0
    for t in range(1,s[j][0]+1):
      e=s[j][t]
      if l[i][e-1]==1:
        on+=1
    if on%2!=p[j]:
      ok.append(False)
  if False not in ok:
    ans+=1

print(ans)

Submission status: Accepted

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

#print(n, m, s, p)
#print(s)
#各スイッチのon/offパターン
#0b0000000000~#0b1111111111を全部作成
sw2 = []
for i in range (1 << n):
    #各電球が点灯しているかどうか
    sw =  []
    for j in range(m):
        #各電球に関するスイッチに関するon/offパターンを全て列挙(関連しないスイッチはoff)
        cnt = 0
        for k in range(1, len(s[j])):
            if i >> (s[j][k] - 1) & 1 == 1:
                cnt += 1
            else:
                cnt += 0
            #print(bin(i), j, k, cnt)
        sw.append(cnt)
        #print(sw)
    sw2.append(sw)
#print(sw2)

ans2 = 0
for j in range(len(sw2)):
    ans = 0
    for k in range(len(sw2[j])):
        if sw2[j][k] % 2 == p[k]:
            ans += 1
    if ans == len(sw2[j]):
        ans2 += 1

print(ans2)
#     sw_cnd = []
#     for j in range(len[sw]):
#         for k in range(m):
#             if  sw[j][k] % 2 == p[j]:
#                 i_bin = bin(i)
#                 sw_cnd.append(i_bin)
#
# sw = set(sw)
# print(sw)
# print(len(sw))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
def end_of_loop():raise StopIteration
    
    
def main():
    N, M = MI()
    Switch = [LI() for i in range(M)]
    P = LI()
    result = 0
    for i in range(2**N):
        result += 1
        for index, swich in enumerate(Switch):
            if swich[0] == 0:
                continue
            temp = 0
            for j in range(swich[0]):
                if i >> (swich[j+1]-1) & 1 == 1:
                    temp += 1
            if temp % 2 != P[index]:
                result-=1
                break
            
    print(result)
                    
                    
            
            
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
s = list(list(map(int, input().split())) for _ in range(m)) 
p = list(map(int,input().split()))
ans = 0
for i in range(1<<n):
    # 全switch(n)のon/offパターン数
    sw = [False]*m
    # 各電球の点灯リストを作成
    for j in range(m):
        # 各電球について
        cnt = 0
        for k in range(1,len(s[j])):
            if i>>s[j][k]-1&1:
                cnt += 1
        if cnt%2==p[j]:
            sw[j]=True
    if all(sw):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
comb = []
for _ in range(m):
    comb.append(list(map(int,input().split()))[1:])
point = list(map(int,input().split()))
ans = 0
for i in range(2**n): #スイッチのon/offの組み合わせは2**n通りある
    on = [0]*m
    for j in range(n): #それぞれ何個めがonになっているか調べる
        if (i>>j)&1: #j個目がonになっているとき
            for k in range(m): #それぞれの電球に対して
                if j+1 in comb[k]: #もしj個目のon/offが電球kに関係するなら
                    on[k] += 1 #電球kに関してonポイントを与える
                    on[k] %= 2 #onポイントは偶奇のみ議論する
    if point==on: #もしこの組み合わせのon/offパターンが所与の条件に一致するなら
        ans += 1 #全ての電灯が一致する組み合わせが一つ見つかったことになる
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
comb = []
for _ in range(m):
    comb.append(list(map(int,input().split()))[1:])
point = list(map(int,input().split()))
ans = 0
for i in range(2**n): #スイッチのon/offの組み合わせは2**n通りある
    on = [0]*m
    for j in range(n): #それぞれ何個めがonになっているか調べる
        if (i>>j)&1: #j個目がonになっているとき
            for k in range(m): #それぞれの電球に対して
                if j+1 in comb[k]: #もしj個目のon/offが電球kに関係するなら
                    on[k] += 1 #電球kに関してonポイントを与える
                    on[k] %= 2 #onポイントは偶奇のみ議論する
    if all(point[l]==on[l] for l in range(m)): #もしこの組み合わせのon/offパターンが所与の条件に一致するなら
        ans += 1 #全ての電灯が一致する組み合わせが一つ見つかったことになる
print(ans)

Submission status: Accepted

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

def cntbin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
            count += int(i)
    return count

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

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

ans=0
for i in range(2**n):
    ok=True
    for mm in range(m):
        if not ok:break
        mask=0
        for ss in s[mm]:
            mask+=1 << ss-1
        on=cntbin(i&mask)
        if p[mm]!=on%2:
            ok=False

    if ok:ans+=1

print(ans)

Submission status: Accepted

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

On = [True for i in range(N)]
K = [0 for j in range(M)]
S = []

for j in range(M):
  inp = list(map(int, input().split(' ')))
  K[j] = inp[0]
  S.append(inp[1:])
  
P = list(map(int, input().split(' ')))


def check_condition(On, K, S, P):
  for j in range(len(K)):
    on_sum = 0
    for k in range(K[j]):
      if On[S[j][k]-1]: on_sum += 1
    if on_sum%2 != P[j]:
      return False
  return True

def enum_patterns(On, index, K, S, P):
  off = On.copy()
  off[index] = False
  if index == len(On)-1:
    count = check_condition(On, K, S, P) + check_condition(off, K, S, P)
  else:
    count = enum_patterns(On, index+1, K, S, P) + enum_patterns(off, index+1, K, S, P)
  return count


print(enum_patterns(On, 0, K, S, P))