P16400 [ECUSTPC 2026 Spring] 朝复夕

:::epigraph 朝复夕，朝夕复。 :::

**本题和试题 G 朝复习没有关系。** 小 T 准备出一些经典的问题…… 对于给定一个长度为 $n$ 的排列 $p = \{p_1, p_2, \dots, p_n\}$，小 T 将进行一次操作 $(i, j)$： - 取一对下标 $1 \le i < j \le n$，交换 $p$ 中的 $p_i$ 和 $p_j$。 对于所有不同的合法操作 $(i, j)$，小 T 需要计算交换之后的排列所表示的置换的阶数之和。 由于答案可能很大，小 T 需要计算答案对 $998\,244\,353$ 取模的值。 请帮助小 T 计算这个问题。 试题的提示中附带有有关于置换和排列的相关信息。

第一行输入一个整数 $T \ (1 \le T \le 10^5)$，表示测试数据的数量。 每组测试数据第一行输入一个整数 $n \ (2 \le n \le 10^5)$，表示排列的长度。 随后一行输入 $n$ 个整数 $p_1, p_2, \dots, p_n \ (1 \le p_i \le n)$，表示所给定的排列。 保证所有测试数据输入中的 $\sum n \le 3 \times 10^5$，且每组测试数据给定序列一定是一个合法的排列。

对于每组测试数据输出一行一个整数，表示对于所有不同的合法操作 $(i, j)$，交换之后的排列所表示的置换的阶数之和对 $998\,244\,353$ 取模的值。

### 样例 1 解释 对于第 $1$ 组测试数据，共有 $3$ 种不同的交换方式： - 交换 $p_1$ 和 $p_2$，排列变为 $p = \{3, 2, 1\}$，可以注意到 $p^2 = \mathrm{id}_3$，因为 $p(p(1)) = p(3) = 1$，$p(p(2)) = p(2) = 2$，$p(p(3)) = p(1) = 3$，因此阶数为 $2$。 - 交换 $p_1$ 和 $p_3$，排列变为 $p = \{1, 3, 2\}$，可以注意到 $p^2 = \mathrm{id}_3$，阶数为 $2$。 - 交换 $p_2$ 和 $p_3$，排列变为 $p = \{2, 1, 3\}$，可以注意到 $p^2 = \mathrm{id}_3$，阶数为 $2$。 因此答案为 $6$。 ### 提示 一个 $1$ 到 $n$ 的排列是一个长度为 $n$ 且其中每个 $1$ 到 $n$ 的整数都出现且仅出现一次的序列，这个排列的长度也为 $n$. 令 $S = \{1, 2, \dots, n\}$，一个 $1$ 到 $n$ 的置换是指从 $S$ 到 $S$ 的一个双射。 一个长度为 $n$ 的排列 $p = \{p_1, p_2, \dots, p_n\}$ 可以表示一个置换 $p$，也即 $p(i) = p_i$. 例如第 $1$ 组样例的 $p = \{2, 3, 1\}$ 表示的置换是 $p(n): \{1, 2, 3\} \to \{1, 2, 3\}$，其中 $$ p(1) = 2,\ p(2) = 3,\ p(3) = 1. $$ 长度为 $n$ 恒等置换 $\mathrm{id}_n: \{1, 2, \dots, n\} \to \{1, 2, \dots, n\}$ 定义为 $\mathrm{id}_n(i) = i$，例如一个长度为 $4$ 的恒等置换 $\mathrm{id}_4$ 有： $$ \mathrm{id}_4(1) = 1,\ \mathrm{id}_4(2) = 2,\ \mathrm{id}_4(3) = 3,\ \mathrm{id}_4(4) = 4. $$ 两个置换 $p$ 和 $q$ 的复合 $p \circ q$ 表示的是 $p \circ q(i) = p(q(i))$ 这个置换。 长度为 $n$ 的置换的幂次 $p^m$（其中 $m$ 是非负整数）定义为 $$ p^m = \begin{cases} p \circ p^{m-1}, & m \ge 1; \\ \mathrm{id}_n, & m = 0. \end{cases} $$ 长度为 $n$ 的置换的阶数 $\mathrm{ord}(p)$ 定义为最小的正整数 $k$，满足 $p^k = \mathrm{id}_n$.