Dado o conjunto universo \( U = \{1, 2, \dots, n\} \), queremos determinar o número de subconjuntos \( S \subseteq U \) tais que todo inteiro de 1 a \( n \) pode ser expresso como a soma dos elementos de algum subconjunto \( T \subseteq S \). O resultado deve ser dado módulo \( M \), onde \( 1 \le n \le 5 \cdot 10^5 \) e \( 1 \le M \le 1.1 \times 10^9 \).
A condição sobre \( S \) parece complexa à primeira vista. No entanto, podemos derivar uma condição equivalente mais tratável. Um subconjunto \( S \) satisfaz a propriedade desejada se e somente se:
Suficiência: Suponha que a condição acima valha para todo \( k \). Vamos mostrar por indução que todo valor até \( n \) pode ser representado. Para \( k = 1 \), a condição implica que \( 1 \in S \). Agora, assuma que todos os valores menores que \( k \) podem ser representados. Seja \( p \) o menor inteiro tal que a soma dos elementos de \( S \cap [1, p] \) seja pelo menos \( k \). Defina \( \Delta = \left( \sum_{x \in S, x \le p} x \right) - k \). Como a soma acumulada em \( p-1 \) é menor que \( k \), temos \( \Delta < k \). Por hipótese indutiva, \( \Delta \) pode ser representado usando elementos \( \le p-1 \), logo removendo esses elementos da soma total até \( p \), obtemos exatamente \( k \).
Portanto, o problema se reduz a contar quantos subconjuntos \( S \subseteq U \) satisfazem:
Defina \( f_k \) como o número de subconjuntos \( S \) tais que a soma dos elementos \( \le k \) é exatamente \( k \), e para todo \( j < k \), a condição é satisfeita (ou seja, a soma até \( j \) é \( \ge j \)). Em particular, isso implica que a soma dos elementos \( \le k-1 \) é exatamente \( k-1 \), caso contrário a falha teria ocorrido antes.
Seja \( g_k \) o número de maneiras de escolher um subconjunto de inteiros distintos de \( [1, k] \) cuja soma seja \( k \). Isso é equivalente ao número de partições de \( k \) em partes distintas, um problema clássico.
Podemos calcular \( g_k \) eficientemente usando programação dinâmica com base na estrutura geométrica das partições. Representando uma partição como um diagrama de Ferrers, a transposição mostra que o número de partições de \( k \) com partes distintas é igual ao número de partições onde as alturas das colunas diminuem estritamente. Alternativamente, podemos pensar em termos do número de linhas de comprimento \( i \).
Observamos que o número de comprimentos de linha distintos em partições de \( k \) é \( O(\sqrt{k}) \), pois \( 1 + 2 + \cdots + m \approx m^2/2 \le k \Rightarrow m = O(\sqrt{k}) \). Isso permite uma otimização.
Seja \( B = \lfloor \sqrt{2n} \rfloor \). Podemos computar \( g \) iterando sobre comprimentos de linha \( i \) de \( B \) até 1, simulando um tipo de "pacote completo" mas apenas para linhas de comprimento fixo \( i \), garantindo que todas as partes sejam distintas:
g[0] = 1;
for (int i = B; i >= 1; i--) {
for (int j = n; j >= i; j--) {
g[j] = (g[j] + g[j - i]) % M;
}
}
No entanto, isso ainda conta partições com partes repetidas. A abordagem correta é ajustar o loop para refletir que cada parte aparece no máximo uma vez — o que já está implícito no fato de estarmos escolhendo subconjuntos. Assim, o loop acima está correto se interpretado como adicionar a opção de incluir \( i \) exatamente uma vez, mas devemos processar em ordem decrescente para evitar múltiplas inclusões.
Para computar \( f_k \), temos:
Assim, os elementos permitidos no trecho \( (j, k] \) são \( \ge j+2 \).
Podemos calcular \( f \) usando uma abordagem de divisão e conquista. Dividimos o intervalo \( [1, n] \) ao meio, calculamos \( f_j \) para \( j \le m \), e depois atualizamos \( f_i \) para \( i > m \) subtraindo as contribuições dos \( f_j \) via convolução com partições restritas a partes \( \ge j+2 \).
Seja \( h \) um array auxiliar. Para cada chamada recursiva no intervalo \( [l, r] \), primeiro resolvemos \( [l, m] \), depois computamos todas as contribuições de \( f_j \) (com \( j \in [l, m] \)) para \( f_i \) (com \( i \in [m+1, r] \)) onde a diferença \( i - j \) é preenchida com partes distintas \( \ge j+2 \).
O cálculo é feito com um laço semelhante ao de pacotes completos, mas limitado às partes \( \ge j+2 \). Como \( j \) varia, fazemos um loop externo sobre tamanhos de partes e acumulamos as contribuições ponderadas por \( f_j \).
void solve(int l, int r) {
if (l == r) {
f[l] = (g[l] - h[l] + M) % M;
return;
}
int m = (l + r) >> 1;
solve(l, m);
// Atualiza h[i] para i em [m+1, r] com contribuições de f[j], j em [l, m]
vector<long long> temp(n + 1);
for (int i = B; i >= 1; i--) {
for (int j = n; j >= i; j--) {
temp[j] = (temp[j] + temp[j - i]) % M;
}
// Adiciona f[j] * [partições de i-j com partes ≥ j+2]
for (int j = l; j <= min(m, n / i); j++) {
if (j + 2 <= i) { // condição mínima para poder usar parte i
temp[i] = (temp[i] + f[j]) % M;
}
}
}
for (int i = m + 1; i <= r; i++) {
h[i] = (h[i] + temp[i]) % M;
}
solve(m + 1, r);
}
A complexidade total é dominada pelas iterações sobre \( i \) de \( 1 \) a \( \sqrt{n} \) em cada nível da recursão. Como o tamanho do problema é dividido pela metade a cada nível, e o trabalho por nível é \( O(n \sqrt{n}) \), a recorrência é:
Após calcular \( f_n \), a resposta final é o número total de subconjuntos válidos, que é simplesmente a soma de todos os \( f_k \) para os quais a condição se mantém até \( n \), mas na verdade \( f_n \) já conta os subconjuntos cuja soma acumulada é exatamente \( n \) e todos os prefixos são críticos. A resposta completa é o complemento da união de falhas, mas como usamos inclusão-exclusão corretamente, o valor \( f_k \) representa exatamente os conjuntos que são válidos até \( k-1 \) e têm soma exata \( k \) em \( k \).
No entanto, o número total de subconjuntos válidos é simplesmente: