#PQJ928x4045. QOJ 928_4045

    ID: 3065 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:AHOI 2022并查集

QOJ 928_4045

NOI 2022 安徽省省队选拔 排列(perm) 排列(perm) 【题目描述】 对于一个长度为n 的排列P = (p1, p2, . . . , pn) 和整数k ≥0,定义P 的k 次幂 P (k) = ( p(k) 1 , p(k) 2 , . . . , p(k) n ) , 该排列的第i 项为 p(k) i

   i, k = 0, p(k−1) pi , k > 0. 容易证明任意排列的任意次幂都是一个排列。 定义排列P 的.循.环.值v(P) 为最小的.正.整.数k 使得P (k+1) = P。 给出一个长度为n 的排列A = (a1, a2, . . . , an),对于整数1 ≤i, j ≤n,定义f(i, j): 若存在k ≥0 使得a(k) i = j,则f(i, j) = 0,否则设排列Aij 为将排列A 的第i 项ai 和 第j 项aj 交换后得到的排列,则f(i, j) = v(Aij)。 求∑n i=1 ∑n j=1 f(i, j) 的值。答案可能很大,你只需要输出其对(109 + 7) 取模的结 果。 【输入格式】 从文件perm.in 中读入数据。 .本.题.有.多.组.测.试.数.据。输入数据的第一行为一个整数T,表示测试数据组数。 对于每组测试数据,第一行一个正整数n 表示排列的长度,接下来一行n 个整数 a1, a2, . . . , an,描述输入的排列。 【输出格式】 输出到文件perm.out 中。 对于每组数据输出一行一个整数,表示题目所求的答案对(109 + 7) 取模的结果。 【样例1 输入】 1 2 2 3 3 1 2 3 4 3 5 2 3 1 第2 页 共15 页

NOI 2022 安徽省省队选拔 排列(perm) 【样例1 输出】 1 12 2 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 ≤35,前四个测试数据满足n ≤200,所有测 试数据满足n ≤2500。 【样例3】 见选手目录下的perm/perm3.in 与perm/perm3.ans。 该组样例中,第一个测试数据满足特殊性质A,第二个测试数据满足特殊性质B, 第三个测试数据满足特殊性质C,前四个测试数据满足n ≤105,第五个测试数据满足 n ≤5 × 105。 特殊性质的具体内容参见子任务部分。 【子任务】 对于100% 的测试数据,1 ≤T ≤5,1 ≤n ≤5 × 105,1 ≤ai ≤n。 测试点编号 n ≤ 特殊性质 1 ∼2 105 A 3 35 无 4 200 5 2500 6 105 B 7 C 8 无 9 ∼10 5 × 105 第3 页 共15 页

NOI 2022 安徽省省队选拔 排列(perm) 特殊性质A:ai = (i mod n) + 1。 特殊性质B:对于任意1 ≤i ≤n,存在1 ≤k ≤20,a(k) i = i。 特殊性质C:存在大小不超过10 的集合S,使得对于任意1 ≤i ≤n,存在 x ∈S, k ≥0,a(k) x = i。 【提示】 输入数据规模较大,请使用较为快速的输入方式。 第4 页 共15 页