A7664. [ABC128C] Switches
编程题
普及-
知识点
题目描述
有 $n$ 个开关和 $m$ 个灯泡，每个开关都处于“开”和“关”状态中的一种。开关从 $1$ 到 $n$ 编号，灯泡从 $1$ 到 $m$ 编号。
$i$ 号灯泡连接着 $k_i$ 个开关：开关 $s_{i,1}$，$s_{i,2}$，...，$s_{i,k_i}$。当这些开关中，处于“开”状态的开关数量之和模 2 余 $p_i$ 时，这个灯泡就会被点亮。
有多少“开”和“关”的组合，可以点亮所有灯泡？
$i$ 号灯泡连接着 $k_i$ 个开关：开关 $s_{i,1}$，$s_{i,2}$，...，$s_{i,k_i}$。当这些开关中，处于“开”状态的开关数量之和模 2 余 $p_i$ 时，这个灯泡就会被点亮。
有多少“开”和“关”的组合，可以点亮所有灯泡？
输入格式
输入来自以下格式的标准输入：
> $N$ $M$
$k_1$ $s_{1,1}$ $s_{1,2}$ $...$ $s_{1,k_1}$
$:$
$k_M$ $s_{M,1}$ $s_{M,2}$ $...$ $s_{M,k_M}$
$p_1$ $p_2$ $...$ $p_M$
> $N$ $M$
$k_1$ $s_{1,1}$ $s_{1,2}$ $...$ $s_{1,k_1}$
$:$
$k_M$ $s_{M,1}$ $s_{M,2}$ $...$ $s_{M,k_M}$
$p_1$ $p_2$ $...$ $p_M$
输出格式
输出一个数，表示有多少总组合方案可以点亮所有灯泡。
输入输出样例
输入 #1
2 2 2 1 2 1 2 0 1
输出 #1
1
输入 #2
2 3 2 1 2 1 1 1 2 0 0 1
输出 #2
0
输入 #3
5 2 3 1 2 5 2 2 3 1 0
输出 #3
8
说明/提示
* $1\le N,M \le 10$
* $1 \le k_i \le N$
* $1 \le s_{i,j} \le N$
* $s_{i,a} \neq s_{i,b} (a \neq b)$
* $p_i$ 只能是 $0$ 或 $1$
* 上述所有值都是整数
#### 样例 1/样例 4
* 灯泡 $1$ 当以下开关里开着的总数是偶数时会亮：开关 $1$ 和 $2$。
* 灯泡 $2$ 当以下开关里开着的总数是奇数是会亮：开关 $2$。
开关 $1$ 和 $2$ 一共组成了四种组合：(开，开)，（开，关），（关，开）和（关，关）。其中只有（开，开）满足要求，所以输出 $1$。
#### 样例 2/样例 5
* 灯泡 $1$ 当以下开关里开着的总数是偶数时会亮：开关 $1$ 和 $2$。
* 灯泡 $2$ 当以下开关里开着的总数是偶数时会亮：开关 $1$。
* 灯泡 $3$ 当以下开关里开着的总数是奇数时会亮：开关 $2$。
为了点亮灯泡 $2$，开关 $1$ 必须是关着的；为了点亮灯泡 $3$，开关 $2$ 必须是开着的。但这样灯泡 $1$ 就不能被点亮了。所以，没有组合能让所有灯泡亮起来，故输出 $0$。
* $1 \le k_i \le N$
* $1 \le s_{i,j} \le N$
* $s_{i,a} \neq s_{i,b} (a \neq b)$
* $p_i$ 只能是 $0$ 或 $1$
* 上述所有值都是整数
#### 样例 1/样例 4
* 灯泡 $1$ 当以下开关里开着的总数是偶数时会亮：开关 $1$ 和 $2$。
* 灯泡 $2$ 当以下开关里开着的总数是奇数是会亮：开关 $2$。
开关 $1$ 和 $2$ 一共组成了四种组合：(开，开)，（开，关），（关，开）和（关，关）。其中只有（开，开）满足要求，所以输出 $1$。
#### 样例 2/样例 5
* 灯泡 $1$ 当以下开关里开着的总数是偶数时会亮：开关 $1$ 和 $2$。
* 灯泡 $2$ 当以下开关里开着的总数是偶数时会亮：开关 $1$。
* 灯泡 $3$ 当以下开关里开着的总数是奇数时会亮：开关 $2$。
为了点亮灯泡 $2$，开关 $1$ 必须是关着的；为了点亮灯泡 $3$，开关 $2$ 必须是开着的。但这样灯泡 $1$ 就不能被点亮了。所以，没有组合能让所有灯泡亮起来，故输出 $0$。