[AdditionalFile153.zip](file://AdditionalFile153.zip?type=additional_file)

#153. 集合覆盖计数

标签: 传统 | 时间限制: 1000 ms | 内存限制: 114 MiB | 显示标签 通过: 160 | 提交: 278

题目描述

这是一道（集合合并卷积）的模板题。

给定一个集合 $S = \{x_1, x_2, \dots, x_n\}$ 和一个 $S$ 上的集合族 $\mathcal{F} = \{S_0, S_1, \dots, S_{m-1}\}$。

一个覆盖 $C$ 是 $\mathcal{F}$ 的一个子族，满足 $C$ 中所有集合的并为 $S$。

求大小不大于 $k$ 的覆盖的数量 mod 998244353。

两个覆盖 $C_1, C_2$ 不同，当且仅当存在 $i$ 使 $S_i \in C_1 \land S_i \notin C_2$ 或 $S_i \notin C_1 \land S_i \in C_2$。$S_i$ 和 $S_j$ 不同当且仅当 $i \ne j$。

输入格式

第 1 行：$n \ m \ k$

第 2 行：$s_0 \ s_1 \ \dots \ s_{m-1}$，$s_i$ 二进制第 $j$ 位为 0 表示 $x_j \notin S_i$，为 1 表示 $x_j \in S_i$

输出格式

1 个非负整数，表示大小不大于 $k$ 的覆盖的数量 mod 998244353。

样例

输入

4 8 2
7 10 8 11 5 15 4 5

输出

16

数据范围与提示

• $1 \le k \le n \le 22$
• $1 \le m \le 131072$
• $1 \le s_i \le 2^n - 1$

子任务

1. (16 分) $n \le 9, m \le 16$
2. (20 分) $n \le 13, m \le 256$
3. (14 分) $n \le 16, m \le 2048$
4. (25 分) $n \le 18, m \le 8192$
5. (25 分) 没有附加限制