7394. 排列轮数 (Permutation Rounds)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 排列轮数 (Permutation Rounds) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 有一个已排序的数组 $[1,2,\dots,n]$ 以及一个排列 $p_1,p_2,\dots,p_n$。在每一轮中，数组中的所有元素都会根据该排列进行移动：原本处于位置 $i$ 的元素将会移动到位置 $p_i$。 请问在经历了多少轮之后，该数组才首次重新回到完全排好序的状态？ ## 输入格式 第一行包含一个整数 $n$。 第二行包含 $n$ 个整数 $p_1,p_2,\dots,p_n$：给定的排列。 ## 输出格式 输出重新排好序所需的最少轮数，结果对 $10^9+7$ 取模。 ## 输入输出样例 ### 输入 #1 ```text 8 5 3 2 6 4 1 8 7 ``` ### 输出 #1 ```text 4 ``` ## 说明/提示 在每一轮后，数组的变化情况如下： - 第 $1$ 轮：$[6,3,2,5,1,4,8,7]$ - 第 $2$ 轮：$[4,2,3,1,6,5,7,8]$ - 第 $3$ 轮：$[5,3,2,6,4,1,8,7]$ - 第 $4$ 轮：$[1,2,3,4,5,6,7,8]$ ### 数据规模与约定 - $1 \le n \le 2 \cdot 10^5$ ---