PREREQUISITES : dp
The problem can be classified as digit dp . For now , lets just try to solve a simpler version of this problem which says , count the numbers which lie between [L,R] where 1<=L<=R<=10^18 . though we already know that the answer will be R-L+1 but lets just try to solve this problem using dp.
A few observations :
- Any number containing more digits than the number of digits in R (without leading zeroes ) will always be greater than R.
- suppose we count the solution for [0,R] and then for [0,L-1] then the final solution will be solution of [0,R] - solution of [0,L-1].
okay so based on the observations , lets code a function to solve this dp recursively. Here len means the length of the number which we are supposed to make and isequal stores boolean value if the number we have made until now is equal to R or not.* R is converted into array of its digits form .
long long int solve(int len , bool isequal)
{
if(len==0)
{
// if (len==0) means that we have successfully build a number which is less than R
// ** This is the area where we will check if the number we have formed until now should be counted as one solution or not depending upon if it full fills our defined properties**
return 1;
}
long long int sol=0;
if(isequal==false)
{
//means that we have already fixed some digit x which was less than digit of r at some previous len . so now we can try all values because we are sure that the number will be less than R always , for example R=4000 , if we fix 3 at first position then it doesn't matter what digit we fix now , the number will be always less than R.
for(int i=0 ; i<=9 ;i++)
{
sol+=solve(len-1,0);
}
}
else
{
for(int i=0 ; i<=R[len] ;i++)
{
if(i < R[len] )
sol+=solve(len-1,0);
else sol+=solve(len-1,1);
}
}
return sol;
}
Okay , cool ! so now , we have a kind of general structure to solve some digit DPs of form " count a number of certain property between [L,R] ". Now coming back to the question WORKCHEF , so lets just our define our properties first:
- we need to check if the number we have formed contains atleast K distinct numbers or not . This certainly points us to keep a bitmask of length 9 where ith bit stores existance of digit i in the number.(we dont need ‘0’ mentioned in the question)
- incase the above condition is true , then the number should also be divisible by atleast K of digits used in making it . To check divisibility we need the actual number but we cant pass such numbers in recursive call
. Then how will we check this condition at our base case? so the answer is we dont need to pass the whole number , we can actually pass the number%(LCM(1,2,3,4,5,6,7,8,9)) i.e. number%2520.
So finally we need to pass { len,mask ,modvalue%2520 , isequal }in the recursive call. so the above function can be modified easily to this.
int check(int mask,int modvalue)
{
//brute code this function in O(9)
if(property is statisfied for the given K)
return 1;
else return 0;
}
long long int solve(int len ,int mask ,int modvalue,bool isequal)
{
if(len==0)
{
return check(mask,modvalue);
}
long long int sol=0;
if(isequal==false)
{
for(int i=0 ; i<=9 ;i++)
{
if(i==0)
sol+=solve(len-1,mask,(modvalue*10+i)%2520,0);
else sol+=solve(len-1,mask|(1<<i),(modvalue*10+i)%2520,0);
}
}
else
{
for(int i=0 ; i<=R[len] ;i++)
{
if(i < R[len] )
{
if(i==0)
sol+=solve(len-1,mask,(modvalue*10+i)%2520,0);
else sol+=solve(len-1,mask|(1<<i ),(modvalue*10+i)%2520,0);
}
else
{
if(i==0)
sol+=solve(len-1,mask,(modvalue*10+i)%2520 ,1);
else sol+=solve(len-1,mask|(1<<i),(modvalue*10+i)%2520 ,1);
}
}
return sol;
}
okay so now we have a function that computes solution from numbers [0,R] , to print the final solution , just print sol [0,R]-[0,L-1] . And remember L,R are in the form of an array with each digit kept at a position . So , finally just memoize the solution and get AC 
. for more info over digit dp read this . To get info on that modulo and LCM part read this tutorial for problem 687B: Remainders Game.
