Coverage

题目描述

有 $M$ 个集合，记为 $S_1, S_2, \dots, S_M$，它们由介于 $1$ 与 $N$ 之间的整数组成。
$S_i$ 由 $C_i$ 个整数 $a_{i, 1}, a_{i, 2}, \dots, a_{i, C_i}$ 组成。 从这 $M$ 个集合中选择一个或多个集合共有 $(2^M-1)$ 种方式。
其中有多少种方式满足下列条件？

对于所有满足 $1 \leq x \leq N$ 的整数 $x$，至少存在一个被选择的集合包含 $x$。

输入格式

输入格式（从标准输入）如下： $N$ $M$ $C_1$ $a_{1,1}$ $a_{1,2}$ $\dots$ $a_{1,C_1}$ $C_2$ $a_{2,1}$ $a_{2,2}$ $\dots$ $a_{2,C_2}$ $\vdots$ $C_M$ $a_{M,1}$ $a_{M,2}$ $\dots$ $a_{M,C_M}$

输出格式

输出满足题目陈述中条件的集合选择方式的数目。

3 3
2
1 2
2
1 3
1
2

3

4 2
2
1 2
2
1 3

0

6 6
3
2 3 6
3
2 4 6
2
3 6
3
1 5 6
3
1 3 6
2
1 4

18

提示

$1 \leq N \leq 10$ $1 \leq M \leq 10$ $1 \leq C_i \leq N$ $1 \leq a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,C_i} \leq N$ 输入中的所有数值均为整数。输入中给出的集合为 $S_1 = \lbrace 1, 2 \rbrace, S_2 = \lbrace 1, 3 \rbrace, S_3 = \lbrace 2 \rbrace。$
满足题目陈述中条件的三种方式如下：

选择 $S_1, S_2$； 选择 $S_1, S_2, S_3$； 选择 $S_2, S_3$。
也可能不存在任何满足题目陈述中条件的集合选择方式。

标签: AtCoder|abc289C

来源

AtCoder|abc289C