101282: [AtCoder]ABC128 C - Switches

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $300$ points

Problem Statement

We have $N$ switches with "on" and "off" state, and $M$ bulbs. The switches are numbered $1$ to $N$, and the bulbs are numbered $1$ to $M$.

Bulb $i$ is connected to $k_i$ switches: Switch $s_{i1}$, $s_{i2}$, $...$, and $s_{ik_i}$. It is lighted when the number of switches that are "on" among these switches is congruent to $p_i$ modulo $2$.

How many combinations of "on" and "off" states of the switches light all the bulbs?

Constraints

  • $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$ is $0$ or $1$.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of combinations of "on" and "off" states of the switches that light all the bulbs.

Sample Input 1

2 2
2 1 2
1 2
0 1

Sample Output 1

1
  • Bulb $1$ is lighted when there is an even number of switches that are "on" among the following: Switch $1$ and $2$.
  • Bulb $2$ is lighted when there is an odd number of switches that are "on" among the following: Switch $2$.

There are four possible combinations of states of (Switch $1$, Switch $2$): (on, on), (on, off), (off, on) and (off, off). Among them, only (on, on) lights all the bulbs, so we should print $1$.

Sample Input 2

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

Sample Output 2

0
  • Bulb $1$ is lighted when there is an even number of switches that are "on" among the following: Switch $1$ and $2$.
  • Bulb $2$ is lighted when there is an even number of switches that are "on" among the following: Switch $1$.
  • Bulb $3$ is lighted when there is an odd number of switches that are "on" among the following: Switch $2$.

Switch $1$ has to be "off" to light Bulb $2$ and Switch $2$ has to be "on" to light Bulb $3$, but then Bulb $1$ will not be lighted. Thus, there are no combinations of states of the switches that light all the bulbs, so we should print $0$.

Sample Input 3

5 2
3 1 2 5
2 2 3
1 0

Sample Output 3

8

Input

题意翻译

### 题目描述 有 $n$ 个开关和 $m$ 个灯泡，每个开关都处于“开”和“关”状态中的一种。开关从 $1$ 到 $n$ 编号，灯泡从 $1$ 到 $m$ 编号。 $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 $ --- ### 输出格式 输出一个数，表示有多少总组合方案可以点亮所有灯泡。 ### 说明/提示 #### 数据范围 * $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$。

Source/Category

加入题单

算法标签：