当前位置：首页 > news >正文

2020牛客暑期多校第五场 E - Bogo Sort（思维/LCM）

news 来源：原创 2024/5/3 16:19:20

题目链接

比赛时写了Java大数但是没想到不需要取模，orz…

给定数组 $p$ 对一个 $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]];
    }
}

手动模拟两个例子，我们会发现实际上能够形成排列只和环中的数目有关：
在这里插入图片描述
该样例的答案是 $6$

该样例的答案是 $2$

因为一个环在不断进行 $s h u f f l e$ 的过程中所有的数会不断交换位置，那么一个环形成的组合数也就是环中数的个数，那么考虑使用并查集求出所有的环，最后对所有个数求 $L C M$ ，因为数据很大，使用Java

PS：题目说的取模实际上就是个陷阱，最坏情况是分成若干个质数之和，可以在小范围内寻找一些数据测试一下，因为素数的分布是越向后越稀疏，那么若干个素数之和等于 $N$ ，其乘积肯定小于 $10^N$

心得：我们写出来就是在取模不取模犹豫不决，然后没敢去尝试，说白了一些猜想或者推理在比赛同样重要，与其写不出来，试一下又何妨？

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Scanner;

public class Main {
	
	static int f[]=new int[100010];
	static int p[]=new int[100010];
	
	static int find(int x) {
		if(f[x]==x) return x;
		else {
			int t=find(f[x]);
			f[x]=t;
			return f[x];
		}	
	}

	public static void main(String[] args) {
		int n;
		Scanner scanner=new Scanner(System.in);
		n=scanner.nextInt();
		for(int i=0,x;i<n;i++) {
			x=scanner.nextInt();
			p[i]=x-1;
			f[i]=i;
		}
		for(int i=0;i<n;i++) {
			if(p[i]!=i) {
				int fx=find(i);
				int fy=find(p[i]);
				if(fx!=fy) f[fy]=fx;
			}
		}
		HashMap<Integer, Integer> book=new HashMap<>();
		for(int i=0;i<n;i++) {
			find(i);
			int cur=(book.get(f[i])==null?0:book.get(f[i]));
			book.put(f[i], cur+1);
		}
		BigInteger ans=BigInteger.ONE,Mod=BigInteger.ONE;
		for (Entry<Integer, Integer> entry : book.entrySet()) {
			BigInteger temp=BigInteger.valueOf(entry.getValue());
			ans=ans.multiply(temp).divide(ans.gcd(temp));
		}
		System.out.println(ans);
	}
}