# PROBLEM LINKS

Practice

Contest

# DIFFICULTY

EASY

# EXPLANATION

This problem is solvable by dynamic programming method. But there exits simpler solution which works even for ranges **[1; 10^100000]**.

It is well-known that in the problems like this **Count(l, r) = Count(1, r) - Count(1, l-1)**, so we should create function **Count(x)** - the number of such **i (i = 1..x)** that **F(i)** is a lucky number. Let d be an array of digits of **x** (numeration starts from leftmost digit, string from 0). For example, **d** for **x** = **47501** is {**4, 7, 5, 0, 1}**. Now consider function **Number(size)** - the answer for suffix of **d** with size **size** and with prefix equal to corresponding prefix of d (for example, suffix of size **4** for **5475107** is **5107**). Of course, the answer for the problem will be **Number(|d|)**, where |**d|** is the number of digits of **x**. Now consider we need to calc **Number(size)**. What digits we can place on position **|d|-size?** That are digits from **0** to **d[|d|-size]**, inclusive. Why not **d[|d|-size]+1**? Because in that case number will be greater then current suffix of **x**, no matter what we place in next positions. What if we place there digit which is less then **d[|d|-size]**? Then we can place any digits in following positions! Let **cnt** be the number of lucky digits among digits **d[0..|d|-size]** (you may consider that we have placed some digit on position **|d|-size** which is less then **d[|d|-size]**). Then itearate through all lucky numbers from cnt to 1000 (let it be integer l), what is the number of numbers with given prefix (digits **d[0..|d|-size]**) and number of lucky digits equal to l, considering that the rest of digits we can place arbitrary. It is **C(size-1, l-cnt)***Pow(2, l-cnt)*Pow(8, size-1-(l-cnt)) (C(n, k) - Binomial coefficient, **Pow(n, k) - n in k-th** power). Wait, but why? Because **C(size-1, l-cnt**) is the number of ways to place exactly **l-cnt** lucky digits, **Pow(2, l-cnt)** is the number of ways to place either **4** or **7** to each such position, **Pow(8, size-1-(l-cnt)** is the number of ways to place unlucky digits (0, 1, 2, 3, 5, 6, 8, 9) in the rest of the positions. That was in case if we place digit less then d[|d|-size] on position |d|-size, What if place **d[|d|-size]** there? Then we just need to calculate **Number(size-1)**, because our prefix increases and suffix decreases, so we can just go to **Number(size-1).** Of course, **Number(0) is 1** if x contains lucky number of lucky digits, **0** otherwise.

What is the comlexity of such algorithm? It is **O(|d|)**, but you also need to calc C(n, k) for **1 <= n <= 10^3**, which gives complexity **O(|d|*|d|)**. There is the way of computing **C(n, k)** in O(1), in this case the complexity is **O(|d|**) (**read setter's solution for further details).**

# SETTER'S SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

asked
**15 Nov '12, 11:35**

0★admin ♦♦

19.7k●350●498●541

accept rate:
35%