P1459 - 覆盖范围

内存限制：128 MB 时间限制：1.000 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：54 通过：30

有M组S₁,S₂,…,S_M的集合，由介于1和N之间的整数组成。
S_i由C_i个整数组成a_i1,a_i2,a_i3……a_ici
从M组中选择一个或多个集合有(2^M−1)种方式。

有多少种方式满足以下条件？对于所有整数x使得1≤x≤N，至少有一个被选择的集合包含x。

N M

C1

a₁₁ a₁₂……a_1C1

C2

a₂₁ a₂₂……a_2C2

CM

a_M1 a_M2……a_MCm

打印满足题目描述条件的选择集合的数量。
输入中给定的集合为S1={1,2},S2={1,3},S3={2}。
以下三种方式满足题目描述条件：
选择S1,S2；
选择S1,S2,S3；
选择S2,S3。

搜索

1459: 覆盖范围