同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1639_集合划分计数

2022-5-16 18:17| 发布者: Hocassian| 查看: 59| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-8950467419100-Problem List-采集的数据-后羿采集器.html

Pro.ID

1639

Title

集合划分计数

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1639

AC

Submit

Ratio

时间&空间限制

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 512000/512000 K (Java/Others)

描述

这是一道模板题。给定一个集合 S={x1,x2,…,xn} 和一个 S 上的集合族 F={S0,S1,…,Sm−1}。

一个划分 P 是 F 的一个子族，满足 P 中所有集合的并为 S ，任意两个集合的交为空。

问大小不大于 k 的划分的数量 mod 998244353。

两个划分 P1, P2 不同，当且仅当存在 i 使 Si∈P1∧Si∉P2 或 Si∉P1∧Si∈P2 。

输入

第 1 行 3 个正整数 n,m,k 。

第 2+i 行（ 0 ≤ i ≤ m−1 ） 1 个正整数 si ， si 二进制第 j 位为 0 表示 xj∉Si ，为 1 表示 xj∈Si 。

1 ≤ k ≤ n ≤ 21

1 ≤ m ≤ 262144

1 ≤ si ≤ 2ⁿ−1

子任务

（16 分）n≤7 ，m≤16

（20 分）n≤11 ，m≤256

（14 分）n≤14 ，m≤2048

（25 分）n≤18 ，m≤32768

（25 分）没有附加限制

输出

Description

这是一道模板题。给定一个集合 S={x1,x2,…,xn} 和一个 S 上的集合族 F={S0,S1,…,Sm−1}。

一个划分 P 是 F 的一个子族，满足 P 中所有集合的并为 S ，任意两个集合的交为空。

问大小不大于 k 的划分的数量 mod 998244353。

两个划分 P1, P2 不同，当且仅当存在 i 使 Si∈P1∧Si∉P2 或 Si∉P1∧Si∈P2 。

Input

第 1 行 3 个正整数 n,m,k 。

第 2+i 行（ 0 ≤ i ≤ m−1 ） 1 个正整数 si ， si 二进制第 j 位为 0 表示 xj∉Si ，为 1 表示 xj∈Si 。

1 ≤ k ≤ n ≤ 21

1 ≤ m ≤ 262144

1 ≤ si ≤ 2ⁿ−1

子任务

（16 分）n≤7 ，m≤16

（20 分）n≤11 ，m≤256

（14 分）n≤14 ，m≤2048

（25 分）n≤18 ，m≤32768

（25 分）没有附加限制

Output

1 个非负整数，表示大小不大于 k 的划分的数量 mod 998244353。

Sample Input

4 8 2
7 10 8 11 5 15 4 5

Sample Output

样例输入