Problema 1: Probabilidades en Estructuras de Bosques

Este problema requiere modelar la probabilidad de que un bosque de $i$ nodos contenga exactamente $j$ nodos en su primera subtree. Definimos prob_bosque[i][j] para representar este estado. La transición considera si el $i$-ésimo nodo se integra en la primera subtree o no.

La ecuación de recurrencia se define como:

La transición para el arreglo $g$ se realiza combinando un árbol y un bosque:

using namespace std;

typedef long long ll; const int MAXN = 210; ll n_nodos, mod_val; ll inv_modular[MAXN], f_prof[MAXN][MAXN], g_forest[MAXN][MAXN], prob_dist[MAXN][MAXN];

void calcular_inversos(int n, ll m) { inv_modular[1] = 1; for (int i = 2; i <= n; i++) { inv_modular[i] = (m - m / i) * inv_modular[m % i] % m; } }

int main() { cin >> n_nodos >> mod_val; calcular_inversos(n_nodos, mod_val);

prob_dist[1][1] = 1;
for (int i = 2; i <= n_nodos; i++) {
    for (int j = 1; j <= i; j++) {
        prob_dist[i][j] = (prob_dist[i-1][j-1] * (j - 1) % mod_val * inv_modular[i] % mod_val +
                           prob_dist[i-1][j] * (i - j) % mod_val * inv_modular[i] % mod_val) % mod_val;
    }
}

for (int j = 0; j <= n_nodos; j++) {
    f_prof[1][j] = 1;
    g_forest[0][j] = 1;
}

for (int i = 1; i <= n_nodos; i++) {
    for (int j = 0; j < i; j++) {
        g_forest[i][j] = 0;
        for (int k = 1; k <= i; k++) {
            g_forest[i][j] = (g_forest[i][j] + f_prof[k][j] * g_forest[i - k][j] % mod_val * prob_dist[i][k] % mod_val) % mod_val;
        }
        f_prof[i + 1][j + 1] = g_forest[i][j];
        for (int k = j + 2; k <= n_nodos; k++) f_prof[i + 1][k] = f_prof[i + 1][j + 1];
        for (int k = j + 1; k <= n_nodos; k++) g_forest[i][k] = g_forest[i][j];
    }
}

ll esperanza_total = 0;
for (int i = 2; i <= n_nodos; i++) {
    esperanza_total = (esperanza_total + (i - 1) * (f_prof[n_nodos][i - 1] - f_prof[n_nodos][i - 2] + mod_val) % mod_val) % mod_val;
}

cout << esperanza_total << endl;
return 0;

}

### Problema 2: Conteo de Rutas con Meet-in-the-Middle

Dada la restricción de tiempo y memoria, se emplea una técnica de "Meet-in-the-middle" para una ruta de longitud $d$. Dividimos la ruta en dos mitades de longitud $d/2$ y $d - d/2$.

Definimos `dp_ida[pasos][nodo][estado]` como un valor booleano que indica si es posible alcanzar un nodo con una secuencia de bits específica (estado) tras ciertos pasos. La primera mitad comienza obligatoriamente en el nodo 1. La segunda mitad se calcula de forma inversa, comenzando desde cualquier nodo para cubrir todas las rutas posibles que terminen en cualquier punto.

Al finalizar ambas fases, combinamos los estados resultantes en los nodos intermedios para reconstruir la ruta completa de longitud $d$. El uso de `std::vector` para almacenar estados válidos por nodo optimiza la fase de combinación final.

#include #include

using namespace std;

const int MAXN = 105; const int MAX_MASK = 1 << 12; bool dp_ida[15][MAXN][MAX_MASK]; bool dp_vuelta[15][MAXN][MAX_MASK]; bool ruta_global[1 << 22];

struct Arista { int destino, color; };

vector<Arista> adj[MAXN]; vector estados_ida[MAXN], estados_vuelta[MAXN];

int main() { int n, m, d; cin >> n >> m >> d; for (int i = 0; i < m; i++) { int u, v, c; cin >> u >> v >> c; adj[u].push_back({v, c}); adj[v].push_back({u, c}); }

int mitad1 = (d + 1) / 2;
int mitad2 = d - mitad1;

dp_ida[0][1][0] = true;
for (int k = 0; k < mitad1; k++) {
    for (int u = 1; u <= n; u++) {
        if (adj[u].empty()) continue;
        for (auto &e : adj[u]) {
            for (int s = 0; s < (1 << k); s++) {
                if (dp_ida[k][u][s]) dp_ida[k + 1][e.destino][(s << 1) | e.color] = true;
            }
        }
    }
}

for (int i = 1; i <= n; i++) {
    for (int s = 0; s < (1 << mitad1); s++) {
        if (dp_ida[mitad1][i][s]) estados_ida[i].push_back(s);
    }
}

for (int i = 1; i <= n; i++) dp_vuelta[0][i][0] = true;
for (int k = 0; k < mitad2; k++) {
    for (int u = 1; u <= n; u++) {
        for (auto &e : adj[u]) {
            for (int s = 0; s < (1 << k); s++) {
                if (dp_vuelta[k][u][s]) dp_vuelta[k + 1][e.destino][(s << 1) | e.color] = true;
            }
        }
    }
}

for (int i = 1; i <= n; i++) {
    for (int s = 0; s < (1 << mitad2); s++) {
        if (dp_vuelta[mitad2][i][s]) estados_vuelta[i].push_back(s);
    }
}

for (int i = 1; i <= n; i++) {
    for (int s1 : estados_ida[i]) {
        for (int s2 : estados_vuelta[i]) {
            ruta_global[(s1 << mitad2) | s2] = true;
        }
    }
}

long long total_rutas = 0;
for (int i = 0; i < (1 << d); i++) if (ruta_global[i]) total_rutas++;
cout << total_rutas << endl;

return 0;

}

### Prbolema 3: Notas Adicionales

Este apartado queda reservado para futuras implementaciones de optimizaciones avanzadas en problemas de conteo sobre grafos dirigidos acíclicos y estructuras de datos persistentes.