Exercise

Pista 1

¿Cómo sabemos si un camino de ” $k$ pasos” es alcanzable?

Pista 1 (respuesta)

Tras examinar la entrada de ejemplo (más concretamente el caso de $6$ pasos en el enunciado), podemos ver que las vacas se mueven en ciclos disjuntos.

Cycles of the sample input.

Como en cada ciclo $i$ las vacas tardan $\texttt{len}(i)$ pasos en volver a sus posiciones originales, donde $\texttt{len}(x)$ denota la longitud del $x$ -ésimo ciclo. Así, tardarán $lcm(\texttt{len}(0), \texttt{len}(1), \dots, \texttt{len}(N - 1))$ en volver a la permutación identidad.

Pista 2

Con esta información, ¿cómo deberíamos construir nuestros ciclos para asegurarnos de haber cubierto todos los caminos posibles?

Pista 2 (respuesta)

Como tener cualquier conjunto de ciclos con factores comunes solo podría empeorar nuestra respuesta (dividir por su GCD no cambiaría la respuesta), podemos asumir que todos los ciclos son coprimos dos a dos. Así, para cualquier camino de $k$ pasos posible, podemos construirlo con un conjunto de ciclos donde el tamaño de cada ciclo es un factor primo de $k$ . En otras palabras, si $k = \prod p_1^{e_1},p_2^{e_2},\dots, p_n^{e_n}$ , el número mínimo de vacas que necesitamos es $\sum p_1^{e_1},p_2^{e_2},\dots, p_n^{e_n}$ .

Para las vacas restantes, podemos simplemente ciclarlas sobre sí mismas. Esto es porque un bucle es equivalente a quitar ese ciclo del grafo ( $lcm(1, x) = x$ ),

Ahora, solo hay que calcular la suma de los números con $\sum p_1^{e_1},p_2^{e_2},\dots, p_n^{e_n} \leq N$ .

Solución

Editorial oficial (C++)

Explicación

Por las pistas de arriba, sabemos que podemos construir cualquier camino de $k$ pasos si la suma de la factorización prima de $k$ es menor o igual que $N$ .

¡Podemos usar DP de mochila (Knapsack DP) para esto!

Estados

Como tenemos que elegir si tomar o no algún múltiplo de un primo, necesitamos llevar la cuenta de dos cosas:

Los primos que hemos considerado
El número de vacas que hemos usado

Como $N \leq 10^4$ , solo hay $1229$ primos a considerar.

Sea $\texttt{dp}_{i,j} =$ la respuesta para los primeros $i$ primos, dado que solo podemos usar hasta $j$ vacas.

La respuesta será simplemente $\texttt{dp}_{P, N}$ , donde $P$ representa el número de primos $\leq N$ .

Casos base

Sabemos que si nuestro arreglo objetivo es el de la identidad, completaremos el ejercicio en $0$ pasos. Así, $\texttt{dp}_{0, 0} = 1$ .

Transiciones

Inicialmente, asignaremos $\texttt{dp}_{i, j} = \texttt{dp}_{i -1, j}$ , ya que siempre podemos elegir no tomar el $i$ -ésimo primo.

Tras fijar un ciclo de tamaño $p^e$ , necesitamos sumar todas las demás formas de completar el ejercicio con $j - p^e$ vacas.

Así, mientras $p^e \leq j$ :

\texttt{dp}_{i, j} \mathrel{+}= \texttt{dp}_{i - 1, j - p^e} \cdot p^e

Implementación

Complejidad temporal: $\mathcal{O}(NP)$ , donde $P$ representa el número de primos $\leq N$ .

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
	freopen("exercise.in", "r", stdin);
	freopen("exercise.out", "w", stdout);
 
	int n, m;
	cin >> n >> m;
 
	// criba de Eratóstenes para precomputar primos
	vector<bool> is_prime(n + 1, true);
	is_prime[0] = false;
	is_prime[1] = false;
	for (int i = 2; i <= n; i++) {
		if (!is_prime[i]) { continue; }
		for (ll j = i * i; j <= n; j += i) { is_prime[j] = false; }
	}
 
	vector<int> primes;
	for (int i = 1; i <= n; i++) {
		if (is_prime[i]) { primes.push_back(i); }
	}
 
	vector<vector<ll>> dp((int)primes.size() + 1, vector<ll>(n + 1, 0));
 
	// fijamos las permutaciones identidad
	for (int i = 0; i <= n; i++) { dp[0][i] = 1; }
 
	for (int i = 1; i <= (int)primes.size(); i++) {
		for (int j = 0; j <= n; j++) {
			// inicial: no usar prime[i] en absoluto
			dp[i][j] = dp[i - 1][j] % m;
 
			// usamos todas las potencias posibles de prime[i]
			ll cur_exp = primes[i - 1];
			while (j >= cur_exp) {
				dp[i][j] += (dp[i - 1][j - cur_exp] % m) * (cur_exp % m);
 
				cur_exp = ((cur_exp % m) * (primes[i - 1] % m));
			}
		}
	}
 
	cout << dp[(int)primes.size()][n] % m << endl;
}


import java.io.*;
import java.math.BigInteger;
import java.util.*;
 
public final class Exercise {
	public static void main(String[] args) throws IOException {
		StringTokenizer initial = new StringTokenizer(
		    new BufferedReader(new FileReader("exercise.in")).readLine());
		int cowNum = Integer.parseInt(initial.nextToken());
		BigInteger mod = new BigInteger(initial.nextToken());
 
		// la suma de todos los LCM de las potencias de primos que suman i (el
		// índice del arreglo)
		BigInteger[] totalWithSum = new BigInteger[cowNum + 1];
		Arrays.fill(totalWithSum, BigInteger.ZERO);
 
		totalWithSum[0] = new BigInteger("1");
		for (int i = 2; i <= cowNum; i++) {
			if (!prime(i)) { continue; }
 
			/*
			 * mantenemos otro arreglo donde guardamos las actualizaciones para
			 * que las potencias de primo de un mismo número no interfieran
			 * entre sí
			 */
			BigInteger[] updatedTotal = totalWithSum.clone();
			for (int p = i; p <= cowNum; p *= i) {  // recorremos todas las potencias de primo
				for (int from = 0; from + p <= cowNum; from++) {
					updatedTotal[from + p] = updatedTotal[from + p].add(
					    totalWithSum[from].multiply(new BigInteger(String.valueOf(p))));
				}
			}
			totalWithSum = updatedTotal;
		}
 
		BigInteger total = BigInteger.ZERO;
		for (BigInteger prod : totalWithSum) { total = total.add(prod); }
		total = total.mod(mod);
 
		PrintWriter written = new PrintWriter("exercise.out");
		written.println(total);
		written.close();
	}
 
	// https://geeksforgeeks.org/primality-test-set-1-introduction-and-school-method
	private static boolean prime(int n) {
		if (n <= 1) return false;
		if (n <= 3) return true;
		if (n % 2 == 0 || n % 3 == 0) return false;
 
		for (int i = 5; i * i <= n; i = i + 6) {
			if (n % i == 0 || n % (i + 2) == 0) { return false; }
		}
		return true;
	}
}


read = open("exercise.in", "r").readline
write = open("exercise.out", "w").write
 
n, m = map(int, read().split())
 
is_prime = [True] * (n + 1)
is_prime[0] = False
is_prime[1] = False
 
for i in range(2, n + 1):
	if not is_prime[i]:
		continue
	for j in range(i * i, n + 1, i):
		is_prime[j] = False
 
primes = [i for i in range(1, n + 1) if is_prime[i]]
 
dp = [[0] * (n + 1) for _ in range(len(primes) + 1)]
 
# fijamos las permutaciones identidad
for i in range(n + 1):
	dp[0][i] = 1
 
for i in range(1, len(primes) + 1):
	for j in range(n + 1):
		# inicial: no usar prime[i] en absoluto
		dp[i][j] = dp[i - 1][j] % m
 
		# usamos todas las potencias posibles de prime[i]
		curr_exp = primes[i - 1]
		while j >= curr_exp:
			dp[i][j] += dp[i - 1][j - curr_exp] * curr_exp
			curr_exp = curr_exp * primes[i - 1]
 
write(f"{dp[len(primes)][n] % m}")