CF1630E Expected Components

给定一个大小为 $n$ 的循环数组 $a$，其中 $a_i$ 表示第 $i$ 个位置上的值，数组中可能有重复的值。我们定义，如果两个 $a$ 的排列在每个位置 $i$ 的值都相同，或者可以通过若干次循环移位互相变换，则认为这两个排列是相同的。对于一个循环数组 $b$，定义其“连通块数”为如下图中连通块的数量：图的顶点为 $b$ 的各个位置，如果 $b$ 的相邻两个位置上的值相等，则在这两个位置之间连一条边（注意循环数组中第一个和最后一个位置也视为相邻）。 如果我们等概率地从所有不同的 $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$ 的不同排列后，其连通块数的期望值对 $998\,244\,353$ 取模的结果。 形式化地，设 $M = 998\,244\,353$。可以证明答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod{M}$。输出一个整数 $x$，满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$。

在第一个测试样例中，$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$。 由 ChatGPT 4.1 翻译