ABC 128C - 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)