Pro.ID1638 Title集合覆盖计数 Title链接http://10.20.2.8/oj/exercise/problem?problem_id=1638 AC0 Submit0 Ratio- 时间&空间限制描述这是一道模板题。 给定一个集合 S = { x1, x2, …, xn } 和一个 S 上的集合族 F = { S0, S1, …, Sm-1 }。 一个覆盖 C 是 F 的一个子族,满足 C 中所有集合的并为 S。 问大小不大于 k 的覆盖的数量 mod 998244353。 两个覆盖 C1, C2 不同,当且仅当存在 i 使 Si ∈ C1 ∧ Si ∉ C2 或 Si ∉ C1 ∧ Si ∈ C2 。 输入第 1 行 3 个正整数 n, m, k。 第 2+i 行( 0 ≤ i ≤ m-1 )是一个正整数 si ,si 二进制第 j 位为 0 表示 xj ∉ Si ,为 1 表示 xj ∈ Si 。 1 ≤ k ≤ n ≤ 22 1 ≤ m ≤ 131072 1 ≤ si ≤ 2n−1 子任务 (16 分)n ≤ 9 ,m ≤ 16 (20 分)n ≤ 13 ,m ≤ 256 (14 分)n ≤ 16 ,m ≤ 2048 (25 分)n ≤ 18 ,m ≤ 8192 (25 分)没有附加限制 输出Description 这是一道模板题。 给定一个集合 S = { x1, x2, …, xn } 和一个 S 上的集合族 F = { S0, S1, …, Sm-1 }。 一个覆盖 C 是 F 的一个子族,满足 C 中所有集合的并为 S。 问大小不大于 k 的覆盖的数量 mod 998244353。 两个覆盖 C1, C2 不同,当且仅当存在 i 使 Si ∈ C1 ∧ Si ∉ C2 或 Si ∉ C1 ∧ Si ∈ C2 。 Input 第 1 行 3 个正整数 n, m, k。 第 2+i 行( 0 ≤ i ≤ m-1 )是一个正整数 si ,si 二进制第 j 位为 0 表示 xj ∉ Si ,为 1 表示 xj ∈ Si 。 1 ≤ k ≤ n ≤ 22 1 ≤ m ≤ 131072 1 ≤ si ≤ 2n−1 子任务 (16 分)n ≤ 9 ,m ≤ 16 (20 分)n ≤ 13 ,m ≤ 256 (14 分)n ≤ 16 ,m ≤ 2048 (25 分)n ≤ 18 ,m ≤ 8192 (25 分)没有附加限制 Output 1 个非负整数,表示大小不大于 k 的覆盖的数量 mod 998244353 。 Sample Input 4 8 2 Sample Output 16 样例输入4 8 2 样例输出16 提示作者 |