### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### EXPLANATION

Please, before reading this article read some tutorials about dynamic programming, like this one: http://www.codechef.com/wiki/tutorial-dynamic-programming

This problem is the unification of some trivial DP problems (dynamic programming) and problem ‘find somthing k-th’.

In problems like this, when you need to find **k-th** lexicographically minimal sequence, it is useful to notice that if we at each step (i. e. at each position starting from **0** to **n-1**) will always choose the minimal possible integer at that position, here ‘possible’ means that if we place at some position some integer it must be possible to place the rest of positions (without violating the rules described in the statement).

Imagine that we are on position i. All numbers before **i-th** are already placed in array **R.** We need to find **k-th** minimal correct suffix of size **n-i**. The question is what number we should place on **i-th** position. The answer is that it must be the minimal positive integer **x** not greater than m and for which **Count(x-1, mask) < k. mask** is a set (array or bitmask) of possible values of **F(x)** that can be placed on **i-th** position (if **i = 0** it is any integer, if **C[i-1] = 1** it is only **F(R[i-1])** and if **C[i-1]** = 0 it is any integer except **F(R[i-1])**). Now what is **Count(x, mask)**? It is the number of valid suffixes of last **n-i** positions if at first position of that suffix (i. e. **i-th** position in total array) we place integer not greater then **x.** Imagine now that we have such function done. How to quickly find **x**? Of course, you can use binary search in this case, because function Count will be non-decreasing with increasing of **x**. And the last note in this section: when you will have **x**, dont forget to subtract **Count(x-1, mask)** from **k**, because all number from **1** to **x-1** will lead to lesser sequences.

The description of **Count** function is at the end because we need several additional functions.

Let **LuckyCount(x, num)** will be the number of such integers a **(1 <= a <= x)** that **F(a) = num**. It can be calculated with trivial DP with states **[pos][less][cnt]**, here pos is the position of digit in decimal representation of **x, less** = **0** if current prefix is lesser than corresponding prefix in **x** and **1** if it is equal, cnt - the number of lucky digits in current prefix. If we are in state **[pos][less][cnt]** we can iterate through all digits d from **0** to **9** (inclusive) and try to place it on the next position in prefix. If we find transitive state **[pos’][less’][cnt’]** for any digit then we just do **DP[pos’][less’][cnt’] += DP[pos][less][cnt]**, where **DP** is or dynamic programming array. Of course, **pos’ = pos+1**, because we are adding single digit. If **less = 0** then less’ is also **0**, because if our prefix is already less than corresponding prefix in **x** it doesn’t matter what digit we will place to the right, if **less = 1 and d < x[pos] then less’ = 0, if less = 1 and d = x[pos] then less’ = 1,** otherwise, if **less = 1 and d > x[pos]** then we cant use digit d (the prefix will be greater than corresponding prefix in **x**), here **x[pos]** is **pos-th** digit of decimal representation of **x** (strarting from the rightmost digit). **cnt’ = cnt** if **d** is not equal **4** or **7**, otherwise it is **cnt+1**. The return value for function, of course, will be **DP[size(x)][0][num] + DP size(x)[num]**, where **size(x)** is the size of decimal representation of **x**. Note that the strating state of DP, the sate DP0[0] equals to **1**.

Let **SuffixCount(len, last)** will be the number of valid placements of last len numbers (in this case we can place any numbers from **1** to **m**, inclusive at that positions) of our array considering that the first number at position **n-len** has the number of lucky digits equal to **last**. Calculating this DP we should keep track on values of array **C**. Imagine that we are in the state **[len][last]**. As transitions we iterate through all possible values **next** of function **F** for the next number to the left (i. e. at position **n-len-1**), which will not be greater than **9** and doing **DP[len+1][next] += DP[len][last]*LuckyCount(m, next)**. But note that if **C[n-len-1]** is **1** then next may be only the same as last, otherwise it should not be equal to **last**. The return is just **DP[len][last]. DP[0][0] = 1**.

And now the last function **Count(x, mask)**. Iterate through all possible values of **F** we can place at **i-th** position, i. e. numbers in **mask** (generally it will not increase **9** because it is impossible to place more than **9** lucky digits in any number not greater than **10^9)**, let it be integer f. We know that the number of such number not greater than x and with the number of lucky digits equal to f is **LuckyCount(x, f)**. Then the number of valid suffixes with **F(R[i])** equal to f is **LuckyCount(x, f) SuffixCount(n-i-1, g)* for all valid

**g**(depending on

**C[i])**. The sum of such values for all

**f**in

**mask**will be the result for

**Count**function.

Also please note that in this problem you need a lot of memoization, i. e. you need to save your results in different DP states in order to get green **Accepted**

### SETTER’S SOLUTION

Can be found here.

### TESTER’S SOLUTION

Can be found here.