Problema 1: Minería de oro
Este problema requiere encontrar pares de números dentro de un rango dado donde ambos números tienen factores primos solo de 2, 3, 5 y 7. La solución implica precalcular estados válidos usando DP en dígitos y luego combinar resultados bidimensionales. Se observa que los exponentes de estos factores primos son limitados, permitiendo una enumeración eficiente.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
int contador[4][10] = {{0}}; // Almacena exponentes de 2,3,5,7 para dígitos 0-9
ll buscar(int posicion, bool limite, int exp1, int exp2, int exp3, int exp4, bool iniciado, const vector<int>& digitos, vector<vector>>>>>>>& memo) {
if (exp1 < 0 || exp2 < 0 || exp3 < 0 || exp4 < 0) return 0;
if (posicion == 0) return (exp1 == 0 && exp2 == 0 && exp3 == 0 && exp4 == 0 && iniciado) ? 1 : 0;
if (!limite && memo[posicion][exp1][exp2][exp3][exp4][iniciado] != -1)
return memo[posicion][exp1][exp2][exp3][exp4][iniciado];
int maximo = limite ? digitos[posicion] : 9;
ll total = 0;
for (int digito = 0; digito <= maximo; ++digito) {
if (!iniciado && digito == 0) {
total += buscar(posicion - 1, limite && digito == maximo, exp1, exp2, exp3, exp4, false, digitos, memo);
} else {
total += buscar(posicion - 1, limite && digito == maximo, exp1 - contador[0][digito], exp2 - contador[1][digito], exp3 - contador[2][digito], exp4 - contador[3][digito], true, digitos, memo);
}
}
if (!limite) memo[posicion][exp1][exp2][exp3][exp4][iniciado] = total;
return total;
}
vector<int> obtenerDigitos(ll num) {
vector<int> digitos;
while (num > 0) {
digitos.push_back(num % 10);
num /= 10;
}
return digitos;
}
int main() {
// Inicializar contador para dígitos
contador[0][2] = 1; contador[0][4] = 2; contador[0][6] = 1; contador[0][8] = 3;
contador[1][3] = 1; contador[1][6] = 1; contador[1][9] = 2;
contador[2][5] = 1;
contador[3][7] = 1;
ll n;
int k;
cin >> n >> k;
vector<int> digitos = obtenerDigitos(n);
int longitud = digitos.size();
// DP en 7 dimensiones: posición, exp1, exp2, exp3, exp4, limite, iniciado
vector<vector>>>>>> memo(
longitud + 1, vector<vector>>>>>(
42, vector<vector>>>>>(
30, vector<vector>>>>(
20, vector<vector>>>(
15, vector<vector>>(2, vector<ll>(2, -1))
)
)
)
)
);
map<ll int=""> frecuencia;
for (int e1 = 0; e1 <= 40; ++e1) {
for (int e2 = 0; e2 < 30; ++e2) {
for (int e3 = 0; e3 < 20; ++e3) {
for (int e4 = 0; e4 < 15; ++e4) {
ll conteo = buscar(longitud, true, e1, e2, e3, e4, false, digitos, memo);
if (conteo > 0) frecuencia[conteo]++;
}
}
}
}
// Encontrar pares con máxima suma
priority_queue<pair ll="">> cola;
for (auto& par : frecuencia) {
cola.push({par.first * frecuencia.rbegin()->first, par.first});
}
ll suma = 0;
while (!cola.empty() && k > 0) {
ll valor = cola.top().first;
ll base = cola.top().second;
cola.pop();
ll pares = min((ll)k, frecuencia[base] * frecuencia[frecuencia.rbegin()->first]);
suma = (suma + valor % MOD * pares % MOD) % MOD;
k -= pares;
if (k > 0 && frecuencia.find(base) != frecuencia.end()) {
// Actualizar para siguiente valor menor
auto it = frecuencia.find(base);
if (it != frecuencia.begin()) {
--it;
cola.push({base * it->first, base});
}
}
}
cout << suma << endl;
return 0;
}
</pair></ll></ll></vector></vector></vector></vector></vector></vector></int></int></int></vector></int></queue></vector></iostream>
Problema 2: Conteo de números
Este problema implica contar la suma de todos los subconjuntos de dígitos dentro de un rango. La solución utiliza DP en dígitos para calcular contribuciones basadas en prefijos y sufijos, manejando restricciones de límite y carry.
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 20130427;
int calcularSolucion(int base, const vector<int>& limite) {
int longitud = limite.size();
vector<int> num(longitud + 1, 0), len0(longitud + 1, 0), len1(longitud + 1, 0);
vector<int> now0(longitud + 1, 0), now1(longitud + 1, 0), dp0(longitud + 1, 0), dp1(longitud + 1, 0);
for (int i = 1; i <= longitud; ++i) {
int anterior = (i > 1) ? base - 1 : 0;
num[i] = (1LL * num[i-1] * base % MOD + limite[i-1] + anterior) % MOD;
len0[i] = (len0[i-1] + 1) % MOD;
len1[i] = (1LL * len0[i] * limite[i-1] % MOD + (1LL * num[i-1] + len1[i-1]) * base % MOD + anterior) % MOD;
now0[i] = (1LL * now0[i-1] * base % MOD + 1LL * len0[i] * limite[i-1] % MOD) % MOD;
now1[i] = (1LL * anterior * (anterior + 1) / 2 % MOD + 1LL * now0[i-1] * base % MOD * limite[i-1] % MOD + 1LL * len0[i] * (limite[i-1] * (limite[i-1] - 1) / 2 % MOD)) % MOD;
now1[i] = (now1[i] + (1LL * now1[i-1] * base % MOD * base % MOD + (1LL * len1[i-1] + num[i-1]) * ((base - 1) * base / 2 % MOD)) % MOD) % MOD;
dp0[i] = (dp0[i-1] + now0[i]) % MOD;
dp1[i] = (1LL * dp0[i-1] * limite[i-1] % MOD + 1LL * dp1[i-1] * base % MOD + now1[i]) % MOD;
}
return (dp0[longitud] + dp1[longitud]) % MOD;
}
int main() {
int base, longitudInferior, longitudSuperior;
cin >> base;
cin >> longitudInferior;
vector<int> inferior(longitudInferior);
for (int i = 0; i < longitudInferior; ++i) cin >> inferior[i];
cin >> longitudSuperior;
vector<int> superior(longitudSuperior);
for (int i = 0; i < longitudSuperior; ++i) cin >> superior[i];
// Ajustar inferior a l-1
int borrow = 1;
for (int i = longitudInferior - 1; i >= 0; --i) {
inferior[i] -= borrow;
if (inferior[i] < 0) {
inferior[i] += base;
borrow = 1;
} else {
borrow = 0;
}
}
int resultado = (calcularSolucion(base, superior) - calcularSolucion(base, inferior) + MOD) % MOD;
cout << resultado << endl;
return 0;
}
</int></int></int></int></int></vector></iostream>
Problema 3: Números hermosos
Este problema busca números donde el número formado por los dígitos es divisible por cada uno de sus dígitos no nulos. Se utiliza DP en dígitos con módulo 2520 (mcm de 1-9) y bitmask para rastrear divisores.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
const int MCM = 2520;
int mapa[MCM + 1];
ll memo[20][MCM][50];
ll buscar(int posicion, int residuo, int divisorActual, bool limite, const vector<int>& digitos) {
if (posicion == 0) return (residuo % divisorActual == 0) ? 1 : 0;
if (!limite && memo[posicion][residuo][mapa[divisorActual]] != -1)
return memo[posicion][residuo][mapa[divisorActual]];
int maximo = limite ? digitos[posicion] : 9;
ll total = 0;
for (int digito = 0; digito <= maximo; ++digito) {
int nuevoDivisor = (digito == 0) ? divisorActual : mcm(divisorActual, digito);
total += buscar(posicion - 1, (residuo * 10 + digito) % MCM, nuevoDivisor, limite && (digito == maximo), digitos);
}
if (!limite) memo[posicion][residuo][mapa[divisorActual]] = total;
return total;
}
ll resolver(ll limite) {
vector<int> digitos = {0}; // Posición 0 dummy
ll temp = limite;
while (temp > 0) {
digitos.push_back(temp % 10);
temp /= 10;
}
return buscar(digitos.size() - 1, 0, 1, true, digitos);
}
int main() {
// Mapear divisores a índices para memoización
int indice = 0;
for (int i = 1; i <= MCM; ++i) if (MCM % i == 0) mapa[i] = ++indice;
memset(memo, -1, sizeof(memo));
int consultas;
cin >> consultas;
while (consultas--) {
ll l, r;
cin >> l >> r;
cout << resolver(r) - resolver(l - 1) << endl;
}
return 0;
}
</int></int></cstring></vector></iostream>
Porblema 4: Caminos en árbol binario
Este problema involucra contar caminos en un árbol binario con pesos definidos por los nodos. La solución descompone el problema en casos de cadena y bifurcación, utilizando DP sobre bits para manejar sumas de potencias de dos.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
ll contarCaminos(ll valorObjetivo, int longitudIzquierda, int longitudDerecha, int totalUnos) {
int maxBits = 64;
vector<vector>>> dp(maxBits + 1, vector<vector>>(2 * maxBits + 1, vector<ll>(2, 0)));
dp[0][0][0] = 1;
for (int bit = 0; bit < maxBits; ++bit) {
for (int unos = 0; unos <= 2 * bit; ++unos) {
for (int carry = 0; carry < 2; ++carry) {
if (dp[bit][unos][carry] == 0) continue;
for (int izq = 0; izq < 2; ++izq) {
if (izq && bit >= longitudIzquierda) continue;
for (int der = 0; der < 2; ++der) {
if (der && bit >= longitudDerecha) continue;
int suma = carry + izq + der;
if ((suma & 1) == ((valorObjetivo >> bit) & 1)) {
dp[bit + 1][unos + izq + der][suma >> 1] += dp[bit][unos][carry];
}
}
}
}
}
}
return dp[maxBits][totalUnos][0];
}
int main() {
ll n;
cin >> n;
ll total = 0;
// Casos de cadena única
for (int profundidad = 1; (1LL << profundidad) <= n; ++profundidad) {
ll base = (1LL << profundidad) - 1;
ll coeficiente = n / base;
if (coeficiente == 0) continue;
ll residuo = n - coeficiente * base;
// Verificar si residuo puede descomponerse en potencias de dos menores
ll temp = residuo;
bool valido = true;
for (int i = profundidad - 1; i >= 0 && temp > 0; --i) {
ll potencia = (1LL << i) - 1;
if (temp >= potencia) temp -= potencia;
}
if (temp == 0) total++;
}
// Casos con bifurcación
for (int izquierda = 1; (1LL << izquierda) <= n; ++izquierda) {
for (int derecha = 1; (1LL << derecha) <= n; ++derecha) {
ll denominador = (1LL << (izquierda + 1)) + (1LL << (derecha + 1)) - 3;
ll baseDerecha = (1LL << derecha) - 1;
ll coeficiente = (n - baseDerecha) / denominador;
if (coeficiente <= 0) continue;
ll residuo = (n - baseDerecha) - coeficiente * denominador;
if (residuo == 0) {
total++;
continue;
}
for (int unos = 1; unos <= izquierda + derecha; ++unos) {
if ((residuo + unos) % 2 == 0) {
total += contarCaminos(residuo + unos, izquierda, derecha, unos);
}
}
}
}
cout << total << endl;
return 0;
}
</ll></vector></vector></cstring></vector></iostream>
Problema 5: Viaje al centro comercial
Este problema busca la suma de costos para visitar tiendas en un rango, donde el costo depende de la posición en una representación base k. Se usa DP en dígitos con optimización por posición del punto de inflexión.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
ll memo[105][10005];
int digitos[100];
int base;
ll buscar(int posicion, int sumaActual, int puntoInflexion, bool limite) {
if (posicion == 0) return max(sumaActual, 0LL);
if (!limite && memo[posicion][sumaActual] != -1) return memo[posicion][sumaActual];
int maximo = limite ? digitos[posicion] : base - 1;
ll total = 0;
for (int digito = 0; digito <= maximo; ++digito) {
int contribucion = (puntoInflexion == 1) ? digito * (posicion - 1) : (posicion < puntoInflexion ? -digito : digito);
total += buscar(posicion - 1, sumaActual + contribucion, puntoInflexion, limite && (digito == maximo));
}
if (!limite) memo[posicion][sumaActual] = total;
return total;
}
ll resolver(ll limite) {
int longitud = 0;
ll temp = limite;
while (temp > 0) {
digitos[++longitud] = temp % base;
temp /= base;
}
ll suma = 0;
for (int inflexion = 1; inflexion <= longitud; ++inflexion) {
memset(memo, -1, sizeof(memo));
ll contribucion = buscar(longitud, 0, inflexion, true);
suma += (inflexion == 1 ? 1 : -1) * contribucion;
}
return suma;
}
int main() {
ll l, r;
cin >> l >> r >> base;
cout << resolver(r) - resolver(l - 1) << endl;
return 0;
}
</cstring></vector></iostream>