Conceito Fundamental

A ideia principal é processar um número de dígito em dígito, da esquerda para a direita, mantendo um estado que capture a informação relevante do prefixo já processado. Geralmente, usamos uma matriz dp[pos][state] que armazena a contagem de números válidos com pos dígitos já determinados e uma configuração específica de state (por exemplo, soma dos dígitos, último dígito, um bitmask de propriedades).

Problema 1: Contagem em uma Base B com Restrições de Dígito

Este problema pede para contar números no intervalo [L, R] cuja representação em base B contém exatamente K dígitos iguais a 1, e todos os outros dígitos são 0. Primeiro, pré-cmoputamos os coeficientes binomiais usando DP.

#include <bits/stdc++.h>
using namespace std;
const int MAX_DIGITS = 35;

int comb[MAX_DIGITS][MAX_DIGITS];
int base, target_k;

void precompute_combinations() {
    for (int n = 0; n < MAX_DIGITS; ++n) {
        for (int m = 0; m <= n; ++m) {
            if (m == 0) comb[n][m] = 1;
            else comb[n][m] = comb[n-1][m] + comb[n-1][m-1];
        }
    }
}

int count_valid_upto(int limit) {
    if (limit == 0) return 0;
    vector<int> digits;
    int temp = limit;
    while (temp > 0) {
        digits.push_back(temp % base);
        temp /= base;
    }
    int result = 0;
    int ones_used = 0;
    for (int i = digits.size() - 1; i >= 0; --i) {
        int current_digit = digits[i];
        if (current_digit > 0) {
            // Opção 1: Colocar 0 no dígito atual e escolher os dígitos restantes.
            int remaining_positions = i;
            int ones_needed = target_k - ones_used;
            if (ones_needed >= 0)
                result += comb[remaining_positions][ones_needed];

            // Opção 2: Se current_digit > 1, podemos colocar 1 aqui.
            if (current_digit > 1) {
                if (target_k - ones_used - 1 >= 0)
                    result += comb[i][target_k - ones_used - 1];
                break; // Dígitos maiores que 1 não são permitidos.
            }
            // Se current_digit == 1, seguir o caminho restrito.
            if (current_digit == 1) {
                ++ones_used;
                if (ones_used > target_k) break;
            }
        }
        // Verificação final no último dígito.
        if (i == 0 && ones_used == target_k) ++result;
    }
    return result;
}

int main() {
    precompute_combinations();
    int l, r;
    cin >> l >> r >> target_k >> base;
    cout << count_valid_upto(r) - count_valid_upto(l - 1) << endl;
    return 0;
}

Problema 2: Sequência Não Decrescente de Dígitos

Contar números onde os dígitos, da esquerda para a direita, formam uma sequência não decrescente (ex: 1233, 455, 7899). Pré-computamos a quantidade de números válidos de um certo tamanho com um certo dígito mais significativo.

#include <iostream>
#include <vector>
using namespace std;
const int MAX_LEN = 15;

int dp_table[MAX_LEN][10]; // dp_table[comprimento][primeiro_dígito]

void precompute_non_decreasing() {
    for (int d = 0; d <= 9; ++d) dp_table[1][d] = 1;
    for (int len = 2; len < MAX_LEN; ++len) {
        for (int first_digit = 0; first_digit <= 9; ++first_digit) {
            for (int next_digit = first_digit; next_digit <= 9; ++next_digit) {
                dp_table[len][first_digit] += dp_table[len-1][next_digit];
            }
        }
    }
}

int count_upto(int num) {
    if (num == 0) return 1;
    vector<int> digits;
    while (num > 0) {
        digits.push_back(num % 10);
        num /= 10;
    }
    int total = 0;
    int prev_digit = 0;
    for (int i = digits.size() - 1; i >= 0; --i) {
        int curr_digit = digits[i];
        for (int d = prev_digit; d < curr_digit; ++d) {
            total += dp_table[i+1][d];
        }
        if (curr_digit < prev_digit) break; // Sequência inválida encontrada.
        prev_digit = curr_digit;
        if (i == 0) ++total; // O próprio número é válido.
    }
    return total;
}

int main() {
    precompute_non_decreasing();
    int l, r;
    while (cin >> l >> r) {
        cout << count_upto(r) - count_upto(l - 1) << endl;
    }
    return 0;
}

Problema 3: Diferença Mínima Entre Dígitos Adjacentes (Windy Number)

Um número é considerado "windy" se a diferença absoluta entre quaisquer dois dígitos adjacantes é pelo menos 2. Devemos tratar números com menos dígitos (com zeros à esquerda) separadamente.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int MAX_LEN = 11;

int f[MAX_LEN][10]; // f[comprimento][dígito_mais_significativo]

void precompute_windy() {
    for (int d = 0; d <= 9; ++d) f[1][d] = 1;
    for (int len = 2; len < MAX_LEN; ++len) {
        for (int msd = 0; msd <= 9; ++msd) {
            for (int next = 0; next <= 9; ++next) {
                if (abs(msd - next) >= 2) {
                    f[len][msd] += f[len-1][next];
                }
            }
        }
    }
}

int count_windy_upto(int limit) {
    if (limit == 0) return 0;
    vector<int> digits;
    while (limit > 0) {
        digits.push_back(limit % 10);
        limit /= 10;
    }
    int ans = 0;
    int last_digit = -2; // Valor inicial impossível.
    for (int i = digits.size() - 1; i >= 0; --i) {
        int curr = digits[i];
        int start = (i == digits.size() - 1) ? 1 : 0; // O primeiro dígito não pode ser 0.
        for (int d = start; d < curr; ++d) {
            if (abs(d - last_digit) >= 2) {
                ans += f[i+1][d];
            }
        }
        if (abs(curr - last_digit) >= 2) {
            last_digit = curr;
        } else {
            break;
        }
        if (i == 0) ++ans; // O número original é válido.
    }
    // Adiciona números com menos dígitos (preenchidos com zeros à esquerda).
    for (int len = 1; len < (int)digits.size(); ++len) {
        for (int msd = 1; msd <= 9; ++msd) {
            ans += f[len][msd];
        }
    }
    return ans;
}

int main() {
    precompute_windy();
    int l, r;
    cin >> l >> r;
    cout << count_windy_upto(r) - count_windy_upto(l - 1) << endl;
    return 0;
}

Problema 4: Soma dos Dígitos Módulo P

Contar números onde a soma de seus dígitos é divisível por um dado P. A DP pré-computada considera o comprimento, o dígito atual e o resto atual da soma.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_DIGITS = 11, MAX_MOD = 110;

int P;
int cnt[MAX_DIGITS][10][MAX_MOD]; // cnt[restante_dígitos][dígito_atual][soma_mod_P]

int modulo(int x, int m) {
    return ((x % m) + m) % m;
}

void precompute_sum_mod() {
    memset(cnt, 0, sizeof(cnt));
    for (int d = 0; d <= 9; ++d) {
        cnt[1][d][d % P]++;
    }
    for (int rem_digits = 2; rem_digits < MAX_DIGITS; ++rem_digits) {
        for (int cur_d = 0; cur_d <= 9; ++cur_d) {
            for (int target_sum_mod = 0; target_sum_mod < P; ++target_sum_mod) {
                for (int next_d = 0; next_d <= 9; ++next_d) {
                    cnt[rem_digits][cur_d][target_sum_mod] += cnt[rem_digits-1][next_d][modulo(target_sum_mod - cur_d, P)];
                }
            }
        }
    }
}

int count_divisible_upto(int num) {
    if (num == 0) return 1;
    vector<int> digits;
    while (num > 0) {
        digits.push_back(num % 10);
        num /= 10;
    }
    int res = 0;
    int current_sum = 0;
    for (int i = digits.size() - 1; i >= 0; --i) {
        int x = digits[i];
        for (int d = 0; d < x; ++d) {
            res += cnt[i+1][d][modulo(-current_sum, P)];
        }
        current_sum += x;
        if (i == 0 && current_sum % P == 0) res++; // Inclui o próprio número se for válido.
    }
    return res;
}

int main() {
    int l, r;
    while (cin >> l >> r >> P) {
        precompute_sum_mod();
        cout << count_divisible_upto(r) - count_divisible_upto(l - 1) << endl;
    }
    return 0;
}

Problema 5: Evitando o Dígito 4 e a Sequência "62"

Contar números que não contêm o dígito 4 e não contêm a subsequência "62" (um 6 seguido por um 2). A DP pré-comuptada leva em conta o dígito anterior para a verificação da sequência proibida.

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAX_DIGITS = 35;

int valid_count[MAX_DIGITS][10]; // valid_count[posições_restantes][último_dígito]

void precompute_no62() {
    memset(valid_count, 0, sizeof(valid_count));
    for (int d = 0; d <= 9; ++d) {
        if (d != 4) valid_count[1][d] = 1;
    }
    for (int remaining = 1; remaining < MAX_DIGITS; ++remaining) {
        for (int prev_digit = 0; prev_digit <= 9; ++prev_digit) {
            if (prev_digit == 4) continue;
            for (int next_digit = 0; next_digit <= 9; ++next_digit) {
                if (next_digit == 4) continue;
                if (prev_digit == 6 && next_digit == 2) continue;
                valid_count[remaining][prev_digit] += valid_count[remaining-1][next_digit];
            }
        }
    }
}

int count_safe_upto(int limit) {
    if (limit == 0) return 1;
    vector<int> digits;
    while (limit > 0) {
        digits.push_back(limit % 10);
        limit /= 10;
    }
    int total = 0;
    int last_digit = 0;
    for (int i = digits.size() - 1; i >= 0; --i) {
        int current = digits[i];
        for (int d = 0; d < current; ++d) {
            if (d == 4) continue;
            if (last_digit == 6 && d == 2) continue;
            total += valid_count[i+1][d];
        }
        if (current == 4 || (last_digit == 6 && current == 2)) {
            break; // O caminho restrito (direita) se torna inválido.
        }
        last_digit = current;
        if (i == 0) total++; // O próprio número é válido.
    }
    return total;
}

int main() {
    precompute_no62();
    int l, r;
    while (cin >> l >> r, l || r) {
        cout << count_safe_upto(r) - count_safe_upto(l - 1) << endl;
    }
    return 0;
}