Problema P6754

Dado um intervalo \([a,b]\), determinar a quantidade de cadeias de dígitos com comprimento \(\geq 2\) que não são palíndromos.

Abordagem por Programação Dinâmica

Defina dp[pos][d1][d2] como a contagem de sequências de comprimento pos, onde d1 é o dígito mais significativo e d2 é o segundo dígito mais significativo, que respeitam a condição de não-palindromicidade.

A recorrência é construída adicionando um novo dígito à esquerda, garantindo que os três dígitos mais à esquerda sejam distintos entre si:

dp[i][j][k] = Σ dp[i-1][k][l], para l ∈ {0,...,9}, onde j≠k, j≠l, k≠l

Para responder consultas no intervalo \([a,b]\), utiliza-se a decomposição: resultado(b) - resultado(a-1). O tratamento dos limites é feito convertendo os valores para strings, facilitando a manipulação dígito a dígito.

Implementação

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;

char limite_sup[1010], limite_inf[1010];
ll tabela[1010][10][10];
int digitos[1010];

void precomputar() {
    for (int tam = 2; tam <= 1000; tam++) {
        for (int a = 0; a <= 9; a++) {
            for (int b = 0; b <= 9; b++) {
                if (a == b) continue;
                if (tam == 2) tabela[tam][a][b] = 1;
                for (int c = 0; c <= 9; c++) {
                    if (b != c && a != c) {
                        tabela[tam][a][b] += tabela[tam - 1][b][c];
                    }
                }
            }
        }
    }
}

ll contar_nao_palindromos(char valor[]) {
    bool valido = true;
    memset(digitos, 0, sizeof digitos);
    ll total = 0, acumulado = 0;
    int n = strlen(valor), ant1 = -1, ant2 = -1;

    for (int i = n; i >= 1; i--) {
        digitos[i] = valor[n - i] - '0';
        acumulado = acumulado * 10 + digitos[i];
    }
    acumulado++;
    total += 10;

    if (n == 1) return acumulado;

    // Somar cadeias de comprimentos intermediários
    for (int comp = 2; comp < n; comp++) {
        for (int d = 1; d <= 9; d++) {
            for (int e = 0; e <= 9; e++) {
                total += tabela[comp][d][e];
            }
        }
    }

    // Processar dígito a dígito para o comprimento exato
    for (int pos = n; pos >= 2; pos--) {
        for (int d = 0; d < digitos[pos]; d++) {
            if (pos == n && d == 0) continue;
            for (int e = 0; e <= 9; e++) {
                if (d != e && ant1 != e && ant1 != d && ant2 != d) {
                    total += tabela[pos][d][e];
                }
            }
        }
        if (ant1 == digitos[pos] || ant2 == digitos[pos]) {
            valido = false;
            break;
        }
        ant2 = ant1;
        ant1 = digitos[pos];
    }

    if (valido) {
        for (int d = 0; d <= digitos[1]; d++) {
            if (d != ant1 && d != ant2) total++;
        }
    }

    return total;
}

int main() {
    precomputar();
    cin >> limite_sup >> limite_inf;

    ll resposta = contar_nao_palindromos(limite_inf) - contar_nao_palindromos(limite_sup);
    int tam = strlen(limite_sup);
    bool eh_palindromo = false;

    for (int i = 1; i < tam; i++) {
        if (limite_sup[i] == limite_sup[i - 1] || (i > 1 && limite_sup[i] == limite_sup[i - 2])) {
            eh_palindromo = true;
            break;
        }
    }

    if (!eh_palindromo) resposta++;
    printf("%lld\n", resposta);
    return 0;
}

Problema P3413

Enunciado idêntico ao anteroir, porém com módulo \(10^9 + 7\) nas operações aritméticas.

Invertendo a Perspectiva

Em vez de contar diretamente as cadeias não-palindrômicas, podemos calcular o total de cadeias válidas e subtrair aquelas que são palíndromos. Essa mudança simplifica a lógica em alguns cenários.

O total de cadeias de comprimento \(k\) sem zeros à esquerda é \(9 \times 10^{k-1}\). A contagem de palíndromos segue uma lógica recursiva semelhante, mas verificando simetria nas extremidades.

Implementação com Módulo

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;

char faixa_a[1010], faixa_b[1010];
ll memo[1010][10][10];
int seq[1010];

void inicializar() {
    for (int tam = 2; tam <= 1000; tam++) {
        for (int x = 0; x <= 9; x++) {
            for (int y = 0; y <= 9; y++) {
                if (x == y) continue;
                if (tam == 2) memo[tam][x][y] = 1;
                for (int z = 0; z <= 9; z++) {
                    if (y != z && x != z) {
                        memo[tam][x][y] = (memo[tam][x][y] + memo[tam - 1][y][z]) % MOD;
                    }
                }
            }
        }
    }
}

ll resolver(char texto[]) {
    bool ok = true;
    memset(seq, 0, sizeof seq);
    ll palind = 0, soma_total = 0;
    int comp = strlen(texto), prev1 = -1, prev2 = -1;

    for (int idx = comp; idx >= 1; idx--) {
        seq[idx] = texto[comp - idx] - '0';
        soma_total = (soma_total * 10 + seq[idx]) % MOD;
    }
    soma_total++;
    palind += 10;

    if (comp == 1) return 0;

    for (int k = 2; k < comp; k++) {
        for (int d1 = 1; d1 <= 9; d1++) {
            for (int d2 = 0; d2 <= 9; d2++) {
                palind = (palind + memo[k][d1][d2]) % MOD;
            }
        }
    }

    for (int pos = comp; pos >= 2; pos--) {
        for (int d = 0; d < seq[pos]; d++) {
            if (pos == comp && d == 0) continue;
            for (int e = 0; e <= 9; e++) {
                if (d != e && prev1 != e && prev1 != d && prev2 != d) {
                    palind = (palind + memo[pos][d][e]) % MOD;
                }
            }
        }
        if (prev1 == seq[pos] || prev2 == seq[pos]) {
            ok = false;
            break;
        }
        prev2 = prev1;
        prev1 = seq[pos];
    }

    if (ok) {
        for (int d = 0; d <= seq[1]; d++) {
            if (d != prev1 && d != prev2) palind = (palind + 1) % MOD;
        }
    }

    return (soma_total - palind + MOD) % MOD;
}

int main() {
    inicializar();
    cin >> faixa_a >> faixa_b;

    int tam = strlen(faixa_a);
    ll resultado = (resolver(faixa_b) - resolver(faixa_a) + MOD) % MOD;

    for (int i = 1; i < tam; i++) {
        if (faixa_a[i] == faixa_a[i - 1] || (i > 1 && faixa_a[i] == faixa_a[i - 2])) {
            resultado = (resultado + 1) % MOD;
            break;
        }
    }

    printf("%lld\n", (resultado + MOD) % MOD);
    return 0;
}

Observações Técnicas

A chave para ambos os problemas reside no tratamento correto dos limites do intervalo. Converter os números para representação em string permite uma iteração dígito a dígito, essencial para a técnica de digit DP. Os estados anteriores (prev1, prev2) rastreiam os dígitos já posicionados para verificar a propiredade de não-palindromicidade incrementalmente.