2020牛客多校第五场 Bogo Sort（置换）

本文主要是介绍2020牛客多校第五场 Bogo Sort（置换），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
置换方式为 $c [i] = a [b [i]]$ ，a为初始数字，b为置换数组。
给你初始b数组，求存在多少个a数组经过一些置换可以变成有序数组。

思路：
第二场的时候也出了个置换题，只不过是给你初始序列和最终序列，求置换数组，而且置换方程为 $c [i] = b [a [i]]$

本题置换方式不同，但想法差不多，都得找环。而本题只是求排列 $[1, 2, 3, 4, 5 . . .]$ 可以置换成多少个其他排列，所以具体置换过程我们不考虑。

可以模拟出当 $a = [1, 2, 3, 4, 5 . . .]$ 的时候， $c [i] = a [b [i]]$ 置换是将 $i$ 置换成 $b [i]$ ，继续往后考虑，则将置换表示成 $c [i] = a [b [b [b . . . [b [i]]]]$ 的时候，初始的 $a$ 串为 $a [i] = i$ ，可以直接表示成 $c [i] = b [b [b [b [b [. . . b [i]]]]]$ ，所以每次置换是将 $i$ 置换成 $b [i]$ 。

所以置换的方式确定了。我们要考虑的就是数目了，我们按照 $i - > b [i]$ 的方式找环，得到每个环的长度，当走了环长度的lcm步时，则回到原点，所以变化的路径长度为LCM(环长度)，也就是所求的a数组数目


import java.math.BigInteger;
import java.util.Scanner;public class Main {static int []fa = new int[100005];static int []cnt = new int[100005];static int []array = new int[100005];BigInteger zero = BigInteger.ZERO;public static BigInteger GCD(BigInteger n,BigInteger m) {if(m.equals(BigInteger.ZERO)) {return n;}return GCD(m,n.mod(m));}public static BigInteger LCM(BigInteger n,BigInteger m) {BigInteger tmp = GCD(n,m);return n.multiply(m).divide(tmp);}public static int findset(int x) {if(x == fa[x]) {return x;}return fa[x] = findset(fa[x]);}public static void main(String args[]) {int n;Scanner cin = new Scanner(System.in);n = cin.nextInt();for(int i = 1;i <= n;i++) {fa[i] = i;cnt[i] = 0;}BigInteger ans = BigInteger.ONE;BigInteger mod = BigInteger.ONE;for(int i = 1;i <= n;i++) {array[i] = cin.nextInt();mod = mod.multiply(BigInteger.valueOf(10));}for(int i = 1;i <= n;i++) {int rx = findset(i);int ry = findset(array[i]);fa[rx] = ry;}for(int i = 1;i <= n;i++) {cnt[findset(i)]++;}BigInteger pre = BigInteger.ONE;for(int i = 1;i <= n;i++) {if(i == findset(i)) {ans = LCM(ans,BigInteger.valueOf(cnt[i]));}}System.out.println(ans.mod(mod));}
}