CF2165B Marble Council

给定一个多重集合 $a$，包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。你希望通过以下过程生成一个新的多重集合 $s$： - 将 $a$ 拆分为任意数量的非空多重集合 $x_1,x_2,\ldots,x_k$，使得 $a$ 中的每个元素恰好属于其中的一个多重集合。 - 初始时 $s$ 为空。对于每个 $x_i$，选择一个它的众数 $^*$ 并将其插入 $s$ 中。 请你计算可以通过上述过程生成的不同的多重集合 $s$ 的数量，结果对 $998\,244\,353$ 取模。 请注意，计算多重集合的不同数量时，只考虑集合的内容，不考虑顺序，但是每个元素的出现次数是重要的，即 $\{1,1,2\}$、$\{1,2\}$、$\{1,1,2,2\}$ 都视作不同的多重集合。 $^*$ 多重集合的众数定义为出现次数最多的元素；如果有多个元素出现次数相同且为最大，则这些元素都视为众数。

每个测试点包含多组数据。第一行包含一个整数 $t$（$1 \le t \le 5000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5000$），表示多重集合 $a$ 的大小。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le n$）。 保证所有测试用例的 $n$ 之和不超过 $5000$。

对于每个测试用例，输出一行一个整数，表示可以得到的不同多重集合的数量，对 $998\,244\,353$ 取模。

在第一个测试用例中，$ \{1,2,3\} $ 的任意非空子集都可以被得到，共有 $7$ 个多重集合。 在第三个测试用例中，可以得到 $4$ 个不同的多重集合： - 把所有元素分在 $\{1,2,2\}$，得到 $\{2\}$。 - 把元素分为 $\{1,2\},\{2\}$，得到 $\{2,2\}$。 - 把元素分为 $\{1\},\{2,2\}$，得到 $\{1,2\}$。 - 把元素分为 $\{1\},\{2\},\{2\}$，得到 $\{1,2,2\}$。 可以证明没有其它的多重集合能被得到。 由 ChatGPT 5 翻译