Programação Dinâmica em Árvores e Grafos
Construção de Árvores e Fórmula de Cayley Estendida
Para resolver problemas de contagem de árvores geradoras com restrições de componentes conexos, utilizamos a fórmula estendida de Cayley. A abordagem envolve Programação Dinâmica (PD) em árvores, onde o estado dp[u][has_key][size] representa o número de maneiras de formar um componente conexo de tamanho size na subárvore enraizada em u, indicando se um nó chave foi selecionado. A transição considera a conexão ou desconexão de arestas, ajustando as contribuições para evitar sobreposição.
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
int n;
vector<int> adj[1005];
bool is_key[1005];
int subtree_size[1005];
// dp[node][has_key][component_size]
vector<vector<vector<ll>>> dp;
void add_mod(ll &a, ll b) {
a = (a + b) % MOD;
}
void dfs(int u, int parent) {
subtree_size[u] = 1;
dp[u][0][1] = 1;
dp[u][1][1] = is_key[u] ? 1 : 0;
for (int v : adj[u]) {
if (v == parent) continue;
dfs(v, u);
int new_size = subtree_size[u] + subtree_size[v];
vector<vector<vector<ll>>> next_dp(2, vector<vector<ll>>(2, vector<ll>(new_size + 1, 0)));
for (int i = 1; i <= subtree_size[u]; ++i) {
for (int j = 1; j <= subtree_size[v]; ++j) {
// Case 1: Connect u and v
add_mod(next_dp[0][i + j], dp[u][0][i] * dp[v][0][j] % MOD);
add_mod(next_dp[1][i + j], (dp[u][0][i] * dp[v][1][j] + dp[u][1][i] * dp[v][0][j]) % MOD);
// Case 2: Disconnect u and v (multiply by n for Cayley formula)
add_mod(next_dp[0][i + j - 1], n * dp[u][0][i] % MOD * dp[v][1][j] % MOD);
add_mod(next_dp[1][i + j - 1], n * dp[u][1][i] % MOD * dp[v][1][j] % MOD);
// Case 3: Subtract overcounted disconnected states
add_mod(next_dp[0][i + j - 1], MOD - dp[u][0][i] * dp[v][0][j] % MOD);
add_mod(next_dp[1][i + j - 1], MOD - (dp[u][0][i] * dp[v][1][j] + dp[u][1][i] * dp[v][0][j]) % MOD);
}
}
subtree_size[u] = new_size;
dp[u] = next_dp;
}
}
Árvore de Steiner Mínima
O problema exige conectar um conjunto de nós chave com o custo mínimo. Definimos f[i][S] como o custo mínimo para conectar o nó i ao conjunto de nós chave S. As transições são divididas em duas: relaxamento de arestas (semelhante ao algoritmo de Dijkstra) e união de subconjuntos de nós chave. A complexidade total é \(O(n \times 3^k + m \log m \times 2^k)\).
Árvore de Reconstrução de Kruskal e Soma de Minkowski
Em problemas de otimização em árvores, a Árvore de Reconstrução de Kruskal permite transformar restrições de arestas em estruturas hierárquicas. Ao combinar subárvores, a operação de convolução \((\min, +)\) exibe convexidade, permitindo o uso da Soma de Minkowski. Mantendo as diferenças \(f_{x,i} - f_{x,i+1}\) em uma estrutura de dados balanceada (como std::set), a fusão heurística reduz a complexidade para \(O(n \log^2 n)\).
Estruturas de Dados e Otimizações
Árvore de Segmentos de Li Chao e Linha de Varredura
Ao lidar com funções lineares onde a variável é o parâmetro da função, podemos usar a Árvore de Segmentos de Li Chao. Combinada com a técnica de linha de varredura (sweep line), processamos as consultas da esquerda para a direita, mantendo o valor máximo das funções lineares ativas para resolver problemas de maximização de prefixos e sufixos.
Decomposição Pesada-Leve e Carimbos de Tempo
Para gerenciar a validade de arestas em caminhos de árvores, a Decomposição Pesada-Leve (HLD) é combinada com uma Árvore de Segmentos. Em vez de atualizações complexas, mantemos carimbos de tempo (timestamps) para cada nó, registrando a última vez que uma aresta leve se tornou inválida. As consultas e atualizações são realizadas em \(O(\log^2 n)\).
Autômato de Sufixos (SAM) e Diferenças
Para consultas de substrings, construímos um Autômato de Sufixos (SAM) e processamos os endpos em ordem crescente. A contribuição de cada nó na árvore de falhas pode ser calculada usando difference arrays e somas de sufixo. Isso permite atualizações e consultas eficientes ao percorrer o SAM, resultando em uma complexidade de \(O(n^2 + q)\).
Árvore de Permutação e Interpolação de Lagrange
Otimização de PD em Intervalos com Polinômios
Para problemas complexos de contagem de intervalos, construímos uma Árvore de Permutação (Permutation Tree) para representar segmnetos contínuos e primitivos. A PD em intervalos é otimizada tratando a dimensão do número de segmentos contínuos como um polinômio. Avaliamos o polinômio em \(M+1\) pontos e usamos a Interpolação de Lagrange para recuperar os coeficientes finais, reduzindo a complexidade de \(O(n^8)\) para \(O(n^6)\).
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAXN = 45;
int n, max_segments;
int limit_arr[MAXN];
ll poly_eval[MAXN], final_coeffs[MAXN];
ll dp_and[MAXN][MAXN][MAXN], dp_or[MAXN][MAXN][MAXN];
ll sum_and[MAXN][MAXN], sum_or[MAXN][MAXN];
ll power(ll base, ll exp) {
ll res = 1;
base %= MOD;
while (exp > 0) {
if (exp & 1) res = res * base % MOD;
base = base * base % MOD;
exp >>= 1;
}
return res;
}
void solve_permutation_tree() {
for (int eval_point = 1; eval_point <= max_segments + 1; ++eval_point) {
memset(dp_and, 0, sizeof(dp_and));
memset(dp_or, 0, sizeof(dp_or));
memset(sum_and, 0, sizeof(sum_and));
memset(sum_or, 0, sizeof(sum_or));
for (int i = 1; i <= n; ++i) {
dp_or[i][i][1] = 1;
if (i > limit_arr[i]) {
dp_and[i][i][1] = sum_and[i][i] = eval_point;
}
}
for (int len = 2; len <= n; ++len) {
for (int l = 1; l + len - 1 <= n; ++l) {
int r = l + len - 1;
for (int mid = l + 1; mid < r; ++mid) {
for (int k = 1; k <= r - l + 1; ++k) {
dp_or[l][r][k] = (dp_or[l][r][k] + dp_or[l][mid - 1][k - 1] * (sum_and[mid][r - 1] + sum_or[mid][r - 1])) % MOD;
}
}
for (int k = 1; k <= r - l + 1; ++k) {
dp_or[l][r][k] = (dp_or[l][r][k] + dp_or[l][r - 1][k - 1]) % MOD;
}
if (r <= limit_arr[l]) continue;
for (int k = 2; k <= r - l + 1; ++k) {
sum_or[l][r] = (sum_or[l][r] + dp_or[l][r][k]) % MOD;
}
for (int mid = l; mid <= r; ++mid) {
for (int k = 1; k <= r - l + 1; ++k) {
dp_and[l][r][k] = (dp_and[l][r][k] + dp_and[l][mid - 1][k - 1] * sum_or[mid][r]) % MOD;
}
}
for (int k = 2; k <= r - l + 1; ++k) {
sum_and[l][r] = (sum_and[l][r] + dp_and[l][r][k]) % MOD;
}
}
}
poly_eval[eval_point] = (sum_and[1][n] + sum_or[1][n]) % MOD;
}
memset(final_coeffs, 0, sizeof(final_coeffs));
for (int i = 1; i <= max_segments + 1; ++i) {
ll num = poly_eval[i], den = 1;
for (int j = 1; j <= max_segments + 1; ++j) {
if (i != j) {
num = num * (MOD - j) % MOD;
den = den * (i - j + MOD) % MOD;
}
}
ll coeff = num * power(den, MOD - 2) % MOD;
vector<ll> poly(max_segments + 2, 0);
poly[0] = 1;
for (int j = 1; j <= max_segments + 1; ++j) {
if (i == j) continue;
for (int k = max_segments + 1; k > 0; --k) {
poly[k] = (poly[k] * (MOD - j) + poly[k - 1]) % MOD;
}
poly[0] = poly[0] * (MOD - j) % MOD;
}
for (int k = 1; k <= max_segments; ++k) {
final_coeffs[k] = (final_coeffs[k] + coeff * poly[k]) % MOD;
}
}
}
Técnicas Combinatórias e Matemáticas
Princípio da Inclusão-Exclusão e Nível Harmônico
Para calcular o número de arranjos onde o comprimento do segmento contínuo é limitado, aplicamos o Princípio da Inclusão-Exclusão. Enumeramos pelo menos i segmentos que excedem o limite. A complexidade é otimizada para uma série harmônica, pois i é limitado por \(\min(n-m+1, \frac{m}{k+1})\).
Algoritmo de Mo com Rollback
Para consultas de intervalos que exigem o maior segmento contínuo no domínio de valores, o Algoritmo de Mo com Rollback é ideal. Como a operação de união de intervalos não requer remoção, mantemos apenas as fronteiras esquerda e direita de cada componente conexo, atualizando-as em \(O(1)\) durante a fase de inserção, eliminando a necessidade de estruturas de dados com logaritmo.
Pilha Monótona e Consultas em Intervalos
Ao processar elementos para manter uma pilha onde cada elemento "vence" o próximo, o tamanho da pilha pode ser modleado por uma função recursiva. A resposta para um intervalo corresponde à posição do valor mínimo dessa função. Utilizando uma Árvore de Segmentos para adicionar valores em sufixos e consultar o mínimo em intervalos, o problema é resolvido eficientemente.