AT_abc289_c [ABC289C] Coverage

题目描述

有 $M$ 个集合，每个集合由 $1$ 到 $N$ 之间的若干整数构成，依次记为 $S_1, S_2, \dots, S_M$。
集合 $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}$

输出格式

输出满足题目条件的集合选择方法的数量。

输入输出样例 #1

输入 #1

3 3
2
1 2
2
1 3
1
2

输出 #1

3

输入输出样例 #2

输入 #2

4 2
2
1 2
2
1 3

输出 #2

0

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $1 \leq N \leq 10$
• $1 \leq M \leq 10$
• $1 \leq C_i \leq N$
• $1 \leq a_{i,1} < a_{i,2} < \dots < a_{i,C_i} \leq N$
• 所有输入的值均为整数

样例解释 1

输入给出的集合分别为 $S_1 = \{1, 2\}$，$S_2 = \{1, 3\}$，$S_3 = \{2\}$。满足题目条件的集合选择方法有以下 $3$ 种：

• 选择 $S_1, S_2$。
• 选择 $S_1, S_2, S_3$。
• 选择 $S_2, S_3$。

样例解释 2

也有可能不存在满足题目条件的选择方法。

由 ChatGPT 4.1 翻译