Permutation Rounds

Explicación

Interpretemos nuestra permutación $p$ como las aristas de un grafo funcional, donde para cada $i$ existe una arista dirigida $(i, p_i)$ . Como $p$ es una permutación, cada nodo tiene grado de entrada y grado de salida uno, lo que significa que nuestro grafo está compuesto de ciclos disjuntos. Para entender por qué, observemos que un nodo conectado a un ciclo sin ser parte de él implicaría que algún nodo tiene grado de entrada mayor que uno.

Como cada nodo está en un ciclo, cada valor eventualmente vuelve a su posición de partida después de cierta cantidad de tiempo. Específicamente, si $s_i$ denota el tamaño del ciclo en el que está el nodo $i$ , entonces cada valor $i$ vuelve a su ubicación después de $s_i$ rondas.

Esto significa que nuestra respuesta es $\text{lcm}(s_1, s_2, \dots, s_n)$ , porque el MCM de los tamaños de los ciclos corresponde al primer valor divisible por todos los tamaños de ciclo. Sin embargo, calcular el MCM de forma trivial no es posible, porque necesitamos hallar el valor módulo $10^9 + 7$ , y el MCM puede crecer mucho más allá de esa cota. Notar que usar la fórmula $\text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}$ y calcular el MCM de forma iterativa tampoco funciona, porque $a$ y $b$ estar bajo módulo implica que el inverso modular del GCD no se calculará correctamente.

Recordemos que el MCM de dos números se puede calcular tomando cada primo que aparece en alguno de los números y elevándolo a la potencia más grande que aparece en alguna de las factorizaciones. Formalmente, esto se puede escribir como

\text{lcm}(a, b) = \prod_{p \mid ab} p^{\max(\text{power of } p \text{ in } a, \text{ power of } p \text{ in } b)}.

Con esto en mente, podemos calcular el MCM de nuestros valores $s_i$ factorizando en primos cada $s_i$ , y combinándolo con el MCM de todos los $i$ previos usando la formulación de arriba. Guardamos los factores primos en un mapa y usamos división simple para calcular nuestra factorización prima.

Implementación

Complejidad temporal: $\mathcal{O}(N \sqrt N)$

C++PythonJava


#include <bits/stdc++.h>
 
using ll = long long;
 
constexpr int MOD = 1e9 + 7;
 
std::vector<std::array<int, 2>> prime_factorize(int x) {
	std::vector<std::array<int, 2>> res;
	for (int i = 2; i * i <= x; i++) {
		int freq = 0;
		while (x % i == 0) {
			x /= i;
			freq++;
		}
 
		if (freq > 0) { res.push_back({i, freq}); }
	}
 
	if (x > 1) { res.push_back({x, 1}); }
 
	return res;
}
 
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
 
	int n;
	std::cin >> n;
	std::vector<int> p(n);
	for (int &i : p) { std::cin >> i, i--; }
 
	std::vector<bool> vis(n);
	std::map<int, int> primes;
	for (int i = 0; i < n; i++) {
		if (vis[i]) { continue; }
		int in_cycle = 0;
		int ptr = i;
		while (!vis[ptr]) {
			in_cycle++;
			vis[ptr] = true;
			ptr = p[ptr];
		}
 
		auto factors = prime_factorize(in_cycle);
		for (const auto &[prime, freq] : factors) {
			primes[prime] = std::max(primes[prime], freq);
		}
	}
 
	int res = 1;
	for (const auto &[prime, freq] : primes) {
		for (int i = 0; i < freq; i++) { res = (1ll * res * prime) % MOD; }
	}
 
	std::cout << res << '\n';
}


MOD = 10**9 + 7
 
 
def prime_factorize(x):
	res = []
	i = 2
	while i * i <= x:
		freq = 0
		while x % i == 0:
			x //= i
			freq += 1
		if freq > 0:
			res.append((i, freq))
		i += 1
 
	if x > 1:
		res.append((x, 1))
 
	return res
 
 
n = int(input())
p = [int(x) - 1 for x in input().split()]
 
vis = [False] * n
primes = {}
 
for i in range(n):
	if vis[i]:
		continue
	in_cycle = 0
	ptr = i
	while not vis[ptr]:
		in_cycle += 1
		vis[ptr] = True
		ptr = p[ptr]
 
	for prime, freq in prime_factorize(in_cycle):
		primes[prime] = max(primes.get(prime, 0), freq)
 
res = 1
 
for prime, freq in primes.items():
	for _ in range(freq):
		res = (res * prime) % MOD
 
print(res)


import java.io.*;
import java.util.*;
 
public class PermutationRounds {
	static final long MOD = 1000000007L;
 
	static List<int[]> primeFactorize(int x) {
		List<int[]> res = new ArrayList<>();
		for (int i = 2; i * i <= x; i++) {
			int freq = 0;
			while (x % i == 0) {
				x /= i;
				freq++;
			}
 
			if (freq > 0) { res.add(new int[] {i, freq}); }
		}
 
		if (x > 1) { res.add(new int[] {x, 1}); }
 
		return res;
	}
 
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
 
		int n = sc.nextInt();
		int[] p = new int[n];
		for (int i = 0; i < n; i++) { p[i] = sc.nextInt() - 1; }
 
		boolean[] vis = new boolean[n];
		Map<Integer, Integer> primes = new HashMap<>();
 
		for (int i = 0; i < n; i++) {
			if (vis[i]) continue;
 
			int inCycle = 0;
			int ptr = i;
			while (!vis[ptr]) {
				vis[ptr] = true;
				inCycle++;
				ptr = p[ptr];
			}
 
			for (int[] factor : primeFactorize(inCycle)) {
				int prime = factor[0];
				int freq = factor[1];
				primes.put(prime, Math.max(primes.getOrDefault(prime, 0), freq));
			}
		}
 
		long res = 1;
		for (Map.Entry<Integer, Integer> e : primes.entrySet()) {
			int prime = e.getKey();
			int freq = e.getValue();
			for (int i = 0; i < freq; i++) { res = (res * prime) % MOD; }
		}
 
		System.out.println(res);
	}
}