Digit Sum

Solución

Explicación

Definamos la función $\mathtt{pref}(x)$ como la suma de dígitos entre todos los enteros desde $0$ hasta $x$ inclusive. Entonces, la respuesta de cada consulta será $\mathtt{pref}(r) - \mathtt{pref}(l-1)$ .

Podemos calcular $\mathtt{pref}(x)$ usando DP de dígitos. Sea $n$ el número de dígitos de $x$ . La suma máxima de dígitos entre todos los números con a lo sumo $n$ dígitos es $9n$ . Bajo las restricciones del problema, $n$ es a lo sumo $16$ .

Podemos definir el siguiente estado de DP: $\mathtt{dp[i][j][b]}$ = número de enteros con exactamente $i$ dígitos, suma de dígitos $j$ y un valor de libertad $b$ (que es $0$ o $1$ ).

Si $b = 0$ , entonces los primeros $i$ dígitos del estado son equivalentes a los primeros $i$ dígitos de $x$ . En este caso, al colocar el dígito $i+1$ , no puede superar el dígito $i+1$ de $x$ .
Si $b = 1$ , entonces existe algún $d$ con $d < i$ tal que el $d$ -ésimo dígito que colocamos es menor que el $d$ -ésimo dígito de $x$ . En este caso, ya sabemos que nuestro entero debe ser menor que $x$ , independientemente del dígito que coloquemos a continuación.

Para las transiciones, debemos considerar los tres casos en que $b$ permanece $0$ , $b$ permanece $1$ , y $b$ pasa de $0$ a $1$ .

Finalmente, la suma de dígitos entre todos los enteros con exactamente $i$ dígitos que no superan $x$ está dada por $\sum_{j=0}^{9n} \sum_{b=0}^1 \mathtt{dp[n][j][b]} \cdot j$ . Sin embargo, todavía hay que sumar la suma de dígitos de todos los números con menos de $n$ dígitos, que se puede precalcular.

Implementación

Complejidad temporal: $\mathcal{O}(n^2)$ por cada consulta, donde $n$ es la longitud del número.

C++


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int MAX_LEN = 17;
ll ans_pow10[MAX_LEN];
 
ll pref(ll upper) {
	string upper_str = to_string(upper);
	int n = upper_str.length();
	const int MAX_SUM = 9 * n + 1;
	// dp[longitud actual][suma actual de dígitos][¿tenemos libertad?] = # números
	vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(MAX_SUM, vector<ll>(2)));
 
	// inicializamos el primer dígito
	int first_digit = upper_str[0] - '0';
	dp[0][first_digit][0] = 1;
	for (int i = 1; i < first_digit; i++) { dp[0][i][1] = 1; }
 
	int curr_sum = first_digit;
	for (int i = 1; i < n; i++) {
		// caso 1: seguimos sin tener libertad
		int next_digit = upper_str[i] - '0';
		dp[i][curr_sum + next_digit][0] = 1;
 
		// caso 2: antes no teníamos libertad, pero ahora sí
		for (int j = 0; j < next_digit; j++) { dp[i][curr_sum + j][1]++; }
 
		// caso 3: siempre tuvimos libertad
		for (int j = 0; j < 10; j++) {
			for (int prev_sum = 0; prev_sum < MAX_SUM - j; prev_sum++) {
				dp[i][prev_sum + j][1] += dp[i - 1][prev_sum][1];
			}
		}
		curr_sum += next_digit;
	}
 
	ll ans = 0;
	// respuesta para todos los números con la cantidad actual de dígitos
	for (int sum = 0; sum < MAX_SUM; sum++) {
		for (int free = 0; free < 2; free++) { ans += dp[n - 1][sum][free] * sum; }
	}
	// respuesta para todos los números con menos dígitos
	ans += ans_pow10[n - 1];
 
	return ans;
}
 
int main() {
	// precomputamos la respuesta para [0, 10^i - 1]
	ll pow10 = 1;
	for (int i = 1; i < MAX_LEN; i++) {
		pow10 *= 10;
		ans_pow10[i] = pref(pow10 - 1);
	}
 
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		ll l, r;
		cin >> l >> r;
		if (l == 0) {
			// l - 1 < 0 lo cual rompe las cosas
			cout << pref(r) << '\n';
		} else {
			cout << pref(r) - pref(l - 1) << '\n';
		}
	}
}

Solución alternativa

Explicación

Sea $\mathtt{pref}(x)$ la misma función que en la solución de arriba.

Convirtamos el número en un string y tratémoslo como tal.

Definamos $\mathtt{dp[i][b]}$ como la suma de dígitos y la cantidad de números distintos que podemos formar en el sufijo que empieza en la posición $i$ ; $b$ es el mismo valor de libertad que en la solución de arriba.

Veamos las transiciones:

Si el sufijo está vacío, la suma es $0$ y la cantidad es $1$ .
En caso contrario, supongamos que intentamos colocar el dígito $d$ en una posición $i$ . Sea $num$ la cantidad de números distintos que podemos crear en un sufijo que empieza en la posición $i+1$ después de colocar el dígito $d$ , y sea $sum$ la suma de dígitos de esos números. Entonces la contribución de $d$ sería $d \cdot num$ , y las contribuciones de todas las demás posiciones del sufijo serían $sum$ .
Nuestro valor de libertad $b$ pasa de $0$ a $1$ si colocamos un dígito $d$ menor que el dígito en la posición $i$ . No podemos colocar el dígito $d$ si $b$ es $0$ y $d$ es mayor que el dígito en la posición $i$ .

La respuesta es el valor de la suma en $\mathtt{dp[0][0]}$ .

Implementación

Complejidad temporal: $\mathcal{O}(n)$ por cada consulta, donde $n$ es la longitud del número.

C++


#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int max_n = 16;
 
// dp[i][b] = {suma_de_digitos, cantidad}
array<ll, 2> dp[max_n][2];
string digits;
int number_length;
 
array<ll, 2> calc(int pos, bool is_free) {
	// Caso base: sufijo vacío, así que la suma total es 0 y la cantidad total es 1
	if (pos == number_length) { return {0, 1}; }
	if (dp[pos][is_free][0] != -1) return dp[pos][is_free];
 
	bool next_is_free;
	array<ll, 2> ans = {0, 0};
	for (int d = 0; d < 10; d++) {
		// Esto significa que nuestro número sería demasiado grande
		if (is_free == false && d > (digits[pos] - '0')) break;
		next_is_free = is_free;
 
		// Actualizamos nuestro valor de libertad
		if (is_free == false && d < (digits[pos] - '0')) next_is_free = true;
		auto next_state = calc(pos + 1, next_is_free);
 
		// Sumamos la cantidad de números al estado actual de la DP
		ans[1] += next_state[1];
 
		// Sumamos la contribución del dígito actual y la suma total de dígitos
		// posteriores
		ans[0] += d * next_state[1] + next_state[0];
	}
 
	return dp[pos][is_free] = ans;
}
 
// Reiniciamos la DP y digits y obtenemos la respuesta
ll pref(ll n) {
	if (n <= 0) return 0;
	digits = to_string(n);
	number_length = digits.size();
	for (int i = 0; i < number_length; i++) {
		for (int j = 0; j < 2; j++) dp[i][j] = {-1, 0};
	}
 
	return calc(0, false)[0];
}
 
void solve() {
	ll l, r;
	cin >> l >> r;
	cout << pref(r) - pref(l - 1) << '\n';
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	cin >> t;
	while (t--) { solve(); }
	return 0;
}