---
tags: dp, digits
---
# DP de dígitos
Es una técnica que nos permite resolver preguntas del tipo: ¿cuántos enteros positivos hay en el rango $[L, R]$ tal que cumplen alguna propiedad, o cuántas veces aparece esa propiedad entre todos los dígitos combinados en el rango? Dicha propiedad estará relacionada de alguna manera con los dígitos de dichos números.
Normalmente estaremos usando una función $f(n)$ que nos dirá la respuesta para la propiedad, considerando todos los enteros positivos que no excedan $n$. Entonces, para saber el número de números en $[L, R]$ que cumplen, simplemente vamos a calcular $f(R) - f(L-1)$.
Para calcular $f(n)$ vamos a auxiliarnos de otra función $dp(pos, canUseAll, \ldots)$. En esta función vamos a ir construyendo los números que cumplen con la propiedad deseada, dígito a dígito, comenzando desde el más significativo. De forma más específica, sea $n=\overline{n_0 n_1 \cdots n_{l-1}}$ representado dígito a dígito, y supongamos que estamos construyendo un número $x = \overline{d_0 d_1 \cdots d_{l-1}}$ también con $l$ dígitos, donde el orden de colocar los dígitos comienza en $d_0$ y termina en $d_{l-1}$. Los argumentos son:
- $pos$: este argumento nos va a decir en qué posición del número estamos actualmente, de izquierda a derecha. Es decir, estamos colocando el dígito $d_{pos}$.
- $canUseAll$: este es un valor booleano que nos dice si en la posición actual podemos colocar cualquier dígito entre 0 y 9, o solo entre 0 y el dígito en la posición actual de $n$. Por ejemplo, supongamos que $n=527$ y estamos en $pos=0$, entonces solo podemos colocar dígitos entre el 0 y el 5.
- Argumentos para la información de los números construidos hasta el momento: puede ser la suma de dígitos al momento, el conteo de algún dígito, etc, dependiendo de la propiedad deseada.
Entonces $dp(pos, \ldots)$ nos dirá la respuesta para la propiedad deseada, considerando números no mayores a $n$ y que se comenzaron a construir desde la posición $pos$, tomando el cuenta los argumentos adicionales.
Las transiciones tienen esta forma muy general:
$$
limit =\begin{cases}
9 &\mbox{si $canUseAll == true$} \\
n_{pos} &\mbox{si $canUseAll == false$}
\end{cases}
$$
$$
dp(pos, canUseAll, \ldots) = \sum_{d=0}^{limit} dp(pos+1, canUseAll || d < limit, \ldots)
$$
Para mandar llamar a la DP usamos $f(n) = dp(0, false, \ldots)$, y los casos base dependerán del problema, pero siempre se dan cuando ya construimos todo el número $x$, es decir, cuando $pos = l$.
La magia de este tipo de programación dinámica radica en que no necesitamos guardar cada secuencia de dígitos que vamos construyendo, solo cierta información referente a ellas en los argumentos adicionales.
Y además notemos que los números construidos pueden contener ceros a la izquierda. Esto puede o no ocasionar algunas consideraciones adicionales, dependiendo del problema.
## Problema: suma de dígitos
Dados $L$ y $R$, hallar la suma de dígitos de todos los números entre $L$ y $R$.
Ejemplo: si $L=34$ y $R=37$, la respuesta debe ser $3+4 + 3+5 + 3+6 + 3+7 = 7 + 8 + 9 + 10 = 34$.
Sea $f(n)$ la suma de dígitos de todos los números positivos hasta $n$. Entonces, $dp(pos, canUseAll, sum)$ nos va a decir la suma deseada, solo considerando números construidos desde la posisión $pos$, guardando en $sum$ la suma de la secuencia de dígitos actual.
Entonces:
$$
dp(pos, canUseAll, sum) = \sum_{d=0}^{limit} dp(pos+1, canUseAll || d < limit, sum + d)
$$
La mandamos llamar como: $f(n) = dp(0, false, 0)$
Y el caso base es: $dp(l, canUseAll, sum) = sum$
El código completo queda como:
```cpp
#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;
lli mem[17][2][150];
lli dp(int pos, bool canUseAll, int sum, const vector<int> & digits_n){
if(pos == digits_n.size()){
return sum;
}
lli & ans = mem[pos][canUseAll][sum];
if(ans != -1) return ans;
ans = 0;
int limit = canUseAll ? 9 : digits_n[pos];
for(int d = 0; d <= limit; ++d){
ans += dp(pos + 1, canUseAll | d < limit, sum + d, digits_n);
}
return ans;
}
lli f(lli n){
if(n <= 0) return 0;
vector<int> digits_n;
while(n > 0){
digits_n.push_back(n % 10);
n /= 10;
}
reverse(digits_n.begin(), digits_n.end());
memset(mem, -1, sizeof(mem));
return dp(0, false, 0, digits_n);
}
int main(){
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while(t--){
lli a, b;
cin >> a >> b;
lli ans = f(b) - f(a-1);
cout << ans << "\n";
}
return 0;
}
```
Si asumimos que $0 \leq L \leq R \leq 10^{15}$, entonces la complejidad en tiempo es $O(\log_{10}(R) * 2 * 9 * \log_{10}(R) * 10) = O(180 \log_{10}^2(R))$ y en memoria es $O(18 \log_{10}^2(R))$.
## Problema: Contar cuántas veces aparece un dígito $e$
Dados $L$ y $R$, hallar cuántas veces aparece el dígito $e$ ($1 \leq e \leq 9$) en todos los números entre $L$ y $R$.
Sea $f(n)$ el conteo de las veces que aparece el dígito $e$ en todos los números positivos que no exceden $n$.
Sea $dp(pos, canUseAll, freq)$ dicho conteo, solo considerando los números construidos desde la posición $pos$, guardando en $freq$ la frecuencia del dígito $e$.
Entonces:
$$
dp(pos, canUseAll, freq) = \sum_{d=0}^{limit} dp(pos+1, canUseAll || d < limit, freq + (d == e))
$$
La mandamos llamar como: $f(n) = dp(0, false, 0)$
Y el caso base es: $dp(l, canUseAll, freq) = freq$
## Problema: Contar cuántos números contienen al menos una vez el dígito $e$
Dados $L$ y $R$, contar cuántos números contienen al dígito $e$ ($0 \leq e \leq 9$) al menos una vez en el rango $[L, R]$.
La idea anterior falla porque ahora estamos considerando al dígito $0$, y la forma en la que construímos los números puede agregar ceros a la izquierda, los cuales no nos sirven para el conteo.
Una solución posible es agregar otra bandera que nos diga si el cero que coloquemos aporta al conteo o no, es decir, si este cero forma parte del prefijo de ceros.
Entonces:
$$
dp(pos, canUseAll, hasPrefixOfZeros, appears) = \sum_{d=0}^{limit} dp(pos+1, canUseAll || d < limit, hasPrefixOfZeros \& (d == 0), appears | newAppearance)
$$
donde:
$$
newAppearance = \begin{cases}
d == e &\mbox{si $d > 0$} \\
(d == e) \& (!hasPrefixOfZeros) &\mbox{si $d == 0$}
\end{cases}
$$
La mandamos llamar como: $f(n) = dp(0, false, true, false)$
Y el caso base es: $dp(l, canUseAll, hasPrefixOfZeros, appears) = appears$.
## Problema: Números cuya diferencia de dígitos adyacentes no excede 2
Dado un conjunto $S$ de dígitos del 1 al 9 y un entero positivo $n$ ($1 \leq n \leq 10$), hallar cuántos enteros positivos de exactamente $n$ dígitos contienen solo dígitos de $S$ y la diferencia entre sus dígitos adyacentes no excede 2.
En problemas como estos en donde no estamos limitados a contar en un rango $[L, R]$, sino que queremos construir números con una cantidad de dígitos dada, podemos evitar el uso de la bandera $canUseAll$ y de la variable $limit$, pues no tenemos ningún límite para colocar los dígitos.
Sea $f(n)$ la respuesta y sea $dp(pos, lastDigit)$ la respuesta solo considerando los números construidos desde la posición $pos$ guardando el dígito anterior colocado en $lastDigit$. Ese argumento nos sirve para comparar los dígitos adyacentes: el anterior y el actual.
Entonces:
$$
dp(pos, lastDigit) = \sum_{\substack{d \in S \\ (pos == 0) || (\lvert d - lastDigit | \leq 2)}} dp(pos + 1, d)
$$
Es decir, solo iteramos por los dígitos del conjunto $S$ cuya diferencia con el dígito anterior sea menor o igual a 2. Notemos que cuando $pos=0$, podemos colocar cualquier dígito de $S$, pues no hay dígito anterior al primero.
La mandamos llamar como: $f(n) = dp(0, 0)$
Y el caso base es: $dp(n, lastDigit) = 1$
El código de dicha idea queda como:
```cpp
#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;
lli mem[15][10];
lli dp(int pos, int last_digit, int n, const vector<int> & allowed){
if(pos == n){
return 1;
}
lli & ans = mem[pos][last_digit];
if(ans != -1) return ans;
ans = 0;
for(int d : allowed){
if(pos == 0 || abs(d - last_digit) <= 2){
ans += dp(pos + 1, d, n, allowed);
}
}
return ans;
}
lli f(int n, const vector<int> & allowed){
memset(mem, -1, sizeof(mem));
return dp(0, 0, n, allowed);
}
int main(){
int t;
cin >> t;
for(int c = 1; c <= t; ++c){
int m, n;
cin >> m >> n;
vector<int> allowed(m);
for(int & di : allowed){
cin >> di;
}
cout << "Case " << c << ": " << f(n, allowed) << "\n";
}
return 0;
}
```
Preguntas:
- ¿Qué pasa si el dígito 0 también podría estar incluido en $S$?
- ¿Qué cambios habría que hacer si queremos saber cuántos números con **a lo más** $n$ dígitos cumplen con la propiedad?
- ¿Qué cambios habría que hacer para considerar ambas cuestiones al mismo tiempo?
Para la primer cuestión podemos auxiliarnos de nuevo de la bandera $hasPrefixOfZeros$ para controlar los ceros a la izquierda, y cambiar las transiciones adecuadamente.
Para la segunda cuestión hay dos maneras: hallar $f(1) + f(2) + \cdots + f(n)$, o colocar el 0 como dígito válido **solo en el prefijo de ceros**, después ya no. Esto funciona, pues agregar ceros a la izquierda ya no garantiza números de exactamente $n$ dígitos, solamente de a lo más $n$ dígitos, y la respuesta sería simplemente $f(n)$.
Para la tercera cuestión es muy similar a la anterior: consideramos el cero como dígito valido en el prefijo de ceros, y después ya depende si $0 \in S$ o no.
## Problema: digital signature
Hallar cuántos enteros positivos hay con a lo más $n$ dígitos, tal que la suma de dígitos de $x$ es igual a la suma de dígitos de $137x$.
Por ejemplo, una $x$ válida es $x=468$, pues $137x=64116$ y la suma de dígitos de ambos números es $18$.
Entonces, vemos que construir el número de izquierda a derecha es muy complicado, pues no podemos llevar al mismo tiempo la suma de dígitos tanto de $x$ como de $137x$. Una idea es construir el número de derecha a izquierda, pues así podemos llevar simultáneamente ambas sumas de dígitos. Usando este mismo ejemplo:
- Si el dígito actual es $8$, entonces la suma de dígitos de $x$ es $8$, la de $137x$ es $(8*137) \% 10 = 6$ y el carry es $(8*137)/10=109$.
- Si el dígito actual es $6$, entonces la suma de dígitos de $x$ es $8+6=14$, la de $137x$ es $6+(6*137+109)\%10=6+1=7$ y el carry es $(6*137+109)/10=93$.
- Si el dígito actual es $4$, entonces la suma de dígitos de $x$ es $14+4=18$, la de $137x$ es $7+(4*137+93)\%10=7+1=8$ y el carry es $(4*137+93)/10=64$.
- Ya terminamos de construir $x$, pero hay que procesar el carry pendiente que es $64$, es decir, la suma de dígitos de $137x$ es $8+6+4=18$.
Sea $f(n)$ la respuesta y sea $dp(pos, sum, sum\_137, carry)$ la respuesta solo considerando números construidos de derecha a izquierda hasta la posición $pos$, guardando ambas sumas de dígitos y el carry.
Las transiciones quedan como:
$$
dp(pos, sum, sum\_137, carry) = \sum_{d=0}^{9} dp(pos+1, sum+d, sum\_137 + (carry + d*137)\%10, (carry + d*137)/10)
$$
La mandamos llamar como: $f(n) = dp(0, 0, 0, 0)$.
Y el caso base es: $dp(n, sum, sum\_137, carry) = [sum == sum\_137 + digit\_sum(carry)]$
Sign in with Wallet
Connect another wallet