CF1630E.Expected Components

Given a cyclic array $a$ of size $n$, where $a_i$ is the value of $a$ in the $i$-th position, there may be repeated values. Let us define that a permutation of $a$ is equal to another permutation of $a$ if and only if their values are the same for each position $i$ or we can transform them to each other by performing some cyclic rotation. Let us define for a cyclic array $b$ its number of components as the number of connected components in a graph, where the vertices are the positions of $b$ and we add an edge between each pair of adjacent positions of $b$ with equal values (note that in a cyclic array the first and last position are also adjacents).

Find the expected value of components of a permutation of $a$ if we select it equiprobably over the set of all the different permutations of $a$.

给定一个长度为 $n$ 的循环数组 $a$，其中 $a_i$ 表示数组 $a$ 在第 $i$ 个位置上的值，数组中可能存在重复元素。我们定义：当且仅当两个 $a$ 的排列在每个位置 $i$ 上的值均相同，或可通过若干次循环移位相互转换时，这两个排列被视为相等。
对任意循环数组 $b$，我们定义其**连通分量数（number of components）**为如下图的连通块数量：该图的顶点为 $b$ 的所有位置；若 $b$ 中两个相邻位置上的值相等，则在对应顶点间连一条边（注意：在循环数组中，首尾位置也被视为相邻）。

现从 $a$ 的所有互不相同的排列中等概率随机选取一个排列，求该排列作为循环数组时其连通分量数的期望值。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^6$) — the size of the cyclic array $a$.

The second line of each test case contains $n$ integers, the $i$-th of them is the value $a_i$ ($1 \le a_i \le n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

It is guaranteed that the total number of different permutations of $a$ is not divisible by $M$

输入包含多个测试用例。第一行包含一个整数 $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$ 整除。

For each test case print a single integer — the expected value of components of a permutation of $a$ if we select it equiprobably over the set of all the different permutations of $a$ modulo $998\,244\,353$.

Formally, let $M = 998\,244\,353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

对每个测试用例，输出一个整数——在所有 $a$ 的不同排列构成的集合上等概率随机选取一个排列时，该排列的连通块数量的期望值，结果对 $998\,244\,353$ 取模。

形式化地，令 $M = 998\,244\,353$。可以证明答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，请输出满足 $0 \le x \lt M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

In the first test case there is only $1$ different permutation of $a$:

• $[1, 1, 1, 1]$ has $1$ component.
• Therefore the expected value of components is $\frac{1}{1} = 1$

In the second test case there are $4$ ways to permute the cyclic array $a$, but there is only $1$ different permutation of $a$:

• $[1, 1, 1, 2]$, $[1, 1, 2, 1]$, $[1, 2, 1, 1]$ and $[2, 1, 1, 1]$ are the same permutation and have $2$ components.
• Therefore the expected value of components is $\frac{2}{1} = 2$

In the third test case there are $6$ ways to permute the cyclic array $a$, but there are only $2$ different permutations of $a$:

• $[1, 1, 2, 2]$, $[2, 1, 1, 2]$, $[2, 2, 1, 1]$ and $[1, 2, 2, 1]$ are the same permutation and have $2$ components.
• $[1, 2, 1, 2]$ and $[2, 1, 2, 1]$ are the same permutation and have $4$ components.
• Therefore the expected value of components is $\frac{2+4}{2} = \frac{6}{2} = 3$

In the fourth test case there are $120$ ways to permute the cyclic array $a$, but there are only $24$ different permutations of $a$:

• Any permutation of $a$ has $5$ components.
• Therefore the expected value of components is $\frac{24\cdot 5}{24} = \frac{120}{24} = 5$

在第一个测试用例中，数组 $a$ 只有 $1$ 种不同的排列：

• $[1, 1, 1, 1]$ 有 $1$ 个连通分量。
• 因此连通分量数的期望值为 $\frac{1}{1} = 1$。

在第二个测试用例中，循环数组 $a$ 有 $4$ 种排列方式，但其中只有 $1$ 种不同的排列：

• $[1, 1, 1, 2]$、$[1, 1, 2, 1]$、$[1, 2, 1, 1]$ 和 $[2, 1, 1, 1]$ 是同一种排列，且具有 $2$ 个连通分量。
• 因此连通分量数的期望值为 $\frac{2}{1} = 2$。

在第三个测试用例中，循环数组 $a$ 有 $6$ 种排列方式，但其中只有 $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$。

在第四个测试用例中，循环数组 $a$ 有 $120$ 种排列方式，但其中只有 $24$ 种不同的排列：

• $a$ 的任意一种排列均有 $5$ 个连通分量。
• 因此连通分量数的期望值为 $\frac{24\cdot 5}{24} = \frac{120}{24} = 5$。