A - Aritmética básica 2

Dados \(N\) y \(M\) con \(N \leq 10^{18}\) y \(M \leq 10^4\), calcular \(\lfloer 10^N / M \rfloor\).

Enfoque óptimo: Al expandir \((am + b) \times (cm + d) \bmod m\), se observa que el término \(am^2\) no contribuye tras dividir por \(m\) y aplicar módulo \(m\), ya que da cero. Esto permite ejecutar exponenciación rápida directamente con módulo \(m^2\).

# Solución en Python
n, m = map(int, input().split())
resultado = pow(10, n, m * m) // m % m
print(resultado)

Enfoque alternativo por duplicación: Se puede modelar el problema manteniendo la parte entera (módulo \(m\)) y el residuo de \(10^{2^i} \bmod m\) para cada potencia de dos. Luego, descomponiendo \(N\) en binario, se combinan las contribuciones.

# Solución en C++ usando duplicación
#include <cstdio>
using ll = long long;

int main() {
    ll n, m;
    scanf("%lld %lld", &n, &m);
    ll ent[70], res[70];
    ent[0] = 10 / m;
    res[0] = 10 % m;
    for (ll i = 1; (1ll << i) <= n; i++) {
        ent[i] = (2ll * ent[i-1] * res[i-1] + res[i-1] * res[i-1] / m) % m;
        res[i] = (res[i-1] * res[i-1]) % m;
    }
    ll acum_ent = 0, acum_res = 0;
    for (ll i = 0; (1ll << i) <= n; i++) {
        if (n & (1ll << i)) {
            if (acum_ent == 0 && acum_res == 0) {
                acum_ent = ent[i];
                acum_res = res[i];
            } else {
                acum_ent = (acum_ent * res[i] + acum_res * ent[i]) % m;
                acum_ent = (acum_ent + acum_res * res[i] / m) % m;
                acum_res = (acum_res * res[i]) % m;
            }
        }
    }
    printf("%lld\n", acum_ent % m);
    return 0;
}

B - Tarjetas reversibles

Se tienen \(n\) tarjetas, cada una con un número en cada cara. Se pueden voltear libremente. El objetivo es maximizar la cantidad de valores distintos visibles en la parte superior.

Modelado como grafo: Cada valor numérico es un nodo y cada tarjeta conecta los dos valores en sus caras mediante una arista. El problema se reduce a: seleccionar un extremo de cada arista para maximizar nodos seleccionados.

Para cada componnete conexa, la contribución es \(\min(\text{aristas}, \text{nodos})\). Se puede usar Union-Find para identificar componentes.

# Solución en C++ con Union-Find
#include <cstdio>
#include <algorithm>
using namespace std;

const int LIM = 400010;
int padre[LIM], cnt_aristas[LIM], cnt_nodos[LIM];
bool usado[LIM];

int buscar(int v) {
    return (v == padre[v]) ? v : padre[v] = buscar(padre[v]);
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < LIM; i++) padre[i] = i;
    int u, v;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &u, &v);
        int ru = buscar(u), rv = buscar(v);
        if (ru != rv) padre[ru] = rv;
        usado[u] = usado[v] = true;
    }
    for (int i = 0; i < LIM; i++) {
        int raiz = buscar(i);
        cnt_nodos[raiz]++;
    }
    for (int i = 0; i < n; i++) {
        // reconstruir las aristas para contar
    }
    // Recalcular aristas por componente
    // Nota simplificada: se requiere re-leer o almacenar las aristas
    int respuesta = 0;
    for (int i = 0; i < LIM; i++)
        if (usado[i] && buscar(i) == i)
            respuesta += min(cnt_aristas[i], cnt_nodos[i]);
    printf("%d\n", respuesta);
    return 0;
}

C - Demasiado pesado

Hay \(n\) personas y \(n\) paquetes etiquetados. Cada persona y cada paquete tienen un peso. Solo se permite intercambiar paquetes entre dos personas. El objetivo es que la persona \(i\) termine con el paquete \(i\). Restricción: si el paquete es más pesado que la persona, no se puede intercambiar.

Análisis: Si al inicio algún paquete ya asignado incorrectamente no es más ligero que su portador, no hay solución. Formando ciclos en la permutación de asignación, el número mínimo de intercambios es \(n - C\) donde \(C\) es el número de ciclos.

Para cada ciclo, se elige la persona más ligera como punto de intercambio. Procesando en orden ascendente de peso, se logra el óptimo.

# Solución en C++
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
using pii = pair<int,int>;

const int MAX = 200010;
int peso_persona[MAX], peso_paquete[MAX], perm[MAX];
int ubicacion[MAX], etiquetas[MAX];
vector<pii> operaciones;

bool comparar(int x, int y) {
    return peso_persona[x] < peso_persona[y];
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &peso_persona[i]);
        etiquetas[i] = i;
    }
    for (int i = 1; i <= n; i++) scanf("%d", &peso_paquete[i]);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &perm[i]);
        ubicacion[perm[i]] = i;
    }
    for (int i = 1; i <= n; i++)
        if (peso_paquete[perm[i]] >= peso_persona[i] && perm[i] != i) {
            printf("-1\n");
            return 0;
        }
    sort(etiquetas + 1, etiquetas + n + 1, comparar);
    int total = 0;
    for (int i = 1; i <= n; i++) {
        int actual = etiquetas[i];
        if (perm[actual] != actual) {
            total++;
            operaciones.push_back({actual, ubicacion[actual]});
            int otro = ubicacion[actual];
            swap(perm[actual], perm[otro]);
            ubicacion[perm[otro]] = otro;
            ubicacion[perm[actual]] = actual;
        }
    }
    printf("%d\n", total);
    for (auto& op : operaciones)
        printf("%d %d\n", op.first, op.second);
    return 0;
}

D - Orientación

Dado un grafo no dirigido de \(n\) vértices y \(m\) aristas, donde cada vértice tiene una etiqueta \(c[i]\), asignar una dirección a cada arista tal que el vértice \(i\) pueda alcanzar exactamente \(c[i]\) vértices.

Estrategia: Para una arista \((u, v)\), si \(c[u] > c[v]\), la dirección debe ser \(v \to u\). Si \(c[u] < c[v]\), será \(u \to v\). Las aristas entre vértices con igual \(c\) se resuelven mediante DFS, garantizando consistencia.

# Solución en C++
#include <cstdio>
#include <cstring>

const int MAX_N = 110;
int n, m, c[MAX_N];
int adj[MAX_N][MAX_N];
int origen[MAX_N * MAX_N], destino[MAX_N * MAX_N], dir[MAX_N * MAX_N];
bool visitado[MAX_N];

void recorrer(int nodo) {
    visitado[nodo] = true;
    for (int vec = 1; vec <= n; vec++) {
        if (c[nodo] == c[vec] && adj[nodo][vec] != 0) {
            int idx = adj[nodo][vec];
            if (idx > 0) dir[idx] = 0;
            else dir[-idx] = 1;
            if (!visitado[vec]) recorrer(vec);
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    memset(adj, 0, sizeof(adj));
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &origen[i], &destino[i]);
        adj[origen[i]][destino[i]] = i;
        adj[destino[i]][origen[i]] = -i;
    }
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
    for (int i = 1; i <= m; i++) {
        if (c[origen[i]] < c[destino[i]]) dir[i] = 1;
        else if (c[origen[i]] > c[destino[i]]) dir[i] = 0;
    }
    memset(visitado, 0, sizeof(visitado));
    for (int i = 1; i <= n; i++)
        if (!visitado[i]) recorrer(i);
    for (int i = 1; i <= m; i++)
        printf("%s\n", dir[i] ? "->" : "<-");
    return 0;
}

E - Aritmética básica 3

Dados \(A, B, C, D\), contar los enteros positivos \(i\) tales que ningún valor en el rango \([A + Bi, A + Ci]\) es divisible por \(D\).

Caso trivial: Si \(C \cdot i - B \cdot i + 1 \geq D\), siempre existirá un múltiplo de \(D\) en el intervalo.

Sea \(n = \lfloor (D-2)/(C-B) \rfloor\). Para \(1 \leq i \leq n\), la condición de no divisibilidad se expresa como:

\[\lfloor (A + Bi - 1)/D \rfloor = \lfloor (A + Ci)/D \rfloor\] Esto se reduce a evaluar la suma de suelos usando la función floor_sum de la AtCoder Library.

# Solución en C++ usando floor_sum
#include <cstdio>
#include "atcoder/math"
using namespace atcoder;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        long long A, B, C, D;
        scanf("%lld %lld %lld %lld", &A, &B, &C, &D);
        long long n = (D - 2) / (C - B);
        long long res = n - floor_sum(n + 1, D, C, A) + floor_sum(n + 1, D, B, A - 1);
        printf("%lld\n", res);
    }
    return 0;
}

F - ¿Te gustan los problemas de consultas?

Se tienen tres tipos de operaciones sobre un arreglo de tamaño \(n\) inicializado en cero:

• Tipo 1: Asignar mínimo en rango
• Tipo 2: Asignar máximo en rango
• Tipo 3: Consulta de suma en rango

Para todas las \(\left(\frac{n(n+1)}{2}(2m+1)\right)^q\) secuencias posibles de \(q\) operaciones, calcular la suma total de la respuesta final módulo \(998244353\).

Enfoque por valor esperado: Sea \(P[i]\) la probabiliadd de que la posición \(i\) sea seleccionada en una operación dada. Definiendo \(p[j][v][1]\) como la probabilidad de que el valor en una posición sea \(\geq v\) tras \(j\) operaciones, se obtiene la recurrencia:

\[p[j+1][v][1] = p[j][v][1] \cdot \left(1 - \frac{m}{2m+1} \cdot P[i]\right) + P[i] \cdot \frac{m-v}{2m+1}\] La contribución esperada total por posición se computa sumando sobre todas las posiciones y operaciones. El resultado final se multiplica por el total de secuencias posibles.

# Solución en C++
#include <cstdio>
using ll = long long;

const int LIM = 400100;
const ll MOD = 998244353;
ll inverso[LIM];

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

int main() {
    inverso[1] = 1;
    for (int i = 2; i < LIM; i++)
        inverso[i] = (MOD - MOD / i) * inverso[MOD % i] % MOD;

    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);

    ll factor_total = elevar_potencia(
        (ll)n * (n + 1) / 2 % MOD * (2LL * m % MOD + 1) % MOD, q
    );
    factor_total = factor_total * inverso[2 * m + 1] % MOD;

    ll suma_b = 0;
    for (int v = 1; v < m; v++)
        suma_b = (suma_b + (m - v) % MOD * inverso[2 * m + 1]) % MOD;

    ll esperanza = 0;
    for (int i = 1; i <= n; i++) {
        ll prob = 2LL * i % MOD * (n - i + 1) % MOD * inverso[n] % MOD
                  * inverso[n + 1] % MOD;
        ll coef_a = (1 - m * inverso[2 * m + 1] % MOD * prob % MOD + MOD) % MOD;
        ll inv_diff = elevar_potencia((1 + MOD - coef_a) % MOD, MOD - 2);
        ll serie = (q - 1 - coef_a * (1 - elevar_potencia(coef_a, q - 1)) % MOD
                    * inv_diff % MOD + MOD) % MOD;
        serie = serie * inv_diff % MOD;
        esperanza = (esperanza + serie * prob % MOD * prob % MOD) % MOD;
    }

    ll respuesta = factor_total * suma_b % MOD * esperanza % MOD;
    printf("%lld\n", respuesta);
    return 0;
}