分数: 300 点
问题陈述
有 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}.
有 (2^M-1) 从以下选项中选择一组或多组的方法 M 设置。
有多少人满足以下条件?
- 对于所有整数 x 这样 1 \leq x \leq N,至少有一组包含 x.
约束
- 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
输入中给出的集合是 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.
示例输入 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