Switches

题目描述

我们有 $N$ 个开关，具有“开”和“关”的状态，还有 $M$ 个灯泡。开关编号为 $1$ 到 $N$，灯泡编号为 $1$ 到 $M$。 灯泡 $i$ 连接到 $k_i$ 个开关：开关 $s_{i1}$、$s_{i2}$、$...$ 和 $s_{ik_i}$。当这些开关中处于“开”的开关数量对 $2$ 取模后与 $p_i$ 同余时，灯泡会点亮。 有多少种开关“开”“关”状态的组合能使所有灯泡都点亮？

输入格式

输入按下述格式从标准输入给出： $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$

输出格式

输出使所有灯泡都点亮的开关“开”“关”状态组合的个数。

2 2
2 1 2
1 2
0 1

1

2 3
2 1 2
1 1
1 2
0 0 1

0

5 2
3 1 2 5
2 2 3
1 0

8

提示

$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$ 是 $0$ 或 $1$。 输入中的所有值都是整数。当以下开关中处于“开”的数量为偶数时，灯泡 $1$ 会点亮：开关 $1$ 和 $2$。 当以下开关中处于“开”的数量为奇数时，灯泡 $2$ 会点亮：开关 $2$。

（开关 $1$, 开关 $2$）共有四种可能的状态组合：(开, 开)、(开, 关)、(关, 开) 和 (关, 关)。在它们之中，只有 (开, 开) 能使所有灯泡点亮，因此我们应该输出 $1$.
当以下开关中处于“开”的数量为偶数时，灯泡 $1$ 会点亮：开关 $1$ 和 $2$。 当以下开关中处于“开”的数量为偶数时，灯泡 $2$ 会点亮：开关 $1$。 当以下开关中处于“开”的数量为奇数时，灯泡 $3$ 会点亮：开关 $2$。

要使灯泡 $2$ 点亮，开关 $1$ 必须为“关”，要使灯泡 $3$ 点亮，开关 $2$ 必须为“开”，但这样灯泡 $1$ 就不会点亮。因此，没有任何开关状态组合能使所有灯泡点亮，所以我们应该输出 $0$.

标签: AtCoder|abc128C

来源

AtCoder|abc128C