{"problem":{"name":"[AHOI2022] 排列","description":{"content":"对于一个长度为 $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","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8338"},"statements":[{"statement_type":"Markdown","content":"对于一个长度为 $n$ 的排列 $P = (p_1, p_2, \\ldots, p_n)$ 和整数 $k \\ge 0$，定义 $P$ 的 $k$ 次幂\n\n$$P^{(k)} = \\left( p^{(k)}_1, p^{(k)}_2, \\ldots, p^{(k)}_n \\right),$$\n\n该排列的第 $i$ 项为\n\n$$p^{(k)}_i = \\begin{cases} i, & k = 0, \\\\ p^{(k - 1)}_{p_i}, & k > 0. \\end{cases}$$\n\n容易证明任意排列的任意次幂都是一个排列。\n\n定义排列 $P$ 的**循环值** $v(P)$ 为最小的**正整数** $k$ 使得 $P^{(k + 1)} = P$。\n\n给出一个长度为 $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})$。\n\n求 $\\sum_{i = 1}^{n} \\sum_{j = 1}^{n} f(i, j)$ 的值。答案可能很大，你只需要输出其对 $({10}^9 + 7)$ 取模的结果。\n\n## Input\n\n**本题有多组测试数据**。输入数据的第一行为一个整数 $T$，表示测试数据组数。\n\n对于每组测试数据，第一行一个正整数 $n$ 表示排列的长度，接下来一行 $n$ 个整数 $a_1, a_2, \\ldots, a_n$，描述输入的排列。\n\n## Output\n\n对于每组数据输出一行一个整数，表示题目所求的答案对 $({10}^9 + 7)$ 取模的结果。\n\n[samples]\n\n## Note\n\n**【样例解释 #1】**\n\n对于第一组测试数据，$f(1, 2) = f(2, 1) = f(2, 3) = f(3, 2) = f(1, 3) = f(3, 1) = 2$，其余的 $f(i, j)$ 均为 $0$。\n\n对于第二组测试数据，所有的 $f(i, j)$ 均为 $0$。\n\n**【样例 #2】**\n\n见附件中的 `perm/perm2.in` 与 `perm/perm2.ans`。\n\n该组样例中，第一个测试数据满足 $n \\le 35$，前四个测试数据满足 $n \\le 200$，所有测试数据满足 $n \\le 2500$。\n\n**【样例 #3】**\n\n见附件中的 `perm/perm3.in` 与 `perm/perm3.ans`。\n\n该组样例中，第一个测试数据满足特殊性质 A，第二个测试数据满足特殊性质 B，第三个测试数据满足特殊性质 C，前四个测试数据满足 $n \\le {10}^5$，第五个测试数据满足 $n \\le 5 \\times {10}^5$。\n\n特殊性质的具体内容参见数据范围部分。\n\n**【数据范围】**\n\n对于 $100 \\%$ 的测试数据，$1 \\le T \\le 5$，$1 \\le n \\le 5 \\times {10}^5$，$1 \\le a_i \\le n$。\n\n| 测试点编号 | $n \\le$ | 特殊性质 |\n|:-:|:-:|:-:|\n| $1 \\sim 2$ | ${10}^5$ | A |\n| $3$ | $35$ | 无 |\n| $4$ | $200$ | 无 |\n| $5$ | $2500$ | 无 |\n| $6$ | ${10}^5$ | B |\n| $7$ | ${10}^5$ | C |\n| $8$ | ${10}^5$ | 无 |\n| $9 \\sim 10$ | $5 \\times {10}^5$ | 无 |\n\n特殊性质 A：$a_i = (i \\bmod n) + 1$。  \n特殊性质 B：对于任意 $1 \\le i \\le n$，存在 $1 \\le k \\le 20$，$a^{(k)}_i = i$。  \n特殊性质 C：存在大小不超过 $10$ 的集合 $S$，使得对于任意 $1 \\le i \\le n$，存在 $x \\in S, k \\ge 0$，$a^{(k)}_x = i$。\n\n**【提示】**\n\n输入数据规模较大，请使用较为快速的输入方式。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8338","tags":["数学","暴力数据结构","各省省选","平衡树","2022","安徽","O2优化","优先队列","素数判断,质数,筛法"],"sample_group":[["2\n3\n1 2 3\n3\n2 3 1\n","12\n0\n"]],"created_at":"2026-03-03 11:09:25"}}