← 返回题目
题库练习 集合覆盖
← 上一题 下一题 →

A6466 | 集合覆盖

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

有 $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$
- 输入值均为整数。

输入格式

#### 输入

输入内容由标准输入法提供，格式如下

$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
C++ 编辑器
输入
输出