Count of numbers in range which are divisible by M and have digit D at odd places | C ++ program to find the count of numbers in the range [ L , R ] which are divisible by M and have digit D at the odd places ; Variables to store M , N , D ; Vector to store the digit number in the form of digits ; Dp table to compute the answer ; Function to add the individual digits into the vector ; Iterating through the number and adding the digits into the vector ; Function to subtract 1 from a number represented in a form of a string ; Iterating through the number ; If the first digit is 1 , then make it 0 and add 9 at the end of the string . ; If we need to subtract 1 from 0 , then make it 9 and subtract 1 from the previous digits ; Else , simply subtract 1 ; Function to find the count of numbers in the range [ L , R ] which are divisible by M and have digit D at the odd places ; Base case ; If we have built N - digit number and the number is divisible by m then we have got one possible answer . ; If the answer has already been computed , then return the answer ; The possible digits which we can place at the pos position . ; Iterating through all the digits ; If we have placed all the digits up to pos - 1 equal to their limit and currently we are placing a digit which is smaller than this position 's limit then we can place  0 to 9 at all the next positions  to make the number smaller than R ; Calculating the number upto pos mod m . ; Combinations of numbers as there are 10 digits in the range [ 0 , 9 ] ; Recursively call the function for the next position ; Returning the final answer ; Function to call the function for every query ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE ll m , n , d ; vector < int > v ; ll const k = 1e9 + 7 ; ll dp [ 2001 ] [ 2001 ] [ 2 ] ; void init ( string s ) { memset ( dp , -1 , sizeof ( dp ) ) ; v . clear ( ) ; for ( int i = 0 ; i < s . size ( ) ; i ++ ) { v . push_back ( s [ i ] - '0' ) ; } n = s . size ( ) ; } string number_minus_one ( string a ) { string s = a . substr ( 1 ) ; string s1 = " " ; for ( int i = 0 ; i < s . size ( ) - 1 ; i ++ ) s1 += '0' ; if ( a [ 0 ] == 1 and s == s1 ) { ll l = s . size ( ) ; a = " " ; a += '0' ; for ( int i = 0 ; i < l ; i ++ ) a += '9' ; } else { for ( int i = a . size ( ) - 1 ; i >= 0 ; i -- ) { if ( a [ i ] == '0' ) a [ i ] = '9' ; else { a [ i ] = ( ( ( a [ i ] - '0' ) - 1 ) + '0' ) ; break ; } } } return a ; } ll fun ( ll pos , ll sum , ll f ) { if ( pos == n ) { if ( sum == 0 ) { return 1 ; } return 0 ; } if ( dp [ pos ] [ sum ] [ f ] != -1 ) return dp [ pos ] [ sum ] [ f ] ; ll lmt = 9 ; if ( ! f ) lmt = v [ pos ] ; ll ans = 0 ; for ( ll i = 0 ; i <= lmt ; i ++ ) { if ( i == d and pos % 2 == 1 ) ans += 0 ; else if ( i != d and pos % 2 == 0 ) ans += 0 ; else { ll new_f = f ; if ( f == 0 and i < lmt ) new_f = 1 ; ll new_sum = sum ; new_sum *= 10 ; new_sum += i ; new_sum %= m ; ans += fun ( pos + 1 , new_sum , new_f ) ; ans %= k ; } } return dp [ pos ] [ sum ] [ f ] = ans ; } void operations ( string L , string R ) { init ( R ) ; ll ans = fun ( 0 , 0 , 0 ) ; L = number_minus_one ( L ) ; init ( L ) ; ans -= fun ( 0 , 0 , 0 ) ; if ( ans < 0 ) ans += k ; cout << ans << " STRNEWLINE " ; } int main ( ) { m = 2 , d = 2 ; ll Q = 1 ; string arr [ ] [ 2 ] = { { "20" , "32" } } ; for ( ll i = 0 ; i < Q ; i ++ ) { operations ( arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) ; } return 0 ; }