2020牛客暑期多校训练营（第五场）E

题目描述

  Today Tonnnny the monkey learned a new algorithm called Bogo Sort. The teacher gave Tonnnny the code of Bogo sort.

bool is_sorted(int a[], int n) {
    for (int i = 1; i < n; i++) {
        if (a[i] < a[i - 1]) {
            return false;
        }
    }
    return true;
}
void bogo_sort(int a[], int n){
    while (!is_sorted(a, n)){
        shuffle(a, a + n);
    }
} 

  The teacher said the shuffle function is to uniformly randomly permute the array with length , and the algorithm's expectation complexity is .
  However, Tonnnny is a determined boy — he doesn't like randomness at all! So Tonnnny improved Bogo Sort. He had chosen one favorite permutation with length , and he replaced the random shuffle with shuffle of , so the improved algorithm, Tonnnny Sort, can solve sorting problems for length array — at least Tonnnny thinks so.

int p[N]={....};// Tonnnny's favorite permutation of n
void shuffle(int a[],int n){
    int b[n];
    for (int i=0;i<n;i++){
        b[i]=a[i]
    }
    for (int i=0;i<n;i++) {
        a[i]=b[p[i]];
    }
}
void tonnnny_sort(int a[], int n){
    assert (n == N); // Tonnnny appointed!
    while (!is_sorted(a, n)){
        shuffle(a, a + n);
    }
}

  Tonnnny was satsified with the new algorithm, and decided to let you give him a different array of length every day to sort it with Tonnnny Sort.
  You are the best friend of Tonnnny. Even though you had found the algorithm is somehow wrong, you want to make Tonnnny happy as long as possible. You're given , and you need to calculate the maximum number of days that Tonnnny will be happy, since after that you can't give Tonnnny an array that can be sorted with Tonnnny Sort and didn't appeared before.
  The answer may be very large. Tonnnny only like numbers with at most digits, so please output answer mod instead.

输入描述

  The first line contains one integer .
  The second line contains integer indicating , which forms a permutation of .

输出描述

The maximum number of days that Tonnnny will be happy, module .

示例1

输入

5
1 2 3 4 5

输出

1

示例2

输入

6
2 3 4 5 6 1

输出

6

分析

  在 的 中，有操作 ，实际上是用置换 将原序列 映射到当前的序列 。如 ，那么就有：，，，形成了 的闭环，即 三者的值进行了交换；同理，有 这样的闭环。
  问题转化为：给定置换 ，求多少种排列可以通过置换 完成排序。不妨考虑将排序后的序列 用置换 打乱会产生多少种不同序列。设排序后的序列为 ， 有 个环，且各个环的长度为 ，显然，利用置换 进行 次 ， 回到最初排完序的状态，而每次操作后得到的序列都是不同的。因此，只要找出置换 所有的环，所有环长的最小公倍数即为答案。
  值得注意的是，数据范围较大，可以使用 的 类。并且，所有环的长度总和为 ，所以所有环的长度的最小公倍数不可能超过 ，因此最后不必煞费苦心地将答案对 取模。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 2020牛客暑期多校训练营（第五场） Problem E
Date: 8/20/2020
Description: Group Theory, BigInteger
*******************************************************************/
import java.math.BigInteger;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        final int N=100005;
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        BigInteger[] cycle=new BigInteger[N];//环长度
        boolean[] vis=new boolean[N];
        int[] p=new int[N];
        int m=0;
        int i;
        for(i=1;i<=n;i++){
            p[i]=in.nextInt();
        }
        for(i=1;i<=n;i++){
            int len=0;
            int pos=i;
            while(!vis[pos]){
                //遍历环
                //记录访问
                len++;
                vis[pos]=true;
                pos=p[pos];
            }
            if(len>0) cycle[++m]=BigInteger.valueOf(len);
        }
        BigInteger ans=cycle[1];
        //求环长度的最大公约数
        for(i=2;i<=m;i++){
            ans=cycle[i].multiply(ans).divide(cycle[i].gcd(ans));
        }
        System.out.println(ans);
    }
}