← 返回题目列表

Codeforces · 2165/B

B. 大理石委员会

中文机器翻译题面 查看原题

给你一个多重集 $$$a$$$,它由 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ 组成。您想通过以下过程生成新的多重集 $$$s$$$:

  • 将 $$$a$$$ 划分为任意数量的非空多重集 $$$x_1,x_2,\ldots,x_k$$$,使得 $$$a$$$ 的每个元素恰好属于这些多重集之一。
  • 最初,$$$s$$$ 是空的。从每个 $$$x_i$$$ 中选择 一 其 模式$$$^{\text{*}}$$$ 并将其插入到 $$$s$$$ 中。

请计算通过该过程可以生成的不同多重集 $$$s$$$ 的数量,以 $$$998\,244\,353$$$ 为模。

请注意数量不同 多套 被计数,这意味着元素的顺序并不重要。然而,每个元素的计数确实很重要,即 $$$\{1,1,2\},\{1,2\},\{1,1,2,2\}$$$ 都被认为是不同的。

$$$^{\text{*}}$$$多重集的众数定义为出现次数最多的元素;如果多个元素都被视为最大值,则所有这些元素都被视为众数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le5000$$$) — 多重集 $$$a$$$ 的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le n$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。

输出

对于每个测试用例,打印一行包含一个整数 - 您可以获得的不同多重集的数量,以 $$$998\,244\,353$$$ 为模。

示例

输入
复制

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

输出
复制

7
3
4
111
126

注意

在第一个测试用例中,可以实现 $$$\{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\}$$$。

可以证明没有其他多重集是可能的。