One of the solution is like this:

Suppose m has n digits and d_i is the i-th digit of m. Let f(i, j, 0) be the number of integers, with i digits maximum, that have exactly j lucky digits and are less than d₁d₂... d_i (that is, the first i digits of m) and let f(i, j, 1) be the number of integers, with i digits maximum, that have exactly j lucky digits and equal d₁d₂... d_i, i ≥ j. It's easy to see that f(i, j, 1) is either 0 or 1. Let's also assume that we already have two functions, N(x) and L(x), that compute the number of non-lucky and lucky digits less than x respectively.

Base cases:

1. f(1, 0, 0) = N(d₁)

2. f(1, 1, 0) = L(d₁)

3. f(1, 0, 1) = 0 if d₁ is a lucky digit, 1 otherwise

4. f(1, 1, 1) = 1 if d₁ is a lucky digit, 0 otherwise

Transitions:

1. f(i, j, 1) = 1 if there are exactly j lucky digits in d₁, d₂, ... d_i, 0 otherwise

2. If j = 0 then

f(i, j, 0) = 8f(i - 1, j, 0) + N(d_i)f(i - 1, j, 1)

else

f(i, j, 0) = 8f(i - 1, j, 0) + N(d_i)f(i - 1, j, 1) + 2f(i - 1, j - 1, 0) + L(d_i)f(i - 1, j - 1, 1)

Then, the number of integers between 1 and m (inclusive) that have exactly k lucky digits is f(n, k, 0) + f(n, k, 1), minus 1 if k = 0 since we don't want to count the number 0 in.

Seems like there's a little typo in the explanation for Div2 E/Div1 C. It should be The result is equal to 1^q₁ 2^q₂ ...  k^q_k since i takes value between 1 and k, not p

Btw, thanks for the editorial. My solution for Div1 C is the same but I forgot to handle the case where the subtraction yields negative value :(

Thanks for the editorial! However, could you please translate the explanation for problem C Div2 into English? Thank you.