#1594. 集合覆盖计数

集合覆盖计数

题目描述

这是一道(集合并卷积的)模板题。

给定一个集合 S={x1,x2,,xn}S = \{{x_1}, {x_2}, \dots, {x_n}\} 和一个 SS 上的集合族 F={S0,S1,,Sm1}\mathcal F = \{{S_0}, {S_1}, \dots, {S_{m-1}}\}

一个覆盖 C\mathcal CF\mathcal F 的一个子族,满足 C\mathcal C 中所有集合的并为 SS

求大小不大于 kk 的覆盖的数量 mod  998244353\text{mod}\;998244353 %% \bmod 会在前面产生一个空白。。

两个覆盖 C1,C2{\mathcal C_1}, {\mathcal C_2} 不同,当且仅当存在 ii 使 $S_i \in {\mathcal C_1} \land S_i \notin {\mathcal C_2}$ 或 $S_i \notin {\mathcal C_1} \land S_i \in {\mathcal C_2}$。SiS_iSjS_j 不同当且仅当 iji \neq j

输入格式

11 行:n m kn\ m\ k

22 行:s0 s1 sm1s_0\ s_1\ \ldots s_{m-1}sis_i 二进制第 jj 位为 00 表示 xjSi{x_j} \notin {S_i} ,为 11 表示 xjSi{x_j} \in {S_i}

输出格式

11 个非负整数,表示大小不大于 kk 的覆盖的数量 mod  998244353\text{mod}\;998244353 %% \bmod 会在前面产生一个空白。。

样例

4 8 2
7 10 8 11 5 15 4 5
16

数据范围与提示

  • 1kn221 \leq k \leq n \leq 22
  • 1m1310721 \leq m \leq 131072
  • 1si2n11 \leq s_i \leq 2^n-1

子任务

  1. (16 分)n9n \leq 9m16m \leq 16
  2. (20 分)n13n \leq 13m256m \leq 256
  3. (14 分)n16n \leq 16m2048m \leq 2048
  4. (25 分)n18n \leq 18m8192m \leq 8192
  5. (25 分)没有附加限制