[AHOI2022] 排列
题目描述
对于一个长度为 $n$ 的排列 $P = (p_1, p_2, \ldots, p_n)$ 和整数 $k \ge 0$,定义 $P$ 的 $k$ 次幂
$$P^{(k)} = \left( p^{(k)}_1, p^{(k)}_2, \ldots, p^{(k)}_n \right),$$
该排列的第 $i$ 项为
$$p^{(k)}_i = \begin{cases} i, & k = 0, \\ p^{(k - 1)}_{p_i}, & k > 0. \end{cases}$$
容易证明任意排列的任意次幂都是一个排列。
定义排列 $P$ 的**循环值** $v(P)$ 为最小的**正整数** $k$ 使得 $P^{(k + 1)} = P$。
给出一个长度为 $n$ 的排列 $A = (a_1, a_2, \ldots, a_n)$,对于整数 $1 \le i, j \le n$,定义 $f(i, j)$:若存在 $k \ge 0$ 使得 $a^{(k)}_i = j$,则 $f(i, j) = 0$,否则设排列 $A_{i j}$ 为将排列 $A$ 的第 $i$ 项 $a_i$ 和第 $j$ 项 $a_j$ 交换后得到的排列,则 $f(i, j) = v(A_{i j})$。
求 $\sum_{i = 1}^{n} \sum_{j = 1}^{n} f(i, j)$ 的值。答案可能很大,你只需要输出其对 $({10}^9 + 7)$ 取模的结果。
输入输出格式
输入格式
**本题有多组测试数据**。输入数据的第一行为一个整数 $T$,表示测试数据组数。
对于每组测试数据,第一行一个正整数 $n$ 表示排列的长度,接下来一行 $n$ 个整数 $a_1, a_2, \ldots, a_n$,描述输入的排列。
输出格式
对于每组数据输出一行一个整数,表示题目所求的答案对 $({10}^9 + 7)$ 取模的结果。
输入输出样例
输入样例 #1
2
3
1 2 3
3
2 3 1
输出样例 #1
12
0
说明
**【样例解释 #1】**
对于第一组测试数据,$f(1, 2) = f(2, 1) = f(2, 3) = f(3, 2) = f(1, 3) = f(3, 1) = 2$,其余的 $f(i, j)$ 均为 $0$。
对于第二组测试数据,所有的 $f(i, j)$ 均为 $0$。
**【样例 #2】**
见附件中的 `perm/perm2.in` 与 `perm/perm2.ans`。
该组样例中,第一个测试数据满足 $n \le 35$,前四个测试数据满足 $n \le 200$,所有测试数据满足 $n \le 2500$。
**【样例 #3】**
见附件中的 `perm/perm3.in` 与 `perm/perm3.ans`。
该组样例中,第一个测试数据满足特殊性质 A,第二个测试数据满足特殊性质 B,第三个测试数据满足特殊性质 C,前四个测试数据满足 $n \le {10}^5$,第五个测试数据满足 $n \le 5 \times {10}^5$。
特殊性质的具体内容参见数据范围部分。
**【数据范围】**
对于 $100 \%$ 的测试数据,$1 \le T \le 5$,$1 \le n \le 5 \times {10}^5$,$1 \le a_i \le n$。
| 测试点编号 | $n \le$ | 特殊性质 |
|:-:|:-:|:-:|
| $1 \sim 2$ | ${10}^5$ | A |
| $3$ | $35$ | 无 |
| $4$ | $200$ | 无 |
| $5$ | $2500$ | 无 |
| $6$ | ${10}^5$ | B |
| $7$ | ${10}^5$ | C |
| $8$ | ${10}^5$ | 无 |
| $9 \sim 10$ | $5 \times {10}^5$ | 无 |
特殊性质 A:$a_i = (i \bmod n) + 1$。
特殊性质 B:对于任意 $1 \le i \le n$,存在 $1 \le k \le 20$,$a^{(k)}_i = i$。
特殊性质 C:存在大小不超过 $10$ 的集合 $S$,使得对于任意 $1 \le i \le n$,存在 $x \in S, k \ge 0$,$a^{(k)}_x = i$。
**【提示】**
输入数据规模较大,请使用较为快速的输入方式。