题目链接:https://ac.nowcoder.com/acm/contest/5670/E

在这里插入图片描述

题意

已知一个长度为n的序列p,用序列p将排列a(未知)进行置换,要求找到排列使其被p置换若干次之后能够有序,求满足条件的排列有多少种。

思路

举个例子说明一下置换群,其实就是找环。比如p为3 2 1,a为3 2 1,那么a被p置换一次后为1 2 3,再被置换一次为3 2 1,又变为了原数组,即1 3构成一个环,2自身构成一个环。

本题实际上就是要求出每个环的长度,然后求所有环的长度的LCM,因为从最开始的有序序列开始转,转LCM次又能回到最初的序列,每转一次就能得到一个新序列。第i个序列转LCM-i次后,一定能有序,比如从最开始的有序序列转1次得到新序列a1,它再转LCM-1次就有序了;从最开始转2次得到新序列a2,它再转LCM-2次就有序了。
题目中还要求对10^n^取模,实际上是不必要的,因为数的长度不会超过n位(按阶乘放大估计一下,100000! 的位数为456574)。所以答案肯定能爆long long,要写高精度,那不如直接用Java的BigInteger。

AC代码(Java)

import java.io.*;
import java.math.BigInteger;

public class Main {

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int n = (int)in.nval;
        int p[] = new int[n+10];
        for(int i = 1; i <= n; i++) {
            in.nextToken();
            p[i] = (int)in.nval;
        }
        BigInteger ans = solve(p,n);
        out.println(ans);
        out.flush();
    }

    static BigInteger lcm(BigInteger a, BigInteger b) {
        return a.divide(a.gcd(b)).multiply(b); // lcm=a/gcd*b
    }

    static BigInteger solve(int p[], int n) {
        boolean vis[] = new boolean[n+10];
        BigInteger ans = BigInteger.ONE;
        for(int i = 1; i <= n; i++) {
            if(!vis[i]) {
                // 环的起点位置为i,当前位置为j,下一个位置为p[j]
                vis[i] = true;
                int cnt = 1; 
                for(int j = p[i]; j != i; j = p[j]) { 
                    cnt++;
                    vis[j] = true;
                }
                if(cnt!=0)ans = lcm(ans, BigInteger.valueOf(cnt));
            }
        }
        return ans;
    }

}

另外,学到了Java的快读快写,420ms->85ms

StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

// 快读
in.nextToken();
int n = (int)in.nval;

// 快写
out.println(n);
out.flush();