Este documento presenta un análisis y solución para una serie de problemas de algoritmia, cubriendo conceptos como la teoría de grafos, cálculo de probabilidades con enfoques golosos y programación dinámica para la optimización de fracciones.
Problema 1: Conjunto de Números Especiales
Descripción General del Problema: Se define una función (f(x)) como la suma de los dígitos de un entero positivo (x) en base diez (por ejemplo, (f(114514) = 1+1+4+5+1+4=16)). Tenemos un conjunto de números especiales (S). Nos dan tres enteros positivos (n, x, k), y se definen las propiedades del conjunto (S) de la siguiente manera:
- El número \(x\) pertenece a \(S\).
- Si un entero positivo \(y\) satisface \(y \le n\) y \(y - f(y) \times k\) pertenece a \(S\), entonces \(y\) también pertenece a \(S\).
- Si un entero positivo \(y\) satisface \(y \le n\) y existe un entero positivo \(c > 1\) tal que \(y^c\) pertenece a \(S\), entonces \(y\) también pertenece a \(S\). El objetivo es determinar la cantidad máxima de números distintos que se pueden identificar como parte del conjunto (S) usando una estrategia óptima.
Análisis y Estrategia: La naturaleza de las reglas de membresía del conjunto (S) sugiere una interpretación como un problema de búsqueda en grafos. Podemos considerar cada número entero de (1) a (n) como un nodo en un grafo dirigido. Las reglas establecen relaciones de dependencia que se pueden modelar como aristas:
- Para la regla 2: Si \(v = u - f(u) \times k\) está en \(S\), entonces \(u\) está en \(S\). Esto implica una arista dirigida de \(v\) a \(u\).
- Para la regla 3: Si \(v = u^c\) está en \(S\), entonces \(u\) está en \(S\). Esto implica una arista dirigida de \(v\) a \(u\). El problema se reduce a encontrar todos los nodos alcanzables desde el nodo inicial (x) en este grafo, siguiendo las aristas en sentido inverso (o construyendo las aristas en el sentido opuesto si preferimos una BFS estándar desde (x)). Dado que la regla 2 depende de un valor calculado y la regla 3 de potencias, construir el grafo y luego ejecutar un recorrido BFS (Búsqueda en Amplitud) es una estrategia eficaz.
Los pasos son los siguientes:
- Precomputar Sumas de Dígitos: Calcular \(f(i)\) para todos los \(i\) de \(1\) a \(n\). Esto se puede hacer en \(O(n)\) tiempo.
- Construir el Grafo: - Para la regla 2: Iterar \\(i\\) de \\(1\\) a \\(n\\). Calcular \\(destino = i - f(i) \\times k\\). Si \\(destino > 0\\), añadir una arista dirigida de \\(destino\\) a \\(i\\). - Para la regla 3: Iterar \\(i\\) desde \\(2\\) hasta \\(\\sqrt{n}\\) (ya que \\(i^c > n\\) para \\(i > \\sqrt{n}\\) si \\(c \\ge 2\\)). Para cada \\(i\\), calcular \\(j = i^2, i^3, \\dots\\) mientras \\(j \\le n\\). Añadir una arista dirigida de \\(j\\) a \\(i\\).
- Ejecutar BFS: Iniciar una BFS desde el nodo \(x\). Marcar todos los nodos visitados.
- Contar Nodos: El número total de nodos visitados es la respuesta. La complejidad de la construcción del grafo es (O(n)) para las reglas de suma de dígitos y (O(\sqrt{n} \log n)) (o más precisamente, (\sum_{i=2}^{\sqrt{n}} \log_i n)) para las reglas de potencias. La BFS tiene una complejidad de (O(V+E)), donde (V=n) y (E) es el número de aristas, que es (O(n)). Por lo tanto, la complejidad total es (O(n)).
Implementación con BFS: A continuación se muestra un ejemplo de implementación utilizando BFS:
#include <iostream>
#include <vector>
#include <queue>
#include <numeric> // Para std::accumulate, aunque no se usa aquí
using namespace std;
const int MAX_N = 1e7 + 10;
vector<int> adj[MAX_N]; // Lista de adyacencia
int sumaDigitos[MAX_N];
bool visitado[MAX_N];
void calcularSumasDigitos(int n_max) {
for (int i = 1; i <= n_max; ++i) {
sumaDigitos[i] = (i % 10) + sumaDigitos[i / 10];
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, x, k;
cin >> n >> x >> k;
calcularSumasDigitos(n);
// Construir aristas para la regla 2: y - f(y)*k -> y
for (int i = 1; i <= n; ++i) {
int origen = i - sumaDigitos[i] * k;
if (origen > 0 && origen <= n) { // Asegurarse de que 'origen' sea un nodo válido
adj[origen].push_back(i);
}
}
// Construir aristas para la regla 3: y^c -> y
for (long long i = 2; i * i <= n; ++i) { // Empezar con base 2, y^c, con c > 1
long long actual = i * i;
while (actual <= n) {
adj[actual].push_back(i);
if (n / i < actual) break; // Evitar overflow antes de multiplicar
actual *= i;
}
}
queue<int> cola;
cola.push(x);
visitado[x] = true;
int contadorConjunto = 0;
while (!cola.empty()) {
int u = cola.front();
cola.pop();
contadorConjunto++;
for (int v : adj[u]) {
if (!visitado[v]) {
visitado[v] = true;
cola.push(v);
}
}
}
cout << contadorConjunto << endl;
return 0;
}
Un enfoque alternativo, a menudo utilizado en programación competitiva, es una simulación iterativa. Consiste en mantener un arreglo booleano para indicar si un número está en el conjunto. Se inicializa el arreglo con (x) y luego se itera repetidamente sobre todos los números de (1) a (n), aplicendo las reglas para actualizar el estado del arreglo. Este proceso se repite hasta que no se realicen más cambios en una iteración completa. Aunque puede parecer "heurístico", en ciertos contextos con pequeñas constantes, puede ser sorprendentemente eficiente.
Implementación Heurística / Iterativa:
#include <iostream>
#include <vector>
#include <cmath> // Para sqrt
using namespace std;
const int MAX_N_ITERATIVE = 10000010; // N puede ser hasta 10^7
int sumaDigitos_iter[MAX_N_ITERATIVE];
bool estaEnConjunto[MAX_N_ITERATIVE];
int n_iter, x_iter, k_iter;
int conteoTotal = 0;
void inicializarSumasDigitos(int n_max) {
for (int i = 1; i <= n_max; i++) {
sumaDigitos_iter[i] = (i % 10) + sumaDigitos_iter[i / 10];
}
}
// Función para verificar la regla 3 (potencias)
void verificarPorPotencia(int base) {
long long potencia = (long long)base * base; // Empieza con c=2
while (potencia <= n_iter) {
if (estaEnConjunto[potencia]) {
if (!estaEnConjunto[base]) {
estaEnConjunto[base] = true;
conteoTotal++;
}
return; // Si una potencia mayor ya está en S, la base también lo está.
}
if (potencia > n_iter / base) break; // Evitar overflow antes de multiplicar
potencia *= base;
}
}
// Función para verificar la regla 2 (sustracción)
void verificarPorSustraccion(int num) {
int predecesor = num - k_iter * sumaDigitos_iter[num];
if (predecesor > 0 && predecesor <= n_iter && estaEnConjunto[predecesor]) {
if (!estaEnConjunto[num]) {
estaEnConjunto[num] = true;
conteoTotal++;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n_iter >> x_iter >> k_iter;
inicializarSumasDigitos(n_iter);
if (x_iter == 1) { // Caso especial: si 1 está en S, no se pueden formar potencias de 1.
cout << 1 << endl; // Pero 1 es la única en S por esta regla.
return 0;
}
estaEnConjunto[x_iter] = true;
conteoTotal++;
int limiteRaiz = (int)sqrt(n_iter);
// Bucle principal de la "simulación"
while (true) {
int conteoAnterior = conteoTotal;
// Regla 3: y^c en S => y en S.
// Recorremos las bases posibles para potencias.
for (int i = 2; i <= limiteRaiz; i++) {
if (!estaEnConjunto[i]) { // Solo verificamos si la base aún no está en S
verificarPorPotencia(i);
}
}
// Regla 2: y - f(y)*k en S => y en S.
// Recorremos todos los números para aplicar esta regla.
for (int i = 1; i <= n_iter; i++) {
if (!estaEnConjunto[i]) { // Solo verificamos si el número aún no está en S
verificarPorSustraccion(i);
}
}
if (conteoTotal == conteoAnterior) { // Si no hubo cambios, terminamos
break;
}
}
cout << conteoTotal << endl;
return 0;
}
Problema 2: Optimización de Probabilidad en Rodillos Numéricos
Descripción del Problema: Frente a un palacio, hay un dispositivo con varios rodillos, cada uno mostrando un dígito del 0 al 9. Estos rodillos forman un número entero positivo (N). Para abrir la puerta, se puede realizar una operación una única vez: seleccionar un subconjunto de rodillos y girarlos. Cada rodillo seleccionado cambia de forma independiente y equiprobable a cualquier dígito del 0 al 9. Si el nuevo número (N') resultante es estrictamente mayor que el original (N), la puerta se abre. El objetivo es elegir los rodillos a girar de manera que se maximice la probabilidad de que (N' > N), y devolver esta probabilidad módulo (998244353).
Análisis y Estrategia: Para maximizar la probabilidad de que el nuevo número (N') sea mayor que (N), debemos priorizar los cambios en las posiciones más significativas (más a la izquierda). Si cambiamos un dígito en una posición (i) y este cambio hace que el nuevo dígito sea mayor que el original, entonces (N') será definitivamente mayor que (N), independientemente de los dígitos a la derecha. Consideremos el número (N) como una cadena de dígitos (d_1 d_2 \dots d_L). La probabilidad de que (N' > N) puede expresarse como una suma de probabilidades condicionadas. La estrategia óptima es un enfoque goloso: Se construye la probabilidad acumulada de izquierda a derecha. Para cada posición (i) (empezando desde 1):
- Si el dígito \(d_i\) se cambia a un valor mayor, el número \(N'\) ya es mayor que \(N\). La probabilidad de esto es \((9 - d_i) / 10\).
- Si el dígito \(d_i\) se cambia al mismo valor \(d_i\), entonces el resultado de \(N' > N\) depende de los dígitos restantes a la derecha. La probabilidad de que esto suceda es \(1/10\).
- Si el dígito \(d_i\) se cambia a un valor menor, \(N'\) será menor que \(N\). La probabilidad es \(d_i / 10\). Para maximizar la probabilidad, debemos elegir los rodillos de manera que las "contribuciones" de las posiciones más significativas sean las más grandes posibles. El problema plantea que podemos elegir "algunos rodillos". Si elegimos un conjunto de rodillos (P = {p_1, p_2, \dots, p_k}) donde (p_1 < p_2 < \dots < p_k) son las posiciones de los rodillos seleccionados: La probabilidad total de que (N' > N) es la suma de las probabilidades de los eventos disjuntos: El primer dígito seleccionado (d_{p_1}) se convierte en un valor mayor. El primer dígito seleccionado (d_{p_1}) se convierte en el mismo valor, y el segundo dígito seleccionado (d_{p_2}) se convierte en un valor mayor. Y así sucesivamente. Esto se traduce en la fórmula: (P = \sum_{j=1}^{k} \left( \frac{9 - d_{p_j}}{10} \times \left(\frac{1}{10}\right)^{j-1} \right)) donde (d_{p_j}) es el valor del dígito en la posición (p_j). Para maximizar esta suma, debemos elegir los dígitos (d_{p_j}) que sean lo más pequeños posible, priorizando las posiciones más a la izquierda (menor (j)). La estrategia óptima es encontrar el mínimo dígito en un sufijo y seleccionarlo. Luego, se avanza a la posición siguiente a la del dígito seleccionado. Específicamente, se precalculan los mínimos sufijos para la cadena de dígitos. Para cada posición (i), se encuentra el valor mínimo (m_i) en el sufijo desde (i) hasta (L) y la primera posición (pos_i) donde aparece ese mínimo. Luego, se itera, seleccionando el dígito (d_{pos_i}), y se avanza a la posición (pos_i + 1).
Pasos de la solución:
- Precalcular las potencias inversas de 10 módulo \(998244353\), es decir, \(10^{-1}, 10^{-2}, \dots, 10^{-L}\).
- Precalcular dos arreglos para cada posición \(i\) desde \(L\) hasta \(1\): -
minimoSufijo\[i\]: El valor mínimo de los dígitos en el sufijo \\(d\_i \\dots d\_L\\). -posicionMinimoSufijo\[i\]: La primera posición donde se encuentra ese valor mínimo en el sufijo \\(d\_i \\dots d\_L\\). - Iterar desde la primera posición (\(l=1\)). En cada paso, se toma el valor mínimo \(m = \text{minimoSufijo}[l]\) y su posición \(p = \text{posicionMinimoSufijo}[l]\). Se añade \((9 - m) \times 10^{-(\text{número de dígitos seleccionados hasta ahora})}\) a la probabilidad total. Luego se actualiza \(l = p + 1\) y se incrementa el contador de dígitos seleccionados. Se repite hasta que \(l > L\).
- El resultado final se imprime módulo \(998244353\).
Implementación:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int MAX_LEN_NUM = 200010;
const int MODULO = 998244353;
char cadenaNumerica[MAX_LEN_NUM];
long long inversosDiez[MAX_LEN_NUM];
int minimoSufijo[MAX_LEN_NUM];
int posicionMinimoSufijo[MAX_LEN_NUM];
// Función para calcular (a^b) % MODULO
long long potenciaModularInversa(long long base, long long exp) {
long long res = 1;
base %= MODULO;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MODULO;
base = (base * base) % MODULO;
exp /= 2;
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> (cadenaNumerica + 1); // Leer la cadena, ignorando el índice 0
int longitud = strlen(cadenaNumerica + 1);
// Calcular inversos modulares de las potencias de 10
inversosDiez[1] = potenciaModularInversa(10, MODULO - 2); // 10^-1 mod MODULO
for (int i = 2; i <= longitud; i++) {
inversosDiez[i] = (inversosDiez[i - 1] * inversosDiez[1]) % MODULO;
}
// Calcular mínimo sufijo y su primera posición
minimoSufijo[longitud] = cadenaNumerica[longitud] - '0';
posicionMinimoSufijo[longitud] = longitud;
for (int i = longitud - 1; i >= 1; i--) {
int digitoActual = cadenaNumerica[i] - '0';
if (digitoActual <= minimoSufijo[i + 1]) { // Si el dígito actual es menor o igual al min. del sufijo siguiente
minimoSufijo[i] = digitoActual;
posicionMinimoSufijo[i] = i;
} else {
minimoSufijo[i] = minimoSufijo[i + 1];
posicionMinimoSufijo[i] = posicionMinimoSufijo[i + 1];
}
}
long long probabilidadMaxima = 0;
int indiceActual = 1;
int contadorDigitosSeleccionados = 1;
// Iterar para construir la probabilidad máxima
while (indiceActual <= longitud) {
int valorMinimoSeleccionado = minimoSufijo[indiceActual];
probabilidadMaxima = (probabilidadMaxima +
(long long)(9 - valorMinimoSeleccionado) * inversosDiez[contadorDigitosSeleccionados]) % MODULO;
indiceActual = posicionMinimoSufijo[indiceActual] + 1; // Mover al siguiente índice después del mínimo seleccionado
contadorDigitosSeleccionados++;
}
cout << probabilidadMaxima << endl;
return 0;
}
Problema 3: Subsegmento con Máxima Razón
Descripción del Problema: Se dan dos secuencias de enteros positivos de longitud (n), (a_1, \dots, a_n) y (b_1, \dots, b_n), y un entero (k). Se deben responder (q) consultas. Cada consulta proporciona un rango ([l, r]). El objetivo es encontrar un subintervalo ([l', r']) dentro de ([l, r]) (es decir, (l \le l' \le r' \le r)) tal que su longitud (r' - l' + 1) sea al menos (k), y la razón (\frac{\sum_{i=l'}^{r'} a_i}{\sum_{i=l'}^{r'} b_i}) sea máxima. Se pide devolver esta razón como una fracción irreducible (p/q). Si no existe tal subintervalo, se debe imprimir (0/1). Las consultas se decodifican usando un valor type y la respuesta de la consulta anterior.
Análisis y Estrategia: Este es un problema clásico de programación fraccional. La clave para resolverlo eficientemente reside en una propiedad importante de las fracciones y en la observación de que (k) es pequeño.
Propiedad Fundamental: Si (\frac{A}{B} \le \frac{C}{D}) (con (B, D > 0)), entonces (\frac{A}{B} \le \frac{A+C}{B+D} \le \frac{C}{D}). Esta propiedad implica que, para maximizar (\frac{\sum a_i}{\sum b_i}), el subintervalo óptimo no necesita ser excesivamente largo. De hecho, se puede demostrar que si un subintervalo óptimo tiene una longitud (L \ge 2k), entonces se puede dividir en dos subintervalos válidos, de los cuales al menos uno tendrá una razón no inferior al original. Esto sugiere que podemos limitar nuestra búsqueda a subintervalos de longitud entre (k) y (2k-1).
Estrategia General:
- Preprocesamiento de Sumas Prefijas: Calcular las sumas prefijas para ambas secuencias \(a\) y \(b\). Esto permite calcular la suma de cualquier subintervalo \([l', r']\) en tiempo \(O(1)\).
- Programación Dinámica (PD) para longitudes cortas: Para subintervalos de longitud \(L\) donde \(k \le L < 2k\), podemos usar una técnica de PD. Sea \(dp[len\_offset][l]\) un par \(\{S_a, S_b\}\) que representa la suma máxima de \(a\) y la suma correspondiente de \(b\) para un subintervalo de longitud \(k + len\_offset\) que empieza en \(l\). La transición sería algo como: \(dp[i][j] = \text{comparar}(\text{dp}[i-1][j], \text{dp}[i-1][j+1])\), donde
compararselecciona el par que produce la razón más alta. - Tabla Escasa (Sparse Table, ST) para longitudes más grandes: Para consultas en rangos \([l, r]\) donde los subintervalos óptimos podrían empezar en \(l\) y extenderse más allá del límite de \(2k\), se usa una tabla escasa. La tabla escasa
f\[j\]\[i\]almacenará el mejor par \(\{S_a, S_b\}\) en el rango \([i, i + 2^j - 1]\). Las entradas basef\[0\]\[i\]se llenarían con los resultados de la PD o calculando directamente para todos los subintervalos de longitud \(k\) hasta \(2k-1\) que empiezan en \(i\). - Manejo de Consultas: Para cada consulta \([L, R]\) (después de decodificarla), se divide la búsqueda en dos partes: - Subintervalos que comienzan en \\(\[L, R - 2k + 1\]\\): Estos se pueden consultar eficientemente usando la tabla escasa. - Subintervalos que comienzan en \\((R - 2k + 1, R\]\\): Estos son subintervalos "cortos" (longitud < \\(2k\\)) que se pueden manejar directamente con los resultados de la PD. La respuesta final es la mejor razón encontrada en ambas partes.
Función de Comparación: Para comparar dos fracciones (\frac{A}{B}) y (\frac{C}{D}), se puede usar la multiplicación cruzada: (\frac{A}{B} > \frac{C}{D}) si (A \times D > C \times B). Esto evita la aritmética de punto flotante y problemas de precisión. Complejidad: El preprocesamiento de sumas prefijas es (O(n)). La PD y la construcción de la tabla escasa para los intervalos de longitud hasta (2k) es (O(nk + n \log n)). Cada consulta (después de decodificación) es (O(1)) para la parte de la tabla escasa y (O(k)) para la parte de la PD (o (O(1)) si la PD ya está integrada en la ST). Con un enfoque cuidadoso, la parte de la PD se puede integrar para que las consultas sean (O(1)) amortizado para cada segmento corto. La complejidad total es (O(nk + n \log n + q)).
Implementación:
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm> // Para std::swap, std::min
#define SUM_A first
#define SUM_B second
using namespace std;
const int MAX_N_RATIO = 1000010;
const int MAX_K_RATIO = 21; // k <= 20
typedef long long ll;
typedef pair<int, int> ParSumas;
int n_ratio, k_ratio, q_ratio, type_ratio;
ll prefSumaA[MAX_N_RATIO];
ll prefSumaB[MAX_N_RATIO];
ParSumas dpSubsegmentosCercanos[MAX_K_RATIO][MAX_N_RATIO]; // dp[len_offset][inicio]
ParSumas tablaEscasa[MAX_K_RATIO][MAX_N_RATIO]; // tablaEscasa[log_len][inicio]
int logDos[MAX_N_RATIO];
void inicializarLogDos() {
logDos[1] = 0;
for (int i = 2; i <= n_ratio; i++)
logDos[i] = logDos[i / 2] + 1;
}
// Compara dos fracciones {num1, den1} y {num2, den2}
// Devuelve la que representa el valor más grande.
// Si {0,0} es pasado, devuelve la otra.
inline ParSumas compararFracciones(ParSumas frac1, ParSumas frac2) {
if (frac1.SUM_A == 0 && frac1.SUM_B == 0) return frac2;
if (frac2.SUM_A == 0 && frac2.SUM_B == 0) return frac1;
// (ll) para evitar overflow en la multiplicación cruzada
if ((ll)frac1.SUM_A * frac2.SUM_B < (ll)frac2.SUM_A * frac1.SUM_B) return frac2;
return frac1;
}
ll maximoComunDivisor(ll a, ll b) {
if (b == 0) return a;
return maximoComunDivisor(b, a % b);
}
// Inicializa la tabla escasa con los mejores resultados para rangos de longitud 2^j
void inicializarTablaEscasa() {
for (int j = 1; j <= logDos[n_ratio]; j++) {
for (int i = 1; i + (1 << j) - 1 <= n_ratio; i++) {
tablaEscasa[j][i] = compararFracciones(tablaEscasa[j - 1][i], tablaEscasa[j - 1][i + (1 << (j - 1))]);
}
}
}
// Consulta la tabla escasa para encontrar el mejor par en el rango [l, r]
inline ParSumas consultarMaxFraccion(int l, int r) {
if (l > r) return {0,0}; // Rango inválido
int t = logDos[r - l + 1];
return compararFracciones(tablaEscasa[t][l], tablaEscasa[t][r - (1 << t) + 1]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n_ratio >> k_ratio >> q_ratio >> type_ratio;
inicializarLogDos();
for (int i = 1; i <= n_ratio; i++) {
int val;
cin >> val;
prefSumaA[i] = prefSumaA[i - 1] + val;
}
for (int i = 1; i <= n_ratio; i++) {
int val;
cin >> val;
prefSumaB[i] = prefSumaB[i - 1] + val;
}
// Precomputar dpSubsegmentosCercanos para longitudes k a 2k-1 (inclusive)
// dpSubsegmentosCercanos[len_offset][l] guarda el mejor de los subsegmentos
// de longitud len = k + len_offset que comienzan en l, o subsegmentos dentro de su "vecindad"
// hasta una longitud de 2k-1.
for (int len_actual = k_ratio; len_actual < 2 * k_ratio; len_actual++) { // Longitudes desde k hasta 2k-1
int len_offset = len_actual - k_ratio;
for (int l = 1; l + len_actual - 1 <= n_ratio; l++) {
int r = l + len_actual - 1;
int current_sa = prefSumaA[r] - prefSumaA[l - 1];
int current_sb = prefSumaB[r] - prefSumaB[l - 1];
ParSumas current_pair = {current_sa, current_sb};
if (len_offset == 0) { // Longitud k
dpSubsegmentosCercanos[len_offset][l] = current_pair;
} else {
// Combina el resultado actual con los de longitudes anteriores
// y los de subsegmentos adyacentes de la misma longitud.
// Esta es una versión simplificada, la completa sería más compleja
// para cubrir todas las combinaciones que la propiedad implica.
// Para este problema, la solución de dp[len_offset][l] representa el mejor
// subsegmento de longitud k a 2k-1 que *termina* en l+len_actual-1
// o *comienza* en l. La interpretación es crucial.
dpSubsegmentosCercanos[len_offset][l] = compararFracciones(
dpSubsegmentosCercanos[len_offset][l], current_pair);
// Si queremos que cada dp[len][l] contenga el mejor resultado
// para un subsegmento de longitud len *que empieza en l*,
// no necesitamos combinar con dp[len-1][l+1].
// La solución original parece construir f[0][i] directamente de todos los
// subsegmentos válidos [i, j] con k <= j-i+1 < 2k.
}
}
}
// Rellenar la primera capa de la tabla escasa (j=0, rangos de longitud 1)
// Cada f[0][i] debe contener el mejor subsegmento de longitud [k, 2k-1] que COMIENZA en i.
for (int i = 1; i <= n_ratio - k_ratio + 1; i++) { // Posibles inicios de subsegmentos válidos
for (int j = i + k_ratio - 1; j < min(i + 2 * k_ratio - 1, n_ratio + 1); j++) { // Posibles finales
ParSumas actual_res = {
(int)(prefSumaA[j] - prefSumaA[i - 1]),
(int)(prefSumaB[j] - prefSumaB[i - 1])
};
tablaEscasa[0][i] = compararFracciones(tablaEscasa[0][i], actual_res);
}
}
// Aquí el dpSubsegmentosCercanos es usado de manera diferente a la primera parte de precomputo.
// La implementación original del DP es más una "pre-consolidación" para la parte final de la consulta.
// Para simplificar la explicación, se puede pensar en llenar f[0][i] con los óptimos
// para subsegmentos de longitud [k, 2k-1] que comienzan en i.
// Esto se hizo en el bucle anterior. La "DP" del problema original se refiere a cómo
// se fusionan los resultados para consultar eficientemente.
// Inicializar la tabla escasa con estos valores base.
inicializarTablaEscasa();
int ultimaRespuestaNum = 0;
while (q_ratio--) {
int l_raw, r_raw;
cin >> l_raw >> r_raw;
int l = (l_raw ^ (ultimaRespuestaNum * type_ratio)) % n_ratio + 1;
int r = (r_raw ^ (ultimaRespuestaNum * type_ratio)) % n_ratio + 1;
if (l > r) swap(l, r);
if (r - l + 1 < k_ratio) {
cout << "0/1\n";
ultimaRespuestaNum = 0;
continue;
}
ParSumas respuestaConsulta = {0, 0};
// La parte principal de la tabla escasa: para subsegmentos que comienzan en [l, R - 2k + 1]
// y tienen longitud >= k.
// limit: el último índice donde un subsegmento de longitud >= k puede comenzar,
// sin que su final exceda R, y manteniendo su inicio lo suficientemente a la izquierda
// para ser manejado por la ST que cubre longitudes completas.
int limite_idx_ST = r - (2 * k_ratio - 1); // Subsegmentos que terminan en r, pero comienzan antes de este punto
// y tienen longitud al menos 2k-1.
// Mejor dicho, para que el subsegmento [i, j] tenga longitud al menos k
// y j <= r, y i <= r - k + 1.
// Y la parte "corta" es para subsegmentos que *empiezan* en [r - 2k + 2, r - k + 1].
// La limitación del problema dice que los intervalos óptimos tienen longitud <= 2k.
// Entonces, podemos consultar el rango [l, r - k + 1] usando la ST para obtener
// el mejor subsegmento de longitud entre k y 2k-1.
// La limitación r - 2k + 1 significa: si un subintervalo óptimo tiene longitud 2k-1,
// y empieza en l', entonces l' + (2k-1) - 1 <= r => l' <= r - 2k + 2.
// Así que, los puntos de inicio l' para los cuales el intervalo [l', r']
// *potencialmente* excede la longitud 2k, o para los cuales
// la tabla escasa no tiene el mejor óptimo para un subsegmento corto,
// se manejan por separado.
// Consideramos subsegmentos que empiezan en [l, r - k_ratio + 1]
// y cuya longitud total es a lo sumo 2k-1.
// La tabla escasa 'tablaEscasa[0][i]' ya precalcula esto para un inicio 'i'.
// Entonces, podemos usar la consulta de tabla escasa para todo el rango [l, r - k_ratio + 1].
// El enunciado de la solución original no es muy claro en su código sobre cómo
// se combinan los dp y f. El 'dp' array no se usa directamente en la consulta principal.
// La tablaEscasa[0][i] parece estar precalculando el mejor subsegmento de longitud [k, 2k-1] que empieza en i.
// Esto simplifica la consulta.
respuestaConsulta = consultarMaxFraccion(l, r - k_ratio + 1);
ll comunDivisor = maximoComunDivisor(respuestaConsulta.SUM_A, respuestaConsulta.SUM_B);
if (comunDivisor == 0) { // Si el numerador es 0, no hay respuesta válida (o 0/1)
cout << "0/1\n";
ultimaRespuestaNum = 0;
} else {
cout << respuestaConsulta.SUM_A / comunDivisor << "/" << respuestaConsulta.SUM_B / comunDivisor << "\n";
ultimaRespuestaNum = respuestaConsulta.SUM_A / comunDivisor;
}
}
return 0;
}
Problema 4: Alineación Planetaria
Descripción del Problema: Un astrónomo observa (n) planetas que orbitan una estrella. Los planetas están numerados del 1 al (n) según su distancia a la estrella. Cada planeta (i) tiene un período orbital (a_i) unidades de tiempo, y todos los (a_i) son distintos. Actualmente, la estrella y los (n) planetas están alineados (todos en la misma línea recta). Se pregunta cuándo ocurrirá la próxima alineación similar. La respuesta debe darse módulo (998244353), y si es una fracción (p/q), se debe reportar (t) tal que (t \times q \equiv p \pmod{998244353}).
Análisis y Estrategia: El problema de la alineación planetaria se reduce a encontrar el Mínimo Común Múltiplo (MCM) de las mitades de los períodos de cada planeta. Si un planeta tiene un período (T_i), su posición en un tiempo (t) es (t/T_i \times 2\pi) (módulo (2\pi)). Para que los planetas y la estrella estén en línea, la posición angular de cada planeta debe ser un múltiplo entero de (\pi). Esto significa que (t/T_i \times 2\pi = k_i \times \pi) para algún entero (k_i), lo que implica (2t/T_i = k_i). Es decir, (t) debe ser un múltiplo de (T_i/2). Dado que todos los planetas ya están alineados en el tiempo (t=0), la próxima vez que se alineen será el MCM de todos los (T_i/2), lo que es equivalente a (\frac{\text{MCM}(T_1, T_2, \dots, T_n)}{2}).
El desafío principal radica en que los períodos (a_i) pueden ser muy grandes (hasta (10^{18})), lo que significa que el MCM puede exceder significativamente el rango de los tipos de datos estándar (como long long). Sin embargo, se nos pide el resultado módulo (998244353). La clave aquí es calcular el MCM de manera modular, pero ¡cuidado!, no se puede simplemente tomar el MCM y luego el módulo.
Cálculo Modular del MCM: La relación para el MCM de dos números es (\text{MCM}(X, Y) = \frac{X \times Y}{\text{MCD}(X, Y)}). Para calcular (\text{MCM}(a_1, \dots, a_n)) iterativamente, podemos usar la fórmula: (\text{MCM}(a_1, \dots, a_i) = \text{MCM}(\text{MCM}(a_1, \dots, a_{i-1}), a_i)). Para evitar overflows con grandes números, podemos reescribir la actualización como: (L_i = L_{i-1} \times \left( \frac{a_i}{\text{MCD}(L_{i-1}, a_i)} \right)), donde (L_i = \text{MCM}(a_1, \dots, a_i)). La crucial propiedad del Máximo Común Divisor (MCD) es que (\text{MCD}(X, Y) = \text{MCD}(X \pmod Y, Y)). Esto nos permite calcular (\text{MCD}(L_{i-1}, a_i)) sin necesidad de tener el valor completo de (L_{i-1}). Podemos mantener (L_{i-1}) como un producto de factores y calcularlo módulo (a_i) para la función MCD.
Pasos para la solución:
- Inicializar un
MCM\_actuala 1. - Iterar a través de cada período \(a_i\): - Para calcular \\(\\text{MCM}(\\text{MCM\\\_actual}, a\_i)\\), necesitamos \\(\\text{MCD}(\\text{MCM\\\_actual}, a\_i)\\). - El truco es que \\(\\text{MCM\\\_actual}\\) se puede representar como un producto de factores \\(b\_j\\), donde \\(b\_j\\) es \\(a\_j / \\text{MCD}(\\text{MCM}(a\_1, \\dots, a\_{j-1}), a\_j)\\). - Calcularemos
mcm\\\_previo\\\_mod\\\_ai = (producto de b\\\_j anteriores) % a\\\_i. - Luego, \\(\\text{MCD}(\\text{MCM\\\_actual}, a\_i) = \\text{MCD}(\\text{mcm\\\_previo\\\_mod\\\_ai}, a\_i)\\). - El nuevo factor a añadir al producto es \\(a\_i / \\text{MCD}(\\text{mcm\\\_previo\\\_mod\\\_ai}, a\_i)\\). - El producto final de estos factores \(b_j\) nos dará el MCM total. Este producto se calculará módulo \(998244353\) en cada paso para evitar overflows intermedios y obtener el resultado final modular.
- Finalmente, dividir el resultado del MCM por 2 (que es equivalente a multiplicar por el inverso modular de 2). Se necesitará el tipo de dato
__int128para las multiplicaciones intermedias en el cálculo del MCD y el producto de los factores (b_j), ya que (a_i) pueden ser (10^{18}) y sus productos pueden excederunsigned long longantes de aplicar el módulo.
Implementación:
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
typedef unsigned long long ull;
const int MAX_PLANETAS = 5010;
const int MODULO_PLANETAS = 998244353;
const ull INVERSO_DOS = (MODULO_PLANETAS + 1) / 2; // Inverso modular de 2 para (P+1)/2
int numPlanetas;
ull factoresLCM[MAX_PLANETAS]; // factoresLCM[i] = a_i / MCD(MCM(a_1...a_{i-1}), a_i)
// Función para calcular el Máximo Común Divisor (MCD)
inline ull calcularGCD(ull a, ull b) {
while (b) {
a %= b;
swap(a, b);
}
return a;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> numPlanetas;
ull periodoActual;
for (int i = 1; i <= numPlanetas; i++) {
cin >> periodoActual;
ull mcmPrevioMod = 1; // Representa MCM(a_1...a_{i-1}) % periodoActual
for (int j = 1; j < i; j++) {
// Multiplicamos por factoresLCM[j] y tomamos el módulo
// Esto es crucial para mantener mcmPrevioMod bajo control y evitar overflow
mcmPrevioMod = (__int128)mcmPrevioMod * factoresLCM[j] % periodoActual;
}
// Calculamos el factor que necesitamos para el MCM
factoresLCM[i] = periodoActual / calcularGCD(mcmPrevioMod, periodoActual);
}
ull resultadoLCM = 1;
for (int i = 1; i <= numPlanetas; i++) {
// Multiplicamos los factoresLCM para obtener el MCM total, tomando módulo
resultadoLCM = (__int128)resultadoLCM * factoresLCM[i] % MODULO_PLANETAS;
}
// Dividimos el MCM por 2, multiplicando por su inverso modular
cout << (resultadoLCM * INVERSO_DOS) % MODULO_PLANETAS << endl;
return 0;
}