Séries de Potência sobre Conjuntos

Conceito Básico

Considere um conjunto universo \(U = \{1, 2, \ldots, n\}\) e \(2^U\) como sua coleção de subconjuntos. Dada uma função \(f : 2^U \rightarrow \mathbb{R}\), a série de potência sobre conjuntos relacionada é definida como:

Operações Elementares

A adição segue o comportamento usual de séries de potência, com coeficientes somados de forma direta. A multiplicação, contudo, exige que coeficientes sejam multiplicados e índices combinados através de operações binárias (\(\oplus\)):

Em situações práticas, estados são frequentemente expressos em representação binária, dando destaque à convolução por operações bit-a-bit como cenário aplicável.

Operações sobre Subconjuntos

Somas e Diferenças Multidimensionais

Somas sobre superconjuntos ou subconjuntos podem ser computadas de forma eficiente. A versão para prefixos (subconjuntos) obedece ao algoritmo:

// Soma para subconjuntos
for(int bit = 0; bit < n; bit++) {
    for(int mask = 0; mask < (1 << n); mask++) {
        if(mask & (1 << bit)) sum[mask] += sum[mask ^ (1 << bit)];
    }
}

// Soma para superconjuntos
for(int bit = 0; bit < n; bit++) {
    for(int mask = 0; mask < (1 << n); mask++) {
        if(!(mask & (1 << bit))) sum[mask] += sum[mask | (1 << bit)];
    }
}

As operações inversas (diferenças) seguem uma adaptação semelhente:

// Subtração para subconjuntos
for(int bit = 0; bit < n; bit++) {
    for(int mask = 0; mask < (1 << n); mask++) {
        if(mask & (1 << bit)) diff[mask] -= diff[mask ^ (1 << bit)];
    }
}

// Subtração para superconjuntos
for(int bit = 0; bit < n; bit++) {
    for(int mask = 0; mask < (1 << n); mask++) {
        if(!(mask & (1 << bit))) diff[mask] -= diff[mask | (1 << bit)];
    }
}

Transformação Rápida de Möbius (FMT)

Convolução OU (União)

Define-se \(\widehat{f}_S = \sum_{T \subseteq S} f_T\). A convolução para união é dada por \(\widehat{h}_S = \widehat{f}_S \cdot \widehat{g}_S\), seguida da FMT inversa (FMI).

Convolução E (Interseção)

Para interseção, itera-se sobre superconjuntos: \(\widehat{f}_S = \sum_{S \subseteq T} f_T\), resultando em \(\widehat{h}_S = \widehat{f}_S \cdot \widehat{g}_S\).

int modulo = 1000000007;

void aplicar_FMT_OU(int* arranjo, int sinal) {
    for(int bit = 0; bit < n; bit++) {
        for(int mask = 0; mask < (1 << n); mask++) {
            if(mask & (1 << bit)) 
                arranjo[mask] = (arranjo[mask] + sinal * arranjo[mask ^ (1 << bit)]) % modulo;
        }
    }
}

void aplicar_FMT_E(int* arranjo, int sinal) {
    for(int bit = 0; bit < n; bit++) {
        for(int mask = 0; mask < (1 << n); mask++) {
            if(!(mask & (1 << bit))) 
                arranjo[mask] = (arranjo[mask] + sinal * arranjo[mask | (1 << bit)]) % modulo;
        }
    }
}

Transformação Rápida de Walsh (FWT)

Convolução XOR (Diferença Simétrica)

A transformação é explicitada na forma:

void transformar_FWT_XOR(int* arranjo, bool inverso) {
    int dimensao = 1 << n;
    for(int delta = 1; delta < dimensao; delta *= 2) {
        for(int idx = 0; idx < dimensao; idx += 2 * delta) {
            for(int k = 0; k < delta; k++) {
                int a = arranjo[idx + k];
                int b = arranjo[idx + delta + k];
                arranjo[idx + k] = (a + b) % modulo;
                arranjo[idx + delta + k] = (a - b + modulo) % modulo;
            }
        }
    }
    if(inverso) {
        int factor_inverso = potencia_modular(1 << n, modulo - 2, modulo);
        for(int idx = 0; idx < dimensao; idx++) {
            arranjo[idx] = 1LL * arranjo[idx] * factor_inverso % modulo;
        }
    }
}

Convolução Limitada por Cardinalidade

Introduz-se a condição adicional \(|A| + |B| = |C|\) para sbuconjuntos disjuntos na operação:

int contar_bits(int valor) {
    return __builtin_popcount(valor);
}

void convolucionar_subconjunto() {
    int padrao_max = (1 << n);
    for(int i = 0; i <= n; i++) {
        aplicar_FMT_OU(arranjo_F[i], 1);
        aplicar_FMT_OU(arranjo_G[i], 1);
    }
    for(int soma_cards = 0; soma_cards <= n; soma_cards++) {
        for(int mask = 0; mask < padrao_max; mask++) {
            for(int card_A = 0; card_A <= soma_cards; card_A++) {
                int card_B = soma_cards - card_A;
                arranjo_H[soma_cards][mask] = (arranjo_H[soma_cards][mask] + 
                    1LL * arranjo_F[card_A][mask] * arranjo_G[card_B][mask]) % modulo;
            }
        }
    }
    for(int i = 0; i <= n; i++) {
        aplicar_FMT_OU(arranjo_H[i], -1);
    }
}