A16668 | $Marble Council$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个多重集合 $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

5
3
1 2 3
3
1 1 1
3
1 2 2
10
1 1 1 1 2 2 2 3 3 4
10
1 1 1 2 2 2 3 3 3 4

输出 #1

C++ 编辑器

输入

输出