Dados dos números enteros N y K , la tarea es calcular el número de números enteros en el rango [0, N] cuya suma de dígitos es un múltiplo de K . La respuesta podría ser grande, así que imprime la respuesta módulo 10 9 +7 .
Ejemplos:
Entrada: N = 10, K = 5
Salida: 2
0 y 5 son los únicos números enteros posibles.Entrada: N = 30, K = 4
Salida: 7
Enfoque ingenuo: para un valor pequeño de N , recorra el rango [0, N] y verifique si la suma de los dígitos de los números son múltiplos de K o no.
Enfoque eficiente: la idea es usar digit dp para resolver este problema. Los subproblemas que iteran a través de todos los valores de índice desde la izquierda o el dígito más significativo (MSD) en el entero dado se resolverán y para cada índice, almacene el número de formas tales que (suma de dígitos hasta el índice actual) mod K sea cero. Los estados de dp serán:
dp[idx][sum][tight]
idx = posición, informa sobre el valor del índice desde la izquierda en el entero dado
suma = suma de dígitos mod k, este parámetro almacenará la (suma de dígitos mod k) en el entero generado desde el dígito más significativo (MSD) hasta p
apretado = marca si el valor actual está cruzando el rango (1, n) o no
Para rango sin restricciones apretado = 0
Para rango restringido apretado = 1
Digamos que estamos en el MSD que tiene el índice idx . Así que inicialmente la suma será 0 . En cada posición, establezca un límite que siempre esté en el rango [0, 9] .
Por lo tanto, complete el dígito en el índice con los dígitos en su rango de 0 a límite y obtenga la respuesta del siguiente estado que tenga índice = idx + 1 y new_tight para el siguiente estado se calcula por separado. La definición de estado de dp será:
dp[idx][sum][tight] += dp[idx + 1][(sum + d) % k][new_tight]
para d en [0, límite]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define MAX 100005 #define MOD 1000000007 // To store the states of the dp int dp[MAX][101][2]; // Function to return the count of numbers // from the range [0, n] whose digit sum // is a multiple of k using bottom-up dp int countNum(int idx, int sum, int tight, vector<int> num, int len, int k) { if (len == idx) { if (sum == 0) return 1; else return 0; } if (dp[idx][sum][tight] != -1) return dp[idx][sum][tight]; int res = 0, limit; // The digit in this index can // only be from [0, num[idx]] if (tight == 0) { limit = num[idx]; } // The digit in this index can // be anything from [0, 9] else { limit = 9; } for (int i = 0; i <= limit; i++) { // new_tight is the flag value // for the next position int new_tight = tight; if (tight == 0 && i < limit) new_tight = 1; res += countNum(idx + 1, (sum + i) % k, new_tight, num, len, k); res %= MOD; } // res can't be negative if (res < 0) res += MOD; return dp[idx][sum][tight] = res; } // Function to process the string to // a vector of digits from MSD to LSD vector<int> process(string s) { vector<int> num; for (int i = 0; i < s.length(); i++) { num.push_back(s[i] - '0'); } return num; } // Driver code int main() { // For large input number n string n = "98765432109876543210"; // Total number of digits in n int len = n.length(); int k = 58; // Clean dp table memset(dp, -1, sizeof(dp)); // Process the string to a vector // of digits from MSD to LSD vector<int> num = process(n); cout << countNum(0, 0, 0, num, len, k); return 0; }
Java
// Java implementation of the approach import java.util.*; class GFG { static final int MAX = 100005; static final int MOD = 1000000007; // To store the states of the dp static int [][][]dp = new int[MAX][101][2]; // Function to return the count of numbers // from the range [0, n] whose digit sum // is a multiple of k using bottom-up dp static int countNum(int idx, int sum, int tight, Vector<Integer> num, int len, int k) { if (len == idx) { if (sum == 0) return 1; else return 0; } if (dp[idx][sum][tight] != -1) return dp[idx][sum][tight]; int res = 0, limit; // The digit in this index can // only be from [0, num[idx]] if (tight == 0) { limit = num.get(idx); } // The digit in this index can // be anything from [0, 9] else { limit = 9; } for (int i = 0; i <= limit; i++) { // new_tight is the flag value // for the next position int new_tight = tight; if (tight == 0 && i < limit) new_tight = 1; res += countNum(idx + 1, (sum + i) % k, new_tight, num, len, k); res %= MOD; } // res can't be negative if (res < 0) res += MOD; return dp[idx][sum][tight] = res; } // Function to process the String to // a vector of digits from MSD to LSD static Vector<Integer> process(String s) { Vector<Integer> num = new Vector<Integer>(); for (int i = 0; i < s.length(); i++) { num.add(s.charAt(i) - '0'); } return num; } // Driver code public static void main(String[] args) { // For large input number n String n = "98765432109876543210"; // Total number of digits in n int len = n.length(); int k = 58; // Clean dp table for(int i = 0; i < MAX; i++) { for(int j = 0; j < 101; j++) { for(int l = 0; l < 2; l++) dp[i][j][l] = -1; } } // Process the String to a vector // of digits from MSD to LSD Vector<Integer> num = process(n); System.out.print(countNum(0, 0, 0, num, len, k)); } } // This code is contributed by 29AjayKumar
Python 3
# Python 3 implementation of the approach MAX = 10005 MOD = 1000000007 # Function to return the count of numbers # from the range [0, n] whose digit sum # is a multiple of k using bottom-up dp def countNum(idx, sum, tight, num, len1, k): if (len1 == idx): if (sum == 0): return 1 else: return 0 if (dp[idx][sum][tight] != -1): return dp[idx][sum][tight] res = 0 # The digit in this index can # only be from [0, num[idx]] if (tight == 0): limit = num[idx] # The digit in this index can # be anything from [0, 9] else: limit = 9 for i in range(limit + 1): # new_tight is the flag value # for the next position new_tight = tight if (tight == 0 and i < limit): new_tight = 1 res += countNum(idx + 1,(sum + i) % k, new_tight, num, len1, k) res %= MOD # res can't be negative if (res < 0): res += MOD dp[idx][sum][tight] = res return dp[idx][sum][tight] # Function to process the string to # a vector of digits from MSD to LSD def process(s): num = [] for i in range(len(s)): num.append(ord(s[i]) - ord('0')) return num # Driver code if __name__ == '__main__': # For large input number n n = "98765432109876543210" # Total number of digits in n len1 = len(n) k = 58 # To store the states of the dp dp = [[[-1 for i in range(2)] for j in range(101)] for k in range(MAX)] # Process the string to a vector # of digits from MSD to LSD num = process(n) print(countNum(0, 0, 0, num, len1, k)) # This code is contributed by Surendra_Gangwar
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { static readonly int MAX = 10005; static readonly int MOD = 1000000007; // To store the states of the dp static int [,,]dp = new int[MAX, 101, 2]; // Function to return the count of numbers // from the range [0, n] whose digit sum // is a multiple of k using bottom-up dp static int countNum(int idx, int sum, int tight, List<int> num, int len, int k) { if (len == idx) { if (sum == 0) return 1; else return 0; } if (dp[idx, sum, tight] != -1) return dp[idx, sum, tight]; int res = 0, limit; // The digit in this index can // only be from [0, num[idx]] if (tight == 0) { limit = num[idx]; } // The digit in this index can // be anything from [0, 9] else { limit = 9; } for (int i = 0; i <= limit; i++) { // new_tight is the flag value // for the next position int new_tight = tight; if (tight == 0 && i < limit) new_tight = 1; res += countNum(idx + 1, (sum + i) % k, new_tight, num, len, k); res %= MOD; } // res can't be negative if (res < 0) res += MOD; return dp[idx, sum, tight] = res; } // Function to process the String to // a vector of digits from MSD to LSD static List<int> process(String s) { List<int> num = new List<int>(); for (int i = 0; i < s.Length; i++) { num.Add(s[i] - '0'); } return num; } // Driver code public static void Main(String[] args) { // For large input number n String n = "98765432109876543210"; // Total number of digits in n int len = n.Length; int k = 58; // Clean dp table for(int i = 0; i < MAX; i++) { for(int j = 0; j < 101; j++) { for(int l = 0; l < 2; l++) dp[i, j, l] = -1; } } // Process the String to a vector // of digits from MSD to LSD List<int> num = process(n); Console.Write(countNum(0, 0, 0, num, len, k)); } } // This code is contributed by Rajput-Ji
Javascript
<script> // Javascript implementation of the approach var MAX = 100005; var MOD = 1000000007; // To store the states of the dp var dp = Array.from(Array(MAX), () => Array(101)); for(var i =0; i<MAX; i++) for(var j =0; j<101; j++) dp[i][j] = new Array(2).fill(-1); // Function to return the count of numbers // from the range [0, n] whose digit sum // is a multiple of k using bottom-up dp function countNum(idx, sum, tight, num, len, k) { if (len == idx) { if (sum == 0) return 1; else return 0; } if (dp[idx][sum][tight] != -1) return dp[idx][sum][tight]; var res = 0, limit; // The digit in this index can // only be from [0, num[idx]] if (tight == 0) { limit = num[idx]; } // The digit in this index can // be anything from [0, 9] else { limit = 9; } for (var i = 0; i <= limit; i++) { // new_tight is the flag value // for the next position var new_tight = tight; if (tight == 0 && i < limit) new_tight = 1; res += countNum(idx + 1, (sum + i) % k, new_tight, num, len, k); res %= MOD; } // res can't be negative if (res < 0) res += MOD; return dp[idx][sum][tight] = res; } // Function to process the string to // a vector of digits from MSD to LSD function process(s) { var num = []; for (var i = 0; i < s.length; i++) { num.push(s[i].charCodeAt(0) - '0'.charCodeAt(0)); } return num; } // Driver code // For large input number n var n = "98765432109876543210"; // Total number of digits in n var len = n.length; var k = 58; // Process the string to a vector // of digits from MSD to LSD var num = process(n); document.write( countNum(0, 0, 0, num, len, k)); </script>
635270835
Publicación traducida automáticamente
Artículo escrito por ShrabanaBiswas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA