← 返回题目列表

Codeforces · 1630/E

E. 预期组件

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

给定一个大小为 $$$n$$$ 的循环数组 $$$a$$$,其中 $$$a_i$$$ 是 $$$a$$$ 在第 $$$i$$$ 位置的值,可能存在重复值。让我们定义 $$$a$$$ 的排列等于 $$$a$$$ 的另一个排列,当且仅当它们的值对于每个位置 $$$i$$$ 相同,或者我们可以通过执行一些循环旋转将它们相互转换。让我们将循环数组 $$$b$$$ 的分量数量定义为图中连通分量的数量,其中顶点是 $$$b$$$ 的位置,并且我们在 $$$b$$$ 的每对相邻位置之间添加一条具有相等值的边(请注意,在循环数组中,第一个位置和最后一个位置也是相邻的)。

如果我们在 $$$a$$$ 的所有不同排列的集合上等概率地选择它,则求 $$$a$$$ 排列的分量的期望值。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 循环数组 $$$a$$$ 的大小。

每个测试用例的第二行包含 $$$n$$$ 个整数,其中第 $$$i$$$ 是值 $$$a_i$$$ ($$$1 \le a_i \le n$$$)。

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

保证$$$a$$$的不同排列总数不能被$$$M$$$整除

输出

对于每个测试用例,打印一个整数 - 如果我们在 $$$a$$$ 的所有不同排列的集合上以 $$$a$$$ 模 $$$998\,244\,353$$$ 为模,则 $$$a$$$ 排列的分量的期望值。

正式地,让 $$$M = 998\,244\,353$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。

示例

输入 #1

5
4
1 1 1 1
4
1 1 2 1
4
1 2 1 2
5
4 3 2 5 1
12
1 3 2 3 2 1 3 3 1 3 3 2

输出 #1

1
2
3
5
358642921

注意

在第一个测试用例中,$$$a$$$ 只有 $$$1$$$ 不同的排列:

- $$$[1, 1, 1, 1]$$$ 具有 $$$1$$$ 组件。
- 因此组件的预期值为 $$$\frac{1}{1} = 1$$$

在第二个测试用例中,有 $$$4$$$ 方法来排列循环数组 $$$a$$$,但只有 $$$1$$$ 不同的 $$$a$$$ 排列:

- $$$[1, 1, 1, 2]$$$、$$$[1, 1, 2, 1]$$$、$$$[1, 2, 1, 1]$$$ 和 $$$[2, 1, 1, 1]$$$ 是相同的排列,并具有 $$$2$$$ 组件。
- 因此组件的预期值为 $$$\frac{2}{1} = 2$$$

在第三个测试用例中,有 $$$6$$$ 种方法来排列循环数组 $$$a$$$,但 $$$a$$$ 只有 $$$2$$$ 不同的排列:

- $$$[1, 1, 2, 2]$$$、$$$[2, 1, 1, 2]$$$、$$$[2, 2, 1, 1]$$$ 和 $$$[1, 2, 2, 1]$$$ 是相同的排列,并具有 $$$2$$$ 组件。
- $$$[1, 2, 1, 2]$$$ 和 $$$[2, 1, 2, 1]$$$ 是相同的排列,并具有 $$$4$$$ 组件。
- 因此组件的预期值为 $$$\frac{2+4}{2} = \frac{6}{2} = 3$$$

在第四个测试用例中,有 $$$120$$$ 方法来排列循环数组 $$$a$$$,但 $$$a$$$ 的不同排列只有 $$$24$$$:

- $$$a$$$ 的任何排列都有 $$$5$$$ 组件。
- 因此组件的预期值为 $$$\frac{24\cdot 5}{24} = \frac{120}{24} = 5$$$