La programmation dynamique sur les chiffres permet d'exploiter la structure des nombres pour compter ou vérifier des propriétés sur des plages de valeurs. L'idée principale est de traiter les nombres chiffre par chiffre, souvent en partent du chiffre de poids fort.
Comptage des occurrences de chiffres dans un intervalle
Problème : Étant donné deux entiers a et b, déterminer combien de fois chaque chiffre (de 0 à 9) apparaît dans tous les entiers de l'intervalle [a, b] (inclus).
Contraintes : 1 ≤ a ≤ b ≤ 1012.
Solution par construction progressive
On peut calculer le nombre d'occurrences pour une plage [0, N] puis en soustraire les résultats. Soit f(x) le vecteur des occurrences pour l'intervalle [0, x]. La réponse est alors f(b) - f(a-1).
On définit deux séquences utiles :
power[i]= 10icount[i]= nombre d'occurrences de chaque chiffre dans tous les nombres à i chiffres (avec les zéros en tête). Par exemple, pouri=2, les nombres de 00 à 99 contiennent chaque chiffre 20 fois.
La relation de récurrence est : count[i] = i * 10<sup>i-1</sup>.
Pour évaluer f(x), on décompose les chiffres de x. Pour chaque position, on ajoute les contributions des blocs complets et gère le chiffre courant.
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAX_DIGITS = 15;
ll power[MAX_DIGITS], occurrences[MAX_DIGITS];
void init_tables() {
power[0] = 1;
for (int i = 1; i < MAX_DIGITS; ++i) {
power[i] = power[i-1] * 10;
occurrences[i] = i * power[i-1];
}
}
vector<ll> count_up_to(ll limit) {
vector<ll> result(10, 0);
if (limit == 0) return result;
int len = 0;
ll temp = limit;
int digits[MAX_DIGITS];
while (temp > 0) {
digits[len++] = temp % 10;
temp /= 10;
}
for (int pos = len-1; pos >= 0; --pos) {
int d = digits[pos];
// Contributions from complete blocks
for (int k = 0; k <= 9; ++k) {
result[k] += d * occurrences[pos];
}
// Additional occurrences from the current digit's position
for (int k = 0; k < d; ++k) {
result[k] += power[pos];
}
// Contribution from the suffix
ll suffix = 0;
for (int j = pos-1; j >= 0; --j) {
suffix = suffix * 10 + digits[j];
}
result[d] += suffix + 1;
// Correction for leading zeros
result[0] -= power[pos];
}
return result;
}
int main() {
init_tables();
ll a, b;
scanf("%lld %lld", &a, &b);
auto upper = count_up_to(b);
auto lower = count_up_to(a-1);
for (int i = 0; i < 10; ++i) {
printf("%lld ", upper[i] - lower[i]);
}
return 0;
}
Solution par recherche mémorisée
Une approche alternative utilise la récursion avec mémorisation. On définit un état comprenant :
pos: position actuelle (du poids fort au poids faible)sum: nombre d'occurrences du chiffre cible jusqu'icitight: si la construction est contrainte par le chiffre delimità cette positionstarted: si on a déjà placé un chiffre non nul
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll memo[MAX_DIGITS][MAX_DIGITS][2][2];
int target_digit, limit_digits[MAX_DIGITS];
ll dfs(int pos, int count, bool tight, bool started) {
if (pos == -1) return count;
if (memo[pos][count][tight][started] != -1) {
return memo[pos][count][tight][started];
}
int upper_bound = tight ? limit_digits[pos] : 9;
ll res = 0;
for (int d = 0; d <= upper_bound; ++d) {
bool new_tight = tight && (d == upper_bound);
bool new_started = started || (d != 0);
if (started || d != 0) {
res += dfs(pos-1, count + (d == target_digit), new_tight, new_started);
} else {
res += dfs(pos-1, count, new_tight, false);
}
}
return memo[pos][count][tight][started] = res;
}
ll count_for_digit(ll number, int digit) {
target_digit = digit;
int len = 0;
ll tmp = number;
while (tmp) {
limit_digits[len++] = tmp % 10;
tmp /= 10;
}
if (number == 0) {
limit_digits[0] = 0;
len = 1;
}
memset(memo, -1, sizeof(memo));
return dfs(len-1, 0, true, false);
}
int main() {
ll a, b;
scanf("%lld %lld", &a, &b);
for (int d = 0; d <= 9; ++d) {
ll ans = count_for_digit(b, d) - count_for_digit(a-1, d);
printf("%lld ", ans);
}
return 0;
}
Problèmes d'addition des chiffres
Certains problèmes requièrent de vérifier des conditions sur la somme des chiffres. Par exemple, trouver les nombres dont la somme des chiffres divise le nombre lui-même.
On peut adapter la DP pour suivre à la fois la somme et le reste modulo une valeur donnée.
Exemple : Distribution similaire (AHOI2009)
Problème : Compter les nombres dans [a, b] dont la somme des chiffres divise le nombre.
Solution : On itère sur toutes les sommes possibles (de 1 à 9*18 pour des nombres à 18 chiffres). Pour chaque somme candidate s, on vérifie si la somme des chiffres est exactement s et si le nombre modulo s vaut 0.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int target_sum;
int number_digits[MAX_DIGITS];
ll memo[MAX_DIGITS][200][200][2];
ll solve(int pos, int current_sum, int remainder, bool tight) {
if (pos == -1) {
return (current_sum == target_sum) && (remainder == 0);
}
if (memo[pos][current_sum][remainder][tight] != -1) {
return memo[pos][current_sum][remainder][tight];
}
int limit = tight ? number_digits[pos] : 9;
ll total = 0;
for (int d = 0; d <= limit; ++d) {
bool new_tight = tight && (d == limit);
total += solve(pos-1,
current_sum + d,
(remainder * 10 + d) % target_sum,
new_tight);
}
return memo[pos][current_sum][remainder][tight] = total;
}
ll count_until(ll number) {
int len = 0;
ll tmp = number;
while (tmp) {
number_digits[len++] = tmp % 10;
tmp /= 10;
}
if (number == 0) number_digits[0] = 0, len = 1;
ll result = 0;
for (target_sum = 1; target_sum <= 9 * len; ++target_sum) {
memset(memo, -1, sizeof(memo));
result += solve(len-1, 0, 0, true);
}
return result;
}
int main() {
ll a, b;
scanf("%lld %lld", &a, &b);
ll upper = count_until(b);
ll lower = count_until(a-1);
printf("%lld\n", upper - lower);
return 0;
}
Nombres de Windy
Un nombre de Windy est un entier positif sans zéros en tête où la différence absolue entre deux chiffres consécutifs est au moins 2.
Solution par DP
On ajoute un paramètre supplémentaire last_digit à l'état pour contrôler la contrainte de différence. De plus, on gère explicitement les zéros en tête.
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
int limit_digits[MAX_DIGITS];
ll memo[MAX_DIGITS][12][2][2]; // position, dernier chiffre, started, tight
ll count_windy(int pos, int last, bool started, bool tight) {
if (pos == -1) return 1;
if (last != -1 && memo[pos][last][started][tight] != -1) {
return memo[pos][last][started][tight];
}
int upper = tight ? limit_digits[pos] : 9;
ll res = 0;
for (int d = 0; d <= upper; ++d) {
bool new_tight = tight && (d == upper);
bool new_started = started || (d != 0);
if (new_started) {
if (last == -1 || abs(d - last) >= 2) {
res += count_windy(pos-1, d, true, new_tight);
}
} else {
res += count_windy(pos-1, -1, false, new_tight);
}
}
return memo[pos][last][started][tight] = res;
}
ll solve(ll number) {
int len = 0;
ll tmp = number;
while (tmp) {
limit_digits[len++] = tmp % 10;
tmp /= 10;
}
if (number == 0) {
limit_digits[0] = 0;
len = 1;
}
memset(memo, -1, sizeof(memo));
return count_windy(len-1, -1, false, true);
}
int main() {
ll a, b;
scanf("%lld %lld", &a, &b);
printf("%lld\n", solve(b) - solve(a-1));
return 0;
}