PROBLEM LINK:
Author: Vivek Hamirwasia
Tester: Anton Lunyov
Editorialist: Anton Lunyov
DIFFICULTY:
MEDIUM
PREREQUISITES:
PROBLEM:
If positive integer N has decimal representations d1d2…dL, where n1 ≠ 0, then DIVPRO(N) = d1 / d2 * d3 / d4 * …. If at some point division by zero occurs the DIVPRO(N) is undefined (so digits at even positions should be non-zero). For the given integers 0 ≤ V < 1018 and 1 ≤ L ≤ 36 you need to find the number of positive L-digit integers N having DIVPRO(N) = V and output this number modulo 232. You should be able to answer up to 320,000 such tests in 3 seconds.
QUICK EXPLANATION:
If V = 0 then the count is 9L − X * (10X − 9X) where X = floor((L − 1) / 2).
When V > 0 the answer is non-zero only when V has the form 2n2 * 3n3 * 5n5 * 7n7.
Let dp[L][n2][n3][n5][n7] be a count of L-digit positive integers N having DIVPRO(N) = 2n2 * 3n3 * 5n5 * 7n7, 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 = 2g2[d] * 3g3[d] * 5g5[d] * 7g7[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 232 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 2n2 * 3n3 * 5n5 * 7n7, 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 1018 - only 66,060. This suggests to calculate answers for all possible pairs of 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) = 2n2 * 3n3 * 5n5 * 7n7. 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 = 20 * 30 * 50 * 70 (it is math and CS convention to set empty products as 1).
It is quite clear how recalculation should be done. Let d1d2…dL is decimal representation of N. Then
DIVPRO(N) = d1 / d2 * d3 / d4 * … = d1 / (d2 / d3 * d4 / …) = d1 / DIVPRO(N’),
where N’ is the (L-1)-digit number with decimal representation d2d3…dL.
Now if DIVPRO(N’) = 2n2 * 3n3 * 5n5 * 7n7 and d1 = 2g2 * 3g3 * 5g5 * 7g7 then
DIVPRO(N) = 2g2-n2 * 3g3-n3 * 5g5-n5 * 7g7-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 = 2g2[d] * 3g3[d] * 5g5[d] * 7g7[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) = 2n2 * 3n3 * 5n5 * 7n7 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 1018 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 9L2 + 1 in the answer. For digits at odd positions (except the first digits) we count as follows. The total number of choices is 10L1 − 1 but we should subtract those choices where all digits are non-zero which is 9L1 − 1.
Hence the final answer for V = 0 is 9L2 + 1 * (10L1 − 1 − 9L1 − 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 232 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 232 operation. Only when you print the answer you need ensure that you print unsigned value.
The final ever remark. The complexity of the described solution is O(maxL5 * B + T * log maxL4), 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. maxL4 is an upper bound for the number of values of 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(maxL4), hence the final term in complexity.
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.
I had everything in place except the n2 n3 n5 n7 taking negative values… wasted 10 days just because of this 
