#1595. 集合划分计数

    ID: 1595 传统题 7000ms 514MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>模板数学容斥原理组合计数生成函数 / 母函数集合幂级数

集合划分计数

题目描述

这是一道(集合幂级数问题转化为形式幂级数问题,利用求导 O(n2)O(n^2) 完成形式幂级数操作的)模板题。

给定一个集合 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}}\}

一个划分 P\mathcal PF\mathcal F 的一个子族,满足 P\mathcal P 中所有集合的并为 SS ,任意两个集合不相交。

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

两个划分 P1,P2{\mathcal P_1}, {\mathcal P_2} 不同,当且仅当存在 ii 使 $S_i \in {\mathcal P_1} \land S_i \notin {\mathcal P_2}$ 或 $S_i \notin {\mathcal P_1} \land S_i \in {\mathcal P_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
5

数据范围与提示

  • 1kn211 \leq k \leq n \leq 21
  • 1m2621441 \leq m \leq 262144
  • 1si2n11 \leq s_i \leq 2^n-1 %% 想了想果然还是别非负整数了吧……

子任务

  1. (16 分)n7n \leq 7m16m \leq 16
  2. (20 分)n11n \leq 11m256m \leq 256
  3. (14 分)n14n \leq 14m2048m \leq 2048
  4. (25 分)n18n \leq 18m32768m \leq 32768
  5. (25 分)没有附加限制