AT_abc128_c [ABC128C] Switches

题目描述

有 $n$ 个开关和 $m$ 个灯泡,每个开关都处于“开”和“关”状态中的一种。开关从 $1$ 到 $n$ 编号,灯泡从 $1$ 到 $m$ 编号。 $i$ 号灯泡连接着 $k_i$ 个开关:开关 $s_{i,1}$,$s_{i,2}$,...,$s_{i,k_i}$。当这些开关中,处于“开”状态的开关数量之和模 2 余 $p_i$ 时,这个灯泡就会被点亮。 有多少“开”和“关”的组合,可以点亮所有灯泡?

输入格式

输出格式

说明/提示

* $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$。