CF1740F Conditional Mix

Pak Chanek 得到一个包含 $n$ 个整数的数组 $a$。对于每个 $i$（$1 \leq i \leq n$），Pak Chanek 会在白板上写下单元素集合 $\{a_i\}$。 之后，每次操作，Pak Chanek 可以进行如下操作： 1. 选择白板上两个不同的集合 $S$ 和 $T$，要求 $S \cap T = \varnothing$（即 $S$ 和 $T$ 没有公共元素）。 2. 擦除 $S$ 和 $T$，并在白板上写下 $S \cup T$（即 $S$ 和 $T$ 的并集）。 经过若干次（可以为零次）操作后，Pak Chanek 会构造一个多重集 $M$，其中包含白板上所有集合的大小。换句话说，$M$ 中的每个元素对应操作后白板上某个集合的大小。 通过上述过程，最多可以构造出多少种不同的多重集 $M$？由于答案可能很大，请输出答案对 $998\,244\,353$ 取模后的结果。 注：若存在某个值 $k$，使得多重集 $B$ 和 $C$ 中值为 $k$ 的元素个数不同，则 $B$ 和 $C$ 被认为是不同的多重集。

第一行包含一个整数 $n$（$1 \le n \le 2000$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）。

输出不同多重集 $M$ 的个数，对 $998\,244\,353$ 取模。

在第一个样例中，可能的多重集 $M$ 有 $\{1,1,1,1,1,1\}$、$\{1,1,1,1,2\}$、$\{1,1,1,3\}$、$\{1,1,2,2\}$、$\{1,1,4\}$、$\{1,2,3\}$ 和 $\{2,2,2\}$。 举例说明一种可能的操作序列： 1. 初始时，集合为 $\{1\}$、$\{1\}$、$\{2\}$、$\{1\}$、$\{4\}$ 和 $\{3\}$。 2. 对集合 $\{1\}$ 和 $\{3\}$ 进行操作。此时集合为 $\{1\}$、$\{1\}$、$\{2\}$、$\{4\}$、$\{1,3\}$。 3. 对集合 $\{2\}$ 和 $\{4\}$ 进行操作。此时集合为 $\{1\}$、$\{1\}$、$\{1,3\}$、$\{2,4\}$。 4. 对集合 $\{1,3\}$ 和 $\{2,4\}$ 进行操作。此时集合为 $\{1\}$、$\{1\}$、$\{1,2,3,4\}$。 5. 构造出的多重集 $M$ 为 $\{1,1,4\}$。 由 ChatGPT 4.1 翻译