### PROBLEM LINK:

**Author:** Vivek Hamirwasia

**Tester:** Anton Lunyov

**Editorialist:** Anton Lunyov

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

### PROBLEM:

If positive integer **N** has decimal representations **d _{1}d_{2}…d_{L}**, where

**n**, then

_{1}≠ 0**DIVPRO(N) = d**. If at some point division by zero occurs the

_{1}/ d_{2}* d_{3}/ d_{4}* …**DIVPRO(N)**is undefined (so digits at even positions should be non-zero). For the given integers

**0 ≤ V < 10**and

^{18}**1 ≤ L ≤ 36**you need to find the number of positive

**L**-digit integers

**N**having

**DIVPRO(N) = V**and output this number modulo

**2**. You should be able to answer up to

^{32}**320,000**such tests in 3 seconds.

### QUICK EXPLANATION:

If **V = 0** then the count is **9 ^{L − X} * (10^{X} − 9^{X})** where

**X = floor((L − 1) / 2)**.

When **V > 0** the answer is non-zero only when **V** has the form **2 ^{n2} * 3^{n3} * 5^{n5} * 7^{n7}**.

Let **dp[L][n2][n3][n5][n7]** be a count of **L**-digit positive integers **N** having **DIVPRO(N) = 2 ^{n2} * 3^{n3} * 5^{n5} * 7^{n7}**, where

**n2, n3, n5, n7**can be negative. Then values of

**dp[L][][][][]**could be recalculated from values of

**dp[L-1][][][][]**as follows. For all arrays

**(n2, n3, n5, n7)**such that

**dp[L-1][n2][n3][n5][n7] ≠ 0**we iterate over all digits

**d**from

**1**to

**9**, inclusive, and add

**dp[L-1][n2][n3][n5][n7]**to

**dp[L][g2[d]-n2][g3[d]-n3][g5[d]-n5][g7[d]-n7]**, where

**d = 2**.

^{g2[d]}* 3^{g3[d]}* 5^{g5[d]}* 7^{g7[d]}The array for dp could created as

**dp[0…36][-54…54][-36…36][-18…18][-18…18]**.

But to avoid memory limit store dp-values only for two consecutive values of **L**.

To make computations modulo **2 ^{32}** simply use unsigned 32-bit integer type as it is.

During DP step save all non-zero answers to some array.

Then sort it and use binary search to answer each test case fast enough.

### EXPLANATION:

At first we assume that **V ≠ 0**, then it is clear that all digits in **N** should be non-zero. Hence we consider only such **N** from now on. The key observation is that **DIVPRO(N)** has the form **2 ^{n2} * 3^{n3} * 5^{n5} * 7^{n7}**, where

**n2, n3, n5, n7**arbitrary integers (even negative). This is because each non-zero decimal digit has only

**2, 3, 5, 7**as prime divisors. Hence integer

**V**should be of the same form but with non-negative

**n2, n3, n5, n7**, otherwise

**DIVPRO(N) ≠ V**for any

**N**. There are quite a few values of

**V**of this form up to

**10**- only 66,060. This suggests to calculate answers for all possible pairs of

^{18}**L**and

**V**, with

**V**of this form in advance, and answer each test almost instantly.

We now use dynamic programming to calculate **dp[L][n2][n3][n5][n7]** which is the count of **L**-digit positive integers **N** having **DIVPRO(N) = 2 ^{n2} * 3^{n3} * 5^{n5} * 7^{n7}**. Note that

**n2, n3, n5, n7**can be negative here.

The most convenient initialization is to set **dp[0][0][0][0][0] = 1** and **dp[0][n2][n3][n5][n7] = 0** for all other arrays **(n2, n3, n5, n7)**. It has the following meaning: the only **0**-digit number is an empty number which has **DIVPRO** value **1 = 2 ^{0} * 3^{0} * 5^{0} * 7^{0}** (it is math and CS convention to set empty products as 1).

It is quite clear how recalculation should be done. Let **d _{1}d_{2}…d_{L}** is decimal representation of

**N**. Then

**DIVPRO(N) = d**,

_{1}/ d_{2}* d_{3}/ d_{4}* … = d_{1}/ (d_{2}/ d_{3}* d_{4}/ …) = d_{1}/ DIVPRO(N’)where

**N’**is the

**(L-1)**-digit number with decimal representation

**d**.

_{2}d_{3}…d_{L}Now if

**DIVPRO(N’) = 2**and

^{n2}* 3^{n3}* 5^{n5}* 7^{n7}**d**then

_{1}= 2^{g2}* 3^{g3}* 5^{g5}* 7^{g7}**DIVPRO(N) = 2**.

^{g2-n2}* 3^{g3-n3}* 5^{g5-n5}* 7^{g7-n7}This observation shows that values of **dp[L][][][][]** could be recalculated from values of **dp[L-1][][][][]** as follows. For all arrays **(n2, n3, n5, n7)** such that **dp[L-1][n2][n3][n5][n7] ≠ 0** we iterate over all digits **d** from **1** to **9**, inclusive, and add **dp[L-1][n2][n3][n5][n7]** to **dp[L][g2[d]-n2][g3[d]-n3][g5[d]-n5][g7[d]-n7]**, where **d = 2 ^{g2[d]} * 3^{g3[d]} * 5^{g5[d]} * 7^{g7[d]}**. For example,

**g2[6] = 1, g3[6] = 1, g5[6] = 0, g7[6] = 0**. See tester’s solution if you have doubts regarding how values

**g2[d], g3[d], g5[d], g7[d]**are calculated for other digits.

So the problem seems like solved but there are several pitfalls wait for us. At first we should decide the sizes of the array we will use for DP. Let’s estimate for the given **L** in what range could vary each of **n2, n3, n5, n7** so that **dp[L][n2][n3][n5][n7]** is non-zero. Let **L1 = [(L+1)/2]** and **L2 = L − L1**, where **[x]** denotes an integer part of **x**. So **L1** is the number of digits at odd positions in the decimal representation of any **L**-digit number and **L2** is the same thing for even positions. At first let’s find bound on **n2**. It is clear that the maximal value of **g2[d]** is **3** (for **d = 8**). Hence if **N** is **L**-digit number and **DIVPRO(N) = 2 ^{n2} * 3^{n3} * 5^{n5} * 7^{n7}** then

**-3 * L2 ≤ n2 ≤ 3 * L1**. Indeed, the maximum possible value of

**n2**will be when we have all digits at odd positions of

**N**equal to

**8**while all digits at even positions are odd. Similarly, the minimum possible value of

**n2**will be when we have all digits at even positions of

**N**equal to

**8**while all digits at odd positions are odd. Since maximum value of

**g3[d]**is

**2**(for

**d = 9**) then for

**n3**we have

**-2 * L2 ≤ n2 ≤ 2 * L1**. Similarly for

**n5**and

**n7**we have

**-L2 ≤ n5 ≤ L1**and

**-L2 ≤ n7 ≤ L1**. At first note that these inequalities should be used in order to bound the range of arrays

**(n2, n3, n5, n7)**for which we will iterate at the dp-recalculation step. We could simply use 4 nested loops like:

for n2 from -3 * L2 to 3 * L1 do for n3 from -2 * L2 to 2 * L1 do for n5 from -L2 to L1 do for n7 from -L2 to L1 do do dp recalculation

These inequalities shows that in order to handle all values of **L** up to some **maxL** we should create an array of the form

**dp[0 … maxL][-3 * maxL2 … 3 * maxL1][-2 * maxL2 … 2 * maxL1][-maxL2 … maxL1][-maxL2 … maxL1]**,

using Pascal notation, where **maxL1 = [(maxL+1)/2]** and **maxL2 = maxL − maxL1**. We have **maxL = 36** so **maxL1 = maxL2 = 18** and explicit form of the array is

**dp[0…36][-54…54][-36…36][-18…18][-18…18]**.

The total number of elements in this array is **37 * 109 * 73 * 37 * 37 = 403,045,921**. Since we should use 32-bit integer type to deal with dp-values, this array will require more than 1.6GB of memory. Though it seems enormous number, Codechef modern server Cube almost allows this. Namely, the memory limit is 1536MB. One could think of some hacky way how to fix this memory issue like do manual precalc for **L = 1** and store in this array only dp-values for **L ≤ 2** but we explain how to reduce memory in more than 18 times keeping solution clear and elegant.

Note that in our DP we calculate all values of **dp[L][][][][]** from values of **dp[L-1][][][][]**, hence let’s store in memory only dp-values for two consecutive values of **L** each time. We could, for example, create an array of the form

**dp[0…1][-54…54][-36…36][-18…18][-18…18]**

and create the variable **p** that will be switched from **0** to **1** and vice versa each time. Its meaning is that **dp[p][][][][]** is the dp-values for **L** that we want to calculate at this step, while dp-values for **L-1** are stored in **dp[1-p][][][][]**. See tester’s solution as a reference for this trick.

But now in the end we will have dp-values only for **L = 35** and **L = 36**. In order to handle this issue we should iterate over **dp[p][][][][]** after we calculate all values in it and save all non-zero dp-values with the corresponding values of **V** to some array. Namely for each **L** we have array of pairs of the form **(V, dp_val)**. The value of **V** could be easily restored from the array **(n2, n3, n5, n7)**. To do this faster one could precompute all powers of 2, 3, 5, 7 that are less than **10 ^{18}** in advance and restore

**V**in

**O(1)**time. See tester’s solution as a reference.

After DP step we sort the corresponding array of pairs for each **L** and then use binary search to answer each test in **O(log X)** where **X ≤ 66060** is the number of values of **V** for which we have some non-zero dp-value.

Do we solve the problem? Actually, no - we forget the case **V = 0**. But it is quite simple. It is clear that **DIVPRO(N) = 0** if and only if all digits at even positions are non-zero (in order to avoid division by zero) while at least one digit at odd position is zero. Also not to forget about the first digit that could not be zero. Hence the count of such values of **L**-digit integers **N** could be found using basic combinatorics. Recall that we have **L1 = [(L+1)/2]** digits at odd positions and **L2 = L − L1** digits at even positions. For each of the digit at even position as well as for the first digit we have **9** independent choices (each digit from **1** to **9**, inclusive). It leads to the factor **9 ^{L2 + 1}** in the answer. For digits at odd positions (except the first digits) we count as follows. The total number of choices is

**10**but we should subtract those choices where all digits are non-zero which is

^{L1 − 1}**9**.

^{L1 − 1}Hence the final answer for

**V = 0**is

**9**.

^{L2 + 1}* (10^{L1 − 1}− 9^{L1 − 1})To keep solution clear we could add these pairs to the corresponding array of results for each

**L**.

**The final remark.** To create dp-array above in language that does not support such indexation we could create it as

**unsigned dp[2][2 * 54 + 1][2 * 36 + 1][2 * 18 + 1][2 * 18 + 1]**

and denote **dp[p][n2][n3][n5][n7]** above as **dp[p][54 + n2][36 + n3][18 + n5][18 + n7]**.

**The very final remark.** To do calculations modulo **2 ^{32}** you actually do not need to do any special. Just do all calculations using 32-bit integer type (signed and unsigned). Overflow that will occur during calculation behaves exactly as modulo

**2**operation. Only when you print the answer you need ensure that you print unsigned value.

^{32}**The final ever remark.** The complexity of the described solution is **O(maxL ^{5} * B + T * log maxL^{4})**, where

**B = 9**is the number of non-zero decimal digits. Indeed, we have outer loop over

**L**from

**1**to

**maxL**and inner nested 4 loops over

**(n2, n3, n4, n5)**where each loop is over

**O(L)**range. Finally, the most inner loop is over digits. But the constant hidden in this asymptotic is very small since we do the most inner loop over digits only for non-zero dp-values.

**maxL**is an upper bound for the number of values of

^{4}**V**for which we have some non-zero dp-value. We use binary search for

**T**tests over arrays of size with upper bound

**O(maxL**, hence the final term in complexity.

^{4})### ALTERNATIVE SOLUTION:

You will find something very different in author’s solution. Since this solution is not faster than described above but a bit complicated please follow comments there to understand it.

The fastest solution to this problem, of course, should use some incredibly fast I/O (which was discussed several time at codechef). But the main thing that will make it really fast is some neat precalc that based on the fact that digits other than **5** and **7** contains only **2** and **3** as a prime factors. This allows to do similar precalc as above but considering separately numbers without **5** and **7** and numbers having only **5** and **7** as digits. Then the answer for each **L** and **V** can be calculated in **O(L)** time using some easy combinatorial reasoning that involves binomial coefficients and precalcuted tables. Refer to ACRush solution or m1sterzer0 solution.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.