Skip to Content
CTRL K

Magic Numbers

Análisis oficial (C++) 

Explicación

Primero, para reducir el problema, observamos lo siguiente:

  1. Ser divisible por MM significa que nuestro número es equivalente a 00, módulo MM.
  2. Sea \texttt{count\\_magic}(x) el conjunto de todos los números mágicos ≤x\leq x. La frecuencia de números mágicos en el rango [a,b][a, b] es \texttt{count\\_magic}(b) - \texttt{count\\_magic}(a - 1).

Luego, podemos usar un estado de DP bastante típico para modelar el problema.

Sea dp[i][j][k]\texttt{dp}[i][j][k] el conjunto de todas las posibilidades cuando:

  • Hemos considerado los primeros ii dígitos
  • Nuestro número es equivalente a jj, módulo MM
  • kk indica si nuestro número está “libre” o no
    • Es decir, si los primeros ii dígitos de nuestro número coinciden o no con la cota

Luego, tras considerar todos nuestros dígitos, consideramos todos los números equivalentes a 00 módulo MM.

Estos son algunos puntos clave al implementar el problema:

  • Manejar a−1a-1 en forma de string es molesto. En cambio, podemos considerar los valores de \texttt{count\\_magic}(a) y \texttt{count\\_magic}(b), y tratar aa por separado a mano.
  • Observemos que el problema garantiza que aa y bb tienen la misma longitud. Esto significa que podemos ignorar de forma efectiva los ceros a la izquierda en la implementación.

Implementación

Complejidad temporal: O(M⋅D)\mathcal{O}(M \cdot D), donde DD es el número de dígitos de aa y bb.

#include <bits/stdc++.h>
using namespace std;
 
constexpr int MOD = 1e9 + 7;
 
int count_magic(int m, int d, string bound, bool ok) {
	if (bound.length() == 1) {
		int num_good = 0;
		int cur_digit = bound[0] - '0';
		for (int i = 0; i < cur_digit; i++) { num_good += (i != d) && (i % m == 0); }
 
		if (ok && cur_digit != d && cur_digit % m == 0) { num_good++; }
 
		return num_good;
	}
 
	vector<int> digits;
	for (int i = 0; i < bound.length(); i++) { digits.push_back(bound[i] - '0'); }
 
	// dp[i][j] = # de formas, si cur es equiv a i, y j = libre o no
	vector<array<int, 2>> dp(m);
	for (int i = 1; i <= digits[0]; i++) {
		if (i == d) { continue; }
		dp[i % m][(i < digits[0])]++;
	}
 
	for (int i = 1; i < digits.size(); i++) {
		const int cur = digits[i];
		vector<array<int, 2>> next_dp(m);
		for (int j = 0; j < m; j++) {
			if (i % 2 == 1) {
				// forzamos que este dígito sea D
				int nxt = (10 * j + d) % m;
				(next_dp[nxt][1] += dp[j][1]) %= MOD;
				if (cur > d) {
					(next_dp[nxt][1] += dp[j][0]) %= MOD;
				} else if (cur == d) {
					(next_dp[nxt][0] += dp[j][0]) %= MOD;
				}
			} else {
				// solo hay que asegurarse de que el siguiente dígito no sea D
				for (int dig = 0; dig <= 9; dig++) {
					if (dig == d) { continue; }
					int nxt = (10 * j + dig) % m;
					(next_dp[nxt][1] += dp[j][1]) %= MOD;
					if (dig < cur) {
						(next_dp[nxt][1] += dp[j][0]) %= MOD;
					} else if (dig == cur) {
						(next_dp[nxt][0] += dp[j][0]) %= MOD;
					}
				}
			}
		}
 
		dp = move(next_dp);
	}
 
	return (dp[0][1] + dp[0][0] * ok) % MOD;
}
 
int main() {
	int m, d;
	cin >> m >> d;
 
	string a, b;
	cin >> a >> b;
 
	cout << (count_magic(m, d, b, true) - count_magic(m, d, a, false) + MOD) % MOD
	     << endl;
}
Fundamentos