CF2255F Who Will Witness the End?

在她最后的出击前，Chtholly 问了 Willem 三个问题。 第三个问题是：当终结终于来临时，谁会见证这一切？ Willem 无法直接回答她。于是他在黑板上画了一个圆圈，称之为万物之环，并写下了 $n$ 个有标记的整数 $a_1,a_2,\ldots,a_n$。环上的每一种可能的排列都描述了世界可能终结的不同方式。 考虑 $1$ 到 $n$ 的一个排列 $p_1,p_2,\ldots,p_n$。按此顺序将对应的数字依次放到圆圈上。这个环状排列的权值定义为： $$ \prod_{i=1}^n (a_{p_i} + a_{p_{i+1}}) $$ 其中 $p_{n+1}=p_1$。 如果两个排列可以通过循环移位得到彼此，则它们描述的是同一种环状排列。反向排列（即镜像排列）不认为是相同的；也就是说，只有在循环移位后也正好重合的情况才被视为相同。 请你计算所有不同环状排列的权值之和。由于答案可能很大，输出结果需对 $998\,244\,353$ 取模。

每组测试包含若干个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。接下来是各个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 2\cdot 10^5$），表示有标记的整数的个数。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i < 998\,244\,353$）。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每个测试用例，输出一个整数，表示所有不同环状排列的权值之和，结果对 $998\,244\,353$ 取模。

在第一个测试用例中，有两种不同的环状排列。它们可以被表示为排列 $[1,2,3]$ 和 $[1,3,2]$。它们的权值都是 $$ (1+2)(2+3)(3+1)=60 $$ 因此答案是 $120$。 在第二个测试用例中，只有当 $0$ 和 $1$ 在环上交替排列时排列的权值才非零。这样的环状排列有 $$ \frac{2\cdot 3! \cdot 3!}{6} = 12 $$ 种：其中 $2$ 代表线性表示从 $0$ 或 $1$ 开始，$3!$ 是各自的位置全排列，$6$ 是循环移位同构类的数量。每个排列的权值为 $1$。其他排列的权值均为 $0$，因此答案为 $12$。 由 ChatGPT 5 翻译