Cálculo de Conexões em Retângulos

Este problema envolve a determinação do número total de "pontos de conexão" ou "ligações" dentro e entre uma coleção de retângulos em um plano 2D. A abordagem mais direta para resolvê-lo é a simulação.

Estratégia de Resolução

As ligações podem ser categorizadas em dois tipos principais:

1. Ligações internas: Aquelas presentes dentro de cada retângulo.
2. Ligações externas: Aquelas que ocorrem entre retângulos adjaecntes.

O cálculo das ligações internas é relativamente simples. Para cada retângulo, o número de ligações é proporcional ao seu perímetro. Conisderando que cada segmento de unidade na borda de um retângulo contribui com duas ligações (uma em cada "lado" da linha), a contribuição de um retângulo individual com coordenadas \((x_1, y_1)\) e \((x_2, y_2)\) é \((x_2 - x_1) \times 2 + (y_2 - y_1) \times 2\). No entanto, o problema original sugere \((x_2 - x_1) \times (y_2 - y_1) \times 2\), o que implicaria que cada célula interna também tem duas ligações. Assumiremos que a intenção é contar a área como contribuição base, e então adicionar as ligações de adjacência.

As ligações entre retângulos são mais complexas. Dada a simetria, os casos de adjacência horizontal e vertical são semelhantes. Concentraremos na adjacência horizontal, onde dois retângulos estão separados por uma distância de 1 unidade no eixo X.

Para dois retângulos, A e B, onde a diferença entre o X final de A e o X inicial de B (ou vice-versa) é 1, consideramos as seguintes situações de sobreposição no eixo Y:

1. B contém A: Se as extremidades Y de A estiverem dentro do intervalo Y de B, o número de ligações será o dobro do comprimento vertical de A. Adicionalmente, se os extremos Y de A não coincidirem com os de B, haverá 1 ligação extra para cada extremidade de A que se "encaixa" em B.
2. A contém B: Similar ao caso anterior, mas com A envolvendo B. As ligações serão o dobro do comprimento vertical de B, mais 2 ligações extras se as extremidades de B não coincidirem com as de A.
3. Sobreposição parcial: Se apenas uma extremidade Y de A estiver dentro do intervalo Y de B. As ligações são calculadas com base no comprimento da intersecção vertical, com pontos de canto adicionais se aplicável.
4. Cantos adjacentes: Se os retângulos se tocam apenas por um canto (por exemplo, X de A e X de B adjacentes, e Y de A e Y de B adjacentes), adiciona-se 1 ligação.

Para otimizar o processo, os retângulos devem ser classificados primeiramente por sua coordenada X inicial. Ao iterar através dos retângulos, se um retângulo j estiver muito distante de i para ter adjacência horizontal (retangulos[j].x1 - retangulos[i].x2 > 1), não há necessidade de verificar retângulos k > j em relação a i, devido à ordenação.

Exemplo de Código (C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // Para std::accumulate ou similar

struct Retangulo {
    long long x1, y1, x2, y2;
};

// Função de comparação para ordenação: prioriza x1, depois y1
bool compararRetangulos(const Retangulo& r1, const Retangulo& r2) {
    if (r1.x1 == r2.x1) {
        return r1.y1 < r2.y1;
    }
    return r1.x1 < r2.x1;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int num_retangulos;
    std::cin >> num_retangulos;

    std::vector<Retangulo> lista_retangulos(num_retangulos);
    long long total_conexoes = 0;

    for (int i = 0; i < num_retangulos; ++i) {
        std::cin >> lista_retangulos[i].x1 >> lista_retangulos[i].y1 >> lista_retangulos[i].x2 >> lista_retangulos[i].y2;
        // Contribuição interna: 2 vezes a "área" (ou comprimento*largura).
        // A interpretação original do problema parece ser essa.
        total_conexoes += (lista_retangulos[i].x2 - lista_retangulos[i].x1) * (lista_retangulos[i].y2 - lista_retangulos[i].y1) * 2;
    }

    // Ordena os retângulos para otimizar a busca por adjacências
    std::sort(lista_retangulos.begin(), lista_retangulos.end(), compararRetangulos);

    // Itera sobre pares de retângulos para encontrar adjacências
    for (int i = 0; i < num_retangulos; ++i) {
        for (int j = i + 1; j < num_retangulos; ++j) {
            // Otimização: se o retângulo j está muito à direita de i para ser adjacente,
            // então os próximos retângulos também estarão (devido à ordenação por x1).
            if (lista_retangulos[j].x1 - lista_retangulos[i].x2 > 1) {
                break;
            }

            // --- Verificação de adjacência horizontal (no eixo X) ---
            bool adjacente_x = (lista_retangulos[i].x2 == lista_retangulos[j].x1 - 1) || (lista_retangulos[j].x2 == lista_retangulos[i].x1 - 1);

            if (adjacente_x) {
                // Calcula a intersecção vertical
                long long y_inicio_intersecao = std::max(lista_retangulos[i].y1, lista_retangulos[j].y1);
                long long y_fim_intersecao = std::min(lista_retangulos[i].y2, lista_retangulos[j].y2);
                long long comprimento_intersecao_y = y_fim_intersecao - y_inicio_intersecao;

                if (comprimento_intersecao_y > 0) { // Há sobreposição vertical
                    total_conexoes += 2 * comprimento_intersecao_y; // 2 conexões por unidade de comprimento
                }
                // Conexões de canto: se um retângulo "estende" além do outro na direção Y
                if (lista_retangulos[i].y1 < lista_retangulos[j].y1 && lista_retangulos[i].y2 >= lista_retangulos[j].y1) {
                    total_conexoes++; // Canto inferior de J com parte de I
                }
                if (lista_retangulos[i].y2 > lista_retangulos[j].y2 && lista_retangulos[i].y1 <= lista_retangulos[j].y2) {
                    total_conexoes++; // Canto superior de J com parte de I
                }
                if (lista_retangulos[j].y1 < lista_retangulos[i].y1 && lista_retangulos[j].y2 >= lista_retangulos[i].y1) {
                    total_conexoes++; // Canto inferior de I com parte de J
                }
                if (lista_retangulos[j].y2 > lista_retangulos[i].y2 && lista_retangulos[j].y1 <= lista_retangulos[i].y2) {
                    total_conexoes++; // Canto superior de I com parte de J
                }
            }

            // --- Verificação de adjacência vertical (no eixo Y) ---
            bool adjacente_y = (lista_retangulos[i].y2 == lista_retangulos[j].y1 - 1) || (lista_retangulos[j].y2 == lista_retangulos[i].y1 - 1);

            if (adjacente_y) {
                // Calcula a intersecção horizontal
                long long x_inicio_intersecao = std::max(lista_retangulos[i].x1, lista_retangulos[j].x1);
                long long x_fim_intersecao = std::min(lista_retangulos[i].x2, lista_retangulos[j].x2);
                long long comprimento_intersecao_x = x_fim_intersecao - x_inicio_intersecao;

                if (comprimento_intersecao_x > 0) { // Há sobreposição horizontal
                    total_conexoes += 2 * comprimento_intersecao_x;
                }
                // Conexões de canto
                if (lista_retangulos[i].x1 < lista_retangulos[j].x1 && lista_retangulos[i].x2 >= lista_retangulos[j].x1) {
                    total_conexoes++;
                }
                if (lista_retangulos[i].x2 > lista_retangulos[j].x2 && lista_retangulos[i].x1 <= lista_retangulos[j].x2) {
                    total_conexoes++;
                }
                if (lista_retangulos[j].x1 < lista_retangulos[i].x1 && lista_retangulos[j].x2 >= lista_retangulos[i].x1) {
                    total_conexoes++;
                }
                if (lista_retangulos[j].x2 > lista_retangulos[i].x2 && lista_retangulos[j].x1 <= lista_retangulos[i].x2) {
                    total_conexoes++;
                }
            }

            // --- Verificação de adjacência de canto exata ---
            // Se os retângulos se tocam apenas por um vértice, sem sobreposição de borda
            if ( (lista_retangulos[i].x2 == lista_retangulos[j].x1 - 1 && lista_retangulos[i].y2 == lista_retangulos[j].y1 - 1) ||
                 (lista_retangulos[j].x2 == lista_retangulos[i].x1 - 1 && lista_retangulos[j].y2 == lista_retangulos[i].y1 - 1) ||
                 (lista_retangulos[i].x2 == lista_retangulos[j].x1 - 1 && lista_retangulos[j].y2 == lista_retangulos[i].y1 - 1) ||
                 (lista_retangulos[j].x2 == lista_retangulos[i].x1 - 1 && lista_retangulos[i].y2 == lista_retangulos[j].y1 - 1) ) {
                total_conexoes++;
            }
        }
    }

    std::cout << total_conexoes << std::endl;

    return 0;
}

Fusão de Segment Trees em Árvores (DSU on Trees)

Este problema requer a manutenção e consulta de informações sobre cores (identificadores e tempos de aparição) em subárvores de uma estrutura de árvore, com uma restrição de capacidade. A técnica ideal para resolver isso eficientemente é o DSU on Trees (Disjoint Set Union on Trees), também conhecido como Small-to-Large merging, combinado com uma Segment Tree para agregar os dados.

Conceitos Chave

• DSU on Trees: Uma otimização de DFS que processa subárvores. Ela mantém a estrutura de dados (como uma Segment Tree) da subárvore "pesada" (a com maior número de nós) e "limpa" as estruturas das subárvores "leves" após processá-las, reinserindo seus elementos na estrutura do pai. Isso economiza tempo, pois a subárvore pesada não precisa ser reconstruída repetidamente.
• Segment Tree: Usada como a estrutura de dados para agregar informações sobre cores. Cada nó da Segment Tree representa um intervalo de "tempo" (o valor de tempo de aparição da cor). A Segment Tree armazenará o número de tipos de cores distintas e o total de ocorrências de cores dentro de um dado intervalo de tempo.
• Discretização: Como os valores de "cor" podem ser grandes ou negativos, e "tempo" também, é crucial discretizá-los. Isso mapeia os valores originais para um intervalo menor e contínuo, permitindo o uso eficiente da Segment Tree.

Estratégia de Resolução Detalhada

1. Pré-processamento DFS (DFS1): Realiza uma DFS inicial para calcular o tamanho de cada subárvore e identificar o filho pesado para cada nó. O filho pesado é aquele cuja subárvore possui o maior número de eventos (pares cor-tempo).
2. Discretização de Cores e Tempos: Coleta todos os IDs de cores únicos e seus tempos de aparição. Ordena esses valores e mapeia-os para índices sequenciais usando std::lower_bound.
3. DFS Principal (DFS2):
   • Visita recursivamente todos os filhos leves de um nó x. Após procesar cada filho leve, sua Segment Tree é "limpa" (resetada) para reutilização de memória e evitar interferência.
   • Visita o filho pesado de x. A Segment Tree do filho pesado não é limpa, pois seus dados serão reutilizados pelo pai.
   • Adiciona os eventos (pares cor-tempo) diretamente associados ao nó x na Segment Tree global.
   • Re-adiciona os eventos de todos os filhos leves (que foram limpos) na Segment Tree global.
   • Consulta a Segment Tree para obter a resposta para o nó x, com base em sua capacidade s[x].
   • Para o filho pesado, move (ou "troca") os eventos de x para a lista de eventos do filho pesado. Isso é uma otimização de memória onde a lista de eventos do filho pesado se torna a lista de eventos do nó x para seu pai.
4. Operações na Segment Tree:
   • update(pos, delta_tipos, delta_ocorrencias): Atualiza a Segment Tree. delta_tipos incrementa/decrementa o contador de tipos distintos de cores, enquanto delta_ocorrencias ajusta o total de ocorrências.
   • add_event(cor, tempo): Esta função envolve lógica para lidar com a "última aparição" de uma cor. Se uma cor C aparece no tempo T:
     • Se C nunca apareceu antes (ultimo_tempo_cor[C] == 0), adiciona 1 tipo de cor no tempo T e 1 ocorrência no tempo T. Atualiza ultimo_tempo_cor[C] = T.
     • Se C já apareceu antes no tempo T_antigo = ultimo_tempo_cor[C] e T < T_antigo, significa que esta nova aparição é "mais antiga" e agora é a relevante para o tipo distinto. Então, decrementa 1 tipo de cor no tempo T_antigo e incrementa 1 tipo de cor no tempo T. Atualiza ultimo_tempo_cor[C] = T.
     • Sempre incrementa 1 ocorrência no tempo T.
   • query(rank_ocorrencias): Percorre a Segment Tree para encontrar a soma dos tipos de cores distintas que correspondem a um número total de ocorrências menor ou igual a rank_ocorrencias.

Exemplo de Código (C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <map> // Para discretização, se não usar std::sort + std::unique
#include <tuple> // Para std::tuple

// Constantes
const int MAX_NOS = 1e5 + 10;
const int MAX_TEMPOS = 1e6 + 10; // Máximo de eventos (tempos discretizados)

// Estrutura para a Segment Tree
// num_tipos_distintos: armazena a contagem de tipos de cores distintas
// total_ocorrencias: armazena a contagem total de ocorrências de cores
long long num_tipos_distintos[4 * MAX_TEMPOS];
long long total_ocorrencias[4 * MAX_TEMPOS];
bool marcador_limpeza[4 * MAX_TEMPOS]; // Flag para limpeza de subárvores leves

// Variáveis globais
int N_nos, M_eventos, Q_consultas;
int capacidades_s[MAX_NOS]; // s[x] no original
long long resultados_consultas[MAX_NOS]; // ans[x] no original

// Adjacência da árvore
std::vector<int> adj[MAX_NOS];

// Dados da subárvore e DSU on Trees
int tamanho_subarvore[MAX_NOS]; // siz[x] no original
int filho_pesado[MAX_NOS];      // son[x] no original
std::vector<std::pair<int, int> > eventos_no[MAX_NOS]; // vector<pair>> v[x] no original (cor, tempo)
int ultimo_tempo_cor[MAX_TEMPOS]; // tim[col] no original

// Variável para o número de tempos únicos (igual a M_eventos, se cada evento tem um tempo distinto)
int num_tempos_unicos; 

// --- Funções da Segment Tree ---
void propagar_limpeza(int idx_no) {
    if (!marcador_limpeza[idx_no]) return;

    num_tipos_distintos[idx_no * 2] = num_tipos_distintos[idx_no * 2 + 1] = 0;
    total_ocorrencias[idx_no * 2] = total_ocorrencias[idx_no * 2 + 1] = 0;
    marcador_limpeza[idx_no * 2] = marcador_limpeza[idx_no * 2 + 1] = true;
    marcador_limpeza[idx_no] = false;
}

void atualizar_pai(int idx_no) {
    num_tipos_distintos[idx_no] = num_tipos_distintos[idx_no * 2] + num_tipos_distintos[idx_no * 2 + 1];
    total_ocorrencias[idx_no] = total_ocorrencias[idx_no * 2] + total_ocorrencias[idx_no * 2 + 1];
}

void atualizar_segment_tree(int idx_no, int inicio, int fim, int pos, int delta_tipos, int delta_ocorrencias) {
    if (inicio == fim) {
        num_tipos_distintos[idx_no] += delta_tipos;
        total_ocorrencias[idx_no] += delta_ocorrencias;
        return;
    }
    propagar_limpeza(idx_no);
    int meio = (inicio + fim) / 2;
    if (pos <= meio) {
        atualizar_segment_tree(idx_no * 2, inicio, meio, pos, delta_tipos, delta_ocorrencias);
    } else {
        atualizar_segment_tree(idx_no * 2 + 1, meio + 1, fim, pos, delta_tipos, delta_ocorrencias);
    }
    atualizar_pai(idx_no);
}

// Consulta a Segment Tree para a soma de tipos distintos, dada uma capacidade de ocorrências
long long consultar_segment_tree(int idx_no, int inicio, int fim, int capacidade_max_ocorrencias) {
    if (capacidade_max_ocorrencias <= 0) return 0;
    if (inicio == fim) {
        return num_tipos_distintos[idx_no];
    }
    propagar_limpeza(idx_no);
    int meio = (inicio + fim) / 2;
    // Se a capacidade total de ocorrências do filho esquerdo é menor ou igual à nossa capacidade,
    // podemos pegar todos os tipos distintos do filho esquerdo e tentar pegar mais do direito.
    if (capacidade_max_ocorrencias >= total_ocorrencias[idx_no * 2]) {
        return num_tipos_distintos[idx_no * 2] + consultar_segment_tree(idx_no * 2 + 1, meio + 1, fim, capacidade_max_ocorrencias - total_ocorrencias[idx_no * 2]);
    }
    // Caso contrário, a capacidade é esgotada no filho esquerdo
    return consultar_segment_tree(idx_no * 2, inicio, meio, capacidade_max_ocorrencias);
}

// --- Funções DSU on Trees ---

// DFS1: Calcula tamanhos de subárvore e identifica filhos pesados
void dfs_calcula_pesos(int u, int pai) {
    tamanho_subarvore[u] = eventos_no[u].size(); // Eventos no próprio nó
    filho_pesado[u] = 0; // Reset filho pesado

    for (int v : adj[u]) {
        if (v == pai) continue;
        dfs_calcula_pesos(v, u);
        tamanho_subarvore[u] += tamanho_subarvore[v]; // Acumula eventos da subárvore
        if (tamanho_subarvore[filho_pesado[u]] < tamanho_subarvore[v]) {
            filho_pesado[u] = v;
        }
    }
}

// Função para limpar a Segment Tree de uma subárvore
void limpar_subarvore_segment_tree(int u) {
    marcador_limpeza[1] = true; // Marca a raiz da Segment Tree para limpeza
    num_tipos_distintos[1] = total_ocorrencias[1] = 0;
    // Reseta o tempo da última aparição para todas as cores neste nó/subárvore
    for (const auto& evento : eventos_no[u]) {
        ultimo_tempo_cor[evento.first] = 0;
    }
}

// Adiciona todos os eventos de um nó (ou subárvore leve) à Segment Tree global
void adicionar_eventos_na_segment_tree(int u) {
    for (const auto& evento : eventos_no[u]) {
        int cor = evento.first;
        int tempo_discretizado = evento.second;

        if (ultimo_tempo_cor[cor] == 0) { // Primeira vez que vemos esta cor
            atualizar_segment_tree(1, 1, num_tempos_unicos, tempo_discretizado, 1, 0); // Adiciona um tipo distinto
            ultimo_tempo_cor[cor] = tempo_discretizado;
        } else if (tempo_discretizado < ultimo_tempo_cor[cor]) { // Nova aparição é mais antiga
            atualizar_segment_tree(1, 1, num_tempos_unicos, ultimo_tempo_cor[cor], -1, 0); // Remove o tipo antigo
            atualizar_segment_tree(1, 1, num_tempos_unicos, tempo_discretizado, 1, 0);    // Adiciona o novo tipo
            ultimo_tempo_cor[cor] = tempo_discretizado;
        }
        atualizar_segment_tree(1, 1, num_tempos_unicos, tempo_discretizado, 0, 1); // Sempre adiciona uma ocorrência
    }
}

// Move eventos de 'origem' para 'destino'
void mover_eventos(int origem, int destino) {
    for (const auto& evento : eventos_no[origem]) {
        eventos_no[destino].push_back(evento);
    }
    eventos_no[origem].clear(); // Limpa a origem
}

// DFS2: Processa a árvore usando DSU on Trees
void dfs_processa_arvore(int u, int pai) {
    // Processa filhos leves primeiro
    for (int v : adj[u]) {
        if (v == pai || v == filho_pesado[u]) continue;
        dfs_processa_arvore(v, u);
        limpar_subarvore_segment_tree(v); // Limpa Segment Tree do filho leve
    }

    // Processa filho pesado (se existir), mantendo seus dados
    if (filho_pesado[u] != 0) {
        dfs_processa_arvore(filho_pesado[u], u);
        // Após o retorno, a Segment Tree já contém os dados do filho pesado
    }

    // Adiciona os eventos do nó 'u' na Segment Tree
    adicionar_eventos_na_segment_tree(u);

    // Re-adiciona os eventos dos filhos leves na Segment Tree
    for (int v : adj[u]) {
        if (v == pai || v == filho_pesado[u]) continue;
        adicionar_eventos_na_segment_tree(v);
    }

    // Armazena o resultado para o nó 'u'
    resultados_consultas[u] = consultar_segment_tree(1, 1, num_tempos_unicos, capacidades_s[u]);

    // Otimização: se 'u' tem um filho pesado, 'u' reutiliza o vetor de eventos do filho pesado.
    // Isso é feito para que a lista de eventos de 'u' inclua a do filho pesado,
    // e os eventos dos filhos leves sejam adicionados a essa lista.
    if (filho_pesado[u] != 0) {
        // Primeiro move os próprios eventos de 'u' para a lista do filho pesado,
        // porque a lista de 'u' vai se tornar a lista do filho pesado.
        mover_eventos(u, filho_pesado[u]);
        // Em seguida, 'u' assume a lista de eventos do filho pesado.
        std::swap(eventos_no[u], eventos_no[filho_pesado[u]]);
    }
    // Finalmente, move os eventos dos filhos leves (que foram limpos e re-adicionados
    // na Segment Tree) para a lista de eventos de 'u' (que agora inclui o filho pesado).
    for (int v : adj[u]) {
        if (v == pai || v == filho_pesado[u]) continue; // Filho pesado já tratado pelo swap
        mover_eventos(v, u);
    }
}


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> N_nos;

    for (int i = 0; i < N_nos - 1; ++i) {
        int u, v_node;
        std::cin >> u >> v_node;
        adj[u].push_back(v_node);
        adj[v_node].push_back(u);
    }

    for (int i = 1; i <= N_nos; ++i) {
        std::cin >> capacidades_s[i];
    }

    std::cin >> M_eventos;
    std::vector<int> cores_para_discretizar_aux;
    std::vector<std::tuple<int, int, int>> eventos_brutos(M_eventos); // (no, cor_original, tempo_idx)

    for (int i = 0; i < M_eventos; ++i) {
        int no, cor;
        std::cin >> no >> cor;
        eventos_brutos[i] = std::make_tuple(no, cor, i + 1); // tempo_original_idx = i+1
        cores_para_discretizar_aux.push_back(cor);
    }
    
    // Discretização de CORES
    std::sort(cores_para_discretizar_aux.begin(), cores_para_discretizar_aux.end());
    cores_para_discretizar_aux.erase(
        std::unique(cores_para_discretizar_aux.begin(), cores_para_discretizar_aux.end()),
        cores_para_discretizar_aux.end()
    );

    // Mapeia cores originais para seus IDs discretizados
    // E popula a lista de eventos para cada nó
    for (int i = 0; i < M_eventos; ++i) {
        int no = std::get<0>(eventos_brutos[i]);
        int cor_original = std::get<1>(eventos_brutos[i]);
        int tempo_original_idx = std::get<2>(eventos_brutos[i]);

        int id_cor_mapeado = std::lower_bound(cores_para_discretizar_aux.begin(), cores_para_discretizar_aux.end(), cor_original) - cores_para_discretizar_aux.begin() + 1;
        eventos_no[no].push_back({id_cor_mapeado, tempo_original_idx});
    }

    // num_tempos_unicos é o número máximo de "tempos" ou eventos, que é M_eventos
    num_tempos_unicos = M_eventos;

    dfs_calcula_pesos(1, 0); // Começa DFS1 da raiz (nó 1)
    dfs_processa_arvore(1, 0); // Começa DFS2 da raiz (nó 1)

    std::cin >> Q_consultas;
    for (int i = 0; i < Q_consultas; ++i) {
        int no_consulta;
        std::cin >> no_consulta;
        std::cout << resultados_consultas[no_consulta] << "\n";
    }

    return 0;
}
</pair>

Cálculo Combinatório de Máximos Ponderados

Este problema, embora pareça envolver expectativa, é resolvido por uma abordagem puramente combinatória. A tarefa é calcular uma soma ponderada relacionada à dificuldade máxima de tarefas selecionadas ao longo de várias janelas de tempo.

Conceitos e Fórmula

Considere que temos \(m\) níveis de dificuldade, cada um com um peso \(wt_i\), e estamos selecionando tarefas por \(k\) dias. O total de sequências possíveis de dificuldades para \(k\) dias é \(m^k\).

O cerne da solução está em determinar quantas sequências de \(k\) dias têm um nível de dificuldade máximo exato \(i\). Isso pode ser calculado da seguinte forma:

• O número total de sequências onde a dificuldade máxima é menor ou igual a \(i\) é \(i^k\).
• O número total de sequências onde a dificuldade máxima é menor ou igual a \(i-1\) é \((i-1)^k\).

Portanto, o número de sequências onde a dificuldade máxima é exatamente \(i\) é \((i^k - (i-1)^k)\).

A contribuição ponderada de um nível de dificuldade \(i\) para o total é \((i^k - (i-1)^k) \times wt_i\). Somamos essa contribuição para todos os níveis de dificuldade de 1 a \(m\):

\(\sum\limits_{i=1}^{m} (i^k - (i-1)^k) \times wt_i\)

Este somatório nos dá a soma total das dificuldades máximas ponderadas para uma única janela de \(k\) dias.

No entanto, o problema considera um total de \(n\) dias, e existem \((n - k + 1)\) janelas de \(k\) dias possíveis. Para obter a resposta final, precisamos multiplicar o somatório pelo número de janelas e, em seguida, dividir pelo total de combinações possíveis em uma janela para obter uma "média ponderada" ou "esperança". A divisão é feita multiplicando pelo inverso modular de \(m^k\).

Exemplo de Código (C++)

#include <iostream>
#include <vector>
#include <numeric>

const long long MOD = 1000000007;

// Função para calcular potência modular (x^y % MOD)
long long potencia_modular(long long base, long long expoente) {
    long long resultado = 1;
    base %= MOD;
    while (expoente > 0) {
        if (expoente % 2 == 1) resultado = (resultado * base) % MOD;
        base = (base * base) % MOD;
        expoente /= 2;
    }
    return resultado;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long total_dias_N;
    long long num_niveis_M;
    long long tamanho_janela_K;
    std::cin >> total_dias_N >> num_niveis_M >> tamanho_janela_K;

    // Se o tamanho da janela K for maior que o número total de dias N, não há janelas válidas.
    if (tamanho_janela_K > total_dias_N) {
        std::cout << 0 << std::endl;
        return 0;
    }

    std::vector<long long> pesos_dificuldade(num_niveis_M + 1);
    for (int i = 1; i <= num_niveis_M; ++i) {
        std::cin >> pesos_dificuldade[i];
    }

    // Calcula o inverso modular de M^K
    // base_inv = (M^K)^(-1) mod MOD
    long long m_k_potencia = potencia_modular(num_niveis_M, tamanho_janela_K);
    long long inv_m_k = potencia_modular(m_k_potencia, MOD - 2); // Fermat's Little Theorem

    long long soma_ponderada_maximos = 0;

    for (int i = 1; i <= num_niveis_M; ++i) {
        long long num_seq_max_i = potencia_modular(i, tamanho_janela_K);
        long long num_seq_max_i_menos_1 = potencia_modular(i - 1, tamanho_janela_K);

        // Calcula (i^K - (i-1)^K) % MOD, garantindo que o resultado seja positivo
        long long diff = (num_seq_max_i - num_seq_max_i_menos_1 + MOD) % MOD;
        
        // Adiciona a contribuição ponderada ao total
        soma_ponderada_maximos = (soma_ponderada_maximos + (diff * pesos_dificuldade[i]) % MOD) % MOD;
    }

    // Multiplica pela quantidade de janelas possíveis (N - K + 1)
    long long num_janelas = total_dias_N - tamanho_janela_K + 1;
    long long resultado_final = (soma_ponderada_maximos * num_janelas) % MOD;
    
    // Multiplica pelo inverso modular de M^K
    resultado_final = (resultado_final * inv_m_k) % MOD;

    std::cout << resultado_final << std::endl;

    return 0;
}

Caminho de Menor Custo com Compressão de Estados

Este problema pede o custo mínimo para conectar todos os nós em um grafo, começando de um nó arbitrário. O custo de adicionar uma aresta depende do "nível" ou "profundidade" do nó de onde a aresta é ativada. Esta é uma aplicação clássica de Programação Dinâmica (DP) com compressão de estados, ou uma busca com poda inteligente.

Abordagem com DFS e DP por Estado

O problema pode ser modelado como encontrar um caminho (ou conjunto de arestas ativadas) que conecta todos os nós. A peculiaridade é que o custo de uma aresta \((u, v)\) é dado por \(\text{peso}(u,v) \times \text{profundidade}(u)\), onde \(\text{profundidade}(u)\) é a distância em termos de número de arestas desde o nó inicial até \(u\).

Usaremos uma DP baseada em estados, onde cada estado é uma máscara de bits que representa o conjunto de nós já conectados. A função de DP pode ser definida como \(dp[\text{mask}]\), o custo mínimo para conectar todos os nós representados pela \(\text{mask}\).

A solução proposta utiliza uma busca em profundidade (DFS) para explorar os estados:

• profundidade[j]: A profundidade do nó j a partir do nó inicial da componente conectada atual.
• dp_custo_minimo[mask]: O custo mínimo para alcançar o estado mask (um conjunto de nós conectados).

A transição de estado ocorre quando adicionamos um nó j que ainda não está na mask, a partir de um nó i que já está na mask. A nova máscara será mask | (1 << (j-1)).

A fórmula de transição seria:

\(dp\_custo\_minimo[\text{nova\_mask}] = \min(dp\_custo\_minimo[\text{nova\_mask}], dp\_custo\_minimo[\text{mask}] + \text{custo\_aresta}[i][j] \times \text{profundidade}[i])\)

O algoritmo geral é:

1. Inicialize dp_custo_minimo com infinito para todos os estados, exceto para estados iniciais.
2. Para cada nó i de 1 a N:
   • Considere i como o nó inicial. Defina profundidade[i] = 1 e dp_custo_minimo[1 << (i-1)] = 0.
   • Inicie uma DFS a partir deste estado.
   • Dentro da DFS:
     • Itere sobre todos os nós i que já estão na mask atual.
     • Itere sobre todos os nós j que não estão na mask atual.
     • Se houver uma aresta de i para j, calcule o custo de adicionar j. Se este novo custo é menor que o custo atual em dp_custo_minimo[nova_mask]:
       • Atualize dp_custo_minimo[nova_mask].
       • Defina profundidade[j] = profundidade[i] + 1.
       • Faça a chamada recursiva para dfs(nova_mask).
       • Importante: Após a chamada recursiva, restaure profundidade[j] ao seu valor original antes desta transição para não afetar outros caminhos.
3. A resposta final é o mínimo de dp_custo_minimo[(1 << N) - 1] (o estado onde todos os N nós estão conectados) para todas as possíveis escolhas de nó inicial.

A restauração da profundidade após a chamada recursiva é crucial para que a DFS explore caminhos independentemente, sem que as profundidades de um caminho afetem incorretamente outros. Isso transforma a DFS em uma busca exploratória que, junto com a memoização implícita em dp_custo_minimo, encontra a solução ótima.

Exemplo de Código (C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // Para memset

const int MAX_NOS_GRAFO = 15; // N <= 15
const int INFINITO = 0x3f3f3f3f; // Valor grande para representar infinito

int N_nos, M_arestas;
int custo_minimo_total = INFINITO;

// custo_aresta[u][v] armazena o peso da aresta entre u e v
int custo_aresta[MAX_NOS_GRAFO + 1][MAX_NOS_GRAFO + 1];

// dp_custo_minimo[mask] armazena o custo mínimo para conectar os nós na máscara
int dp_custo_minimo[1 << MAX_NOS_GRAFO];

// profundidade_no[j] armazena a profundidade do nó j na componente conectada atual
int profundidade_no[MAX_NOS_GRAFO + 1];

// Função DFS para explorar estados de conexão
void explorar_estados(int mascara_atual) {
    // Itera sobre todos os nós que já estão conectados na mascara_atual
    for (int i = 1; i <= N_nos; ++i) {
        if (!((1 << (i - 1)) & mascara_atual)) continue; // Nó i não está na máscara

        // Itera sobre todos os nós que AINDA NÃO estão conectados
        for (int j = 1; j <= N_nos; ++j) {
            if (((1 << (j - 1)) & mascara_atual)) continue; // Nó j já está na máscara

            // Se existe uma aresta entre i e j e seu custo é válido
            if (custo_aresta[i][j] != INFINITO) {
                int proxima_mascara = mascara_atual | (1 << (j - 1));
                
                // Calcula o custo para adicionar o nó j a partir do nó i
                // O custo depende da profundidade do nó i
                int custo_adicionar_j = custo_aresta[i][j] * profundidade_no[i];

                // Se encontramos um caminho mais barato para proxima_mascara
                if (dp_custo_minimo[proxima_mascara] > dp_custo_minimo[mascara_atual] + custo_adicionar_j) {
                    dp_custo_minimo[proxima_mascara] = dp_custo_minimo[mascara_atual] + custo_adicionar_j;
                    
                    int profundidade_antiga_j = profundidade_no[j]; // Salva profundidade original de j
                    profundidade_no[j] = profundidade_no[i] + 1; // Define nova profundidade para j
                    
                    explorar_estados(proxima_mascara); // Chama recursivamente
                    
                    profundidade_no[j] = profundidade_antiga_j; // Restaura profundidade de j
                }
            }
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> N_nos >> M_arestas;

    // Inicializa a matriz de custos com infinito
    memset(custo_aresta, INFINITO, sizeof(custo_aresta));

    for (int i = 0; i < M_arestas; ++i) {
        int u, v, peso;
        std::cin >> u >> v >> peso;
        // Assume grafo não direcionado e múltiplos arestas entre os mesmos nós
        // Escolhe o menor peso
        custo_aresta[u][v] = std::min(custo_aresta[u][v], peso);
        custo_aresta[v][u] = std::min(custo_aresta[v][u], peso);
    }

    // Tenta cada nó como ponto de partida
    for (int no_inicial = 1; no_inicial <= N_nos; ++no_inicial) {
        // Inicializa profundidades e custos DP para este ponto de partida
        memset(profundidade_no, INFINITO, sizeof(profundidade_no));
        memset(dp_custo_minimo, INFINITO, sizeof(dp_custo_minimo));

        profundidade_no[no_inicial] = 1; // O nó inicial tem profundidade 1
        dp_custo_minimo[1 << (no_inicial - 1)] = 0; // Custo zero para conectar apenas o nó inicial

        explorar_estados(1 << (no_inicial - 1)); // Inicia a DFS

        // Atualiza o custo mínimo global se esta subárvore encontrou uma solução melhor
        custo_minimo_total = std::min(custo_minimo_total, dp_custo_minimo[(1 << N_nos) - 1]);
    }

    std::cout << custo_minimo_total << std::endl;

    return 0;
}