#47 Problem
** Thoughts ** Looking at the constraints, $ N and M $ are as small as 10 or less, so I thought that I could solve them by force, so I implemented it. Since the switch is on / off, all bits are searched. The amount of calculation is $ O (2 ^ N) $, but since $ N $ is small, it does not TLE. Create a bool list in which each element shows the on / off state of each switch, and check the lighting status of the light bulb in each state.
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(2 ** n):
on = [False] * n
for j in range(n): #bit full search
if ((i>>j) & 1):
on[n - j - 1] = True
g = 0
for j in range(m): #Status of each light bulb
c = 0
for s in range(1,len(ks[j])):
if on[ks[j][s]-1]:
c += 1
if c % 2 == p[j]: #If the light bulb is on, g+=1
g += 1
if g == m: #Ans if all g are lit+=1
ans += 1
print(ans)
Recently, I've been implementing it roughly because the amount of calculation is small, so I will do my best to read the explanation carefully and implement it neatly. See you again, good night.
Recommended Posts