Análisis de Secuencias con Relación de Divisibilidad

Dado un entero N y un límite superior M, se solicita determinar cuántas sucesiones de longitud N cumplen que cada término A[i] está acotado por M y A[i+1] es múltiplo exacto de A[i].

Desarrollo del enfoque:

Dado que cada elemento divide al siguiente, la secuencia es inherentemente no decreciente. Una estrategia eficiente consiste en fijar el valor del último elemento A[N]. Si seleccionamos un valor v para la posición final, todos los elementos previos deben ser divisores de v. Al descomponer v en sus factores primos p_i^{e_i}, la construcción de la secuencia equivale a distribuir los exponentes e_i a lo largo de las N posiciones. Dado que los factores son independientes, el número de formas para un primo con exponente e corresponde a combianr N-1 separadores con e unidades, calculado como C(N + e - 1, N - 1). El resultado total para un valor fijo es el producto de estas combinaciones para cada factor primo. Sumando sobre todos los posibles valores finales entre 1 y M obtenemos la respuesta global.

#include <iostream>
using namespace std;

using ll = long long;
const int MAX_VAL = 400005;
const ll MOD = 998244353;

ll fact_tabla[MAX_VAL], inv_fact_tabla[MAX_VAL];

ll calculo_potencia(ll base, ll exp) {
    ll res = 1;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

void precalcular_combinatoria() {
    fact_tabla[0] = inv_fact_tabla[0] = 1;
    for (int i = 1; i < MAX_VAL; i++) {
        fact_tabla[i] = (fact_tabla[i - 1] * i) % MOD;
    }
    inv_fact_tabla[MAX_VAL - 1] = calculo_potencia(fact_tabla[MAX_VAL - 1], MOD - 2);
    for (int i = MAX_VAL - 2; i >= 1; i--) {
        inv_fact_tabla[i] = (inv_fact_tabla[i + 1] * (i + 1)) % MOD;
    }
}

ll nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact_tabla[n] * inv_fact_tabla[r] % MOD * inv_fact_tabla[n - r] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precalcular_combinatoria();

    int n, m;
    cin >> n >> m;

    ll total = 0;
    for (int candidato = 1; candidato <= m; candidato++) {
        int temp = candidato;
        ll formas_actual = 1;
        for (int p = 2; p * p <= temp; p++) {
            if (temp % p == 0) {
                int exponente = 0;
                while (temp % p == 0) {
                    temp /= p;
                    exponente++;
                }
                formas_actual = formas_actual * nCr(n + exponente - 1, n - 1) % MOD;
            }
        }
        if (temp > 1) {
            formas_actual = formas_actual * nCr(n, n - 1) % MOD;
        }
        total = (total + formas_actual) % MOD;
    }
    cout << total << "\n";
    return 0;
}

Conteo bajo Restricciones de Suma y Operación XOR

Determinar la cantidad de arreglos de longitud N con elementos no negativos que sumen exactamente M y cuya operación XOR acumulada sea estrictamente cero.

Desarrollo del enfoque:

La condición Σ A[i] = M junto con ⊕ A[i] = 0 sugiere un análisis bit a bit. Para que el XOR total sea nulo, cada posición binaria debe contener una cantidad par de unos. Si en el bit b (valor 2^b) seleccionamos 2k posiciones para colocar un uno, esto contribuye 2k * 2^b a la suma total. Esto modela un problema de mochila por grupos: para cada nivel de bit, podemos elegir incluir 2, 4, 6, ... unos. Definimos dp[s] como las formas de alcanzar la suma parcial s. Al procesar cada bit b y cada cantidad posible de unos 2k, actualizamos la tabla dinámica en orden decreciente para evitar reutilizaciones dentro del mismo nivel. El factor combinatorio C(N, 2k) representa las formas de elegir las posiciones dentro del arreglo. La respuesta final reside en dp[M].

#include <iostream>
using namespace std;

using ll = long long;
const int MAX_VAL = 5005;
const ll MOD = 998244353;

ll fact_arr[MAX_VAL], inv_fact_arr[MAX_VAL];
ll dp_suma[MAX_VAL];

ll potencia_mod(ll base, ll exp) {
    ll res = 1;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

void setup_fact(int n) {
    fact_arr[0] = inv_fact_arr[0] = 1;
    for(int i=1; i<=n; i++) fact_arr[i] = fact_arr[i-1]*i%MOD;
    inv_fact_arr[n] = potencia_mod(fact_arr[n], MOD-2);
    for(int i=n-1; i>=1; i--) inv_fact_arr[i] = inv_fact_arr[i+1]*(i+1)%MOD;
}

ll binom(int n, int k) {
    if(k<0||k>n) return 0;
    return fact_arr[n]*inv_fact_arr[k]%MOD*inv_fact_arr[n-k]%MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    setup_fact(n);

    dp_suma[0] = 1;
    for (int bit = 0; (1 << bit) <= m; bit++) {
        ll valor_bit = (1LL << bit);
        for (int s = m; s >= 0; s--) {
            for (int k = 1; 2LL * k * valor_bit <= s; k++) {
                ll coste = 2LL * k * valor_bit;
                ll formas_elegir = binom(n, 2 * k);
                dp_suma[s] = (dp_suma[s] + dp_suma[s - coste] * formas_elegir) % MOD;
            }
        }
    }
    cout << dp_suma[m] << "\n";
    return 0;
}

Minimización del Tiempo de Propagación en Estructuras en Árbol

Se proporciona un grafo acíclico conectado con N vértices. Es posible iniciar K focos de infección que se expanden a una velocidad de un nodo por unidad de tiempo. El objetivo es hallar el menor tiempo necesario para cubrir toda la estructura.

Desarrollo del enfoque:

La función que relaciona el tiempo disponible con la cantidad de focos necesarios es monótona, lo que permite aplicar búsqueda binaria sobre el tiempo T. Para un valor fijo de T, evaluamos la viabilidad mediante una recorrida post-orden. Mantenemos dos valores por nodo: la distancia al foco más cercano en su subárbol, y la distancia al nodo más lejano que aún no ha sido alcanzado por la propagación. Si la suma de ambas distancias es menor o igual a T, la subestructura queda cubierta. Cuando la distancia al nodo no cubierto alcanza exactamente T, es obligatorio colocar un nuevo foco en el nodo actual para evitar que se exceda el límite temporal. Tras procesar todo el árbol, si el nodo raíz aún tiene nodos pendientes de cobertura, se incrementa el contador de focos. El algoritmo busca el menor T donde el contador no supere K.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 200005;
const int LIM = 1e9;

vector<int> vecinos[MAX_N];
int dist_fuente[MAX_N];
int dist_no_cubierto[MAX_N];
int focos_necesarios;
int n_nodos, k_focos;

void analizar_subarbol(int u, int padre, int limite_tiempo) {
    dist_fuente[u] = LIM;
    dist_no_cubierto[u] = 0;

    for (int v : vecinos[u]) {
        if (v == padre) continue;
        analizar_subarbol(v, u, limite_tiempo);
        dist_fuente[u] = min(dist_fuente[u], dist_fuente[v] + 1);
        dist_no_cubierto[u] = max(dist_no_cubierto[u], dist_no_cubierto[v] + 1);
    }

    if (dist_fuente[u] + dist_no_cubierto[u] <= limite_tiempo) {
        dist_no_cubierto[u] = -LIM; // Subárbol completamente cubierto
    } else if (dist_no_cubierto[u] == limite_tiempo) {
        // Obligatorio colocar foco aquí para evitar desbordamiento
        dist_fuente[u] = 0;
        dist_no_cubierto[u] = -LIM;
        focos_necesarios++;
    }
}

bool es_viable(int tiempo) {
    focos_necesarios = 0;
    analizar_subarbol(1, -1, tiempo);
    // Si el nodo raíz tiene pendientes, se requiere un foco adicional
    if (dist_no_cubierto[1] >= 0) focos_necesarios++;
    return focos_necesarios <= k_focos;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n_nodos >> k_focos;
    for (int i = 0; i < n_nodos - 1; i++) {
        int u, v;
        cin >> u >> v;
        vecinos[u].push_back(v);
        vecinos[v].push_back(u);
    }

    int izq = 0, der = n_nodos;
    while (izq < der) {
        int mid = (izq + der) / 2;
        if (es_viable(mid)) {
            der = mid;
        } else {
            izq = mid + 1;
        }
    }
    cout << izq << "\n";
    return 0;
}