ABC 128C - Switches

問題概要

C - Switches

解法(解説AC)

bit全探索を行う。
この問題系は虚無でbit全探索も判定も書けるようにしたい。

提出コード

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n, m = readmi()
sw = []
count = 0
d = defaultdict(int)

for i in range(m):
    p = readl()
    sw.append(p[1:])
p = readl()
count = 0
for i in range(2 ** n):
    den = defaultdict(int)
    for j in range(n):
        if (i >> j) & 1:
            for k in range(m):
                if j + 1 in sw[k]:
                    den[k] += 1
    flg = True
    for j in range(m):
        if den[j] % 2 != p[j]:
            flg = False
    if flg:
        count += 1
print(count)