Counting Numbers

Complejidad temporal: $\mathcal O(\log b)$

Usaremos DP de dígitos para resolver este problema.

Primero, en lugar de hallar la respuesta para el rango $[a, b]$, hallamos las respuestas para los rangos $[0, a - 1]$ y $[0, b]$, y su diferencia será la respuesta. (Se verá que se usa esta técnica en casi todos los problemas de DP de dígitos).

Sea $dp[i][j]$ la cantidad de enteros buenos con $i$ dígitos y cuyo $i$-ésimo dígito es $j$. La recurrencia es $dp[i][j] = \sum_{k = 0}^9 dp[i - 1][k] - dp[i - 1][j]$ y los casos base son $dp[1][j] = 1$ para cada $j$. Calcular la DP a mano muestra que $dp[i][j] = 9^{i - 1}$.

¿Cómo contamos la cantidad de enteros buenos no mayores que un $x$ dado con $d$ dígitos? Tenemos dos casos:

• El entero bueno tiene $d' < d$ dígitos.
• El entero bueno tiene $d' = d$ dígitos.

Cualquier entero bueno que caiga en el primer caso se cuenta en la respuesta, así que este caso contribuye exactamente $\sum_{i = 0}^{d - 2}9^i$ a la respuesta.

El segundo caso es un poco más tramposo. La observación clave es que cualquier $y$ bueno no mayor que $x$ que caiga en este caso satisface dos condiciones:

• $x$ e $y$ comparten un prefijo común de longitud $0 \leq i \leq d$ sin dígitos vecinos iguales.
• El $(i + 1)$-ésimo dígito de $y$ es menor que el $(i + 1)$-ésimo dígito de $x$.

Esto significa que, para cada prefijo fijo (bueno) de los dígitos de $x$, podemos contar la cantidad de $y$ buenos con ese prefijo. Si el $i$-ésimo dígito de $x$ es $s_i$, entonces contribuye $s_i \cdot 9^{d - i}$ a la respuesta. Si $s_i > s_{i - 1}$, entonces también debemos restar $9^{d - i}$ de la respuesta para evitar que dos dígitos consecutivos sean iguales.

Como podemos procesar cada dígito de $a$ y $b$ en tiempo $\mathcal O(1)$, esta solución funciona en tiempo $\mathcal O(\log b)$.

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
ll pow_9[19]{1};
 
ll calc(ll x) {
	if (x == -1) return 0;
	ll ans = 0;
	vector<int> digits;
	while (x) {
		digits.push_back(x % 10);
		x /= 10;
	}
	for (int i = 0; i < (int)digits.size() - 1; i++) ans += pow_9[i];
	digits.push_back(10);
	for (int i = (int)digits.size() - 2; ~i; i--) {
		ans += digits[i] * pow_9[i];
		if (digits[i] > digits[i + 1]) ans -= pow_9[i];
 
		if (digits[i] == digits[i + 1]) return ans;
	}
	return ans + 1;
}
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	for (int i = 1; i <= 18; i++) pow_9[i] = 9 * pow_9[i - 1];
	ll a, b;
	cin >> a >> b;
	cout << calc(b) - calc(a - 1);
	return 0;
}