A6466. 集合覆盖
编程题
普及-
知识点
题目描述
有 $M$ 个集合 $S_1,S_2,\dots,S_M$，每个集合中的元素都是 $1$ 到 $N$ 之间的整数。
其中第 $i$ 个集合 $S_i$ 一共有 $C_i$ 个元素，分别为 $a_{i,1},a_{i,2},\dots,a_{i,C_i}$。
现在从这 $M$ 个集合中**任选至少一个**集合进行选择，一共有 $(2^M-1)$ 种选法。
请你统计：有多少种选法能满足下面的要求？
* 对任意整数 $x$（$1\le x\le N$），至少存在一个被选中的集合包含 $x$。换句话说，被选集合的并集需要覆盖 ${1,2,\dots,N}$。
#### 限制因素
- $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$
- 输入值均为整数。
其中第 $i$ 个集合 $S_i$ 一共有 $C_i$ 个元素，分别为 $a_{i,1},a_{i,2},\dots,a_{i,C_i}$。
现在从这 $M$ 个集合中**任选至少一个**集合进行选择，一共有 $(2^M-1)$ 种选法。
请你统计：有多少种选法能满足下面的要求？
* 对任意整数 $x$（$1\le x\le N$），至少存在一个被选中的集合包含 $x$。换句话说，被选集合的并集需要覆盖 ${1,2,\dots,N}$。
#### 限制因素
- $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$
- 输入值均为整数。
输入格式
#### 输入
输入内容由标准输入法提供，格式如下
$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}$
输入内容由标准输入法提供，格式如下
$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}$
输出格式
#### 输出
打印满足问题陈述中条件的集合的选择方式数。
打印满足问题陈述中条件的集合的选择方式数。
输入输出样例
输入 #1
3 3 2 1 2 2 1 3 1 2
输出 #1
3
输入 #2
4 2 2 1 2 2 1 3
输出 #2
0
输入 #3
6 6 3 2 3 6 3 2 4 6 2 3 6 3 1 5 6 3 1 3 6 2 1 4
输出 #3
18
说明/提示
### 样例一解释
输入中给出的集合为 $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$ 。
输入中给出的集合为 $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$ 。