PROBLEM LINK:
Author: Sergey Kulik
Tester: Kevin Atienza and Istvan Nagy
Editorialist: Kevin Atienza
PREREQUISITES:
Counting
PROBLEM:
Two numbers are isomorphic if the digits of one is just a relabelling of the other, and vice versa. Let F(n) be the lowest number isomorphic to n with the same number of digits. Given N and M, find F(1) \bmod M + F(2) \bmod M + \cdots + F(N) \bmod M.
QUICK EXPLANATION:
Let’s call a number V viable if there is an n such that F(n) = V. Note that a number V is viable if and only if, after we treat V as a string of digits and after removing every digit that has already appeared in the string, the resulting string of digits is a prefix of 1023456789. For example, 1010212 is viable.
First, if N = 10^k for some k, compute F(N) \bmod M separately, and decrement N by 1. Therefore, we can now assume that N has at most 11 digits 
Next, collect all viable numbers up to 10^{11} - 1. One can show that the number of such values for a fixed number of digits is equal to a Bell number, so there are less than a million numbers in total.
Next, for any such viable number V, Let C(V) be the number of n s such that 1 \le n \le N and F(n) = V. C(V) can be computed using a backtracking procedure. The answer is therefore \sum_V (V\bmod M)\cdot C(V) for all viable numbers V \le N.
EXPLANATION:
We first note that N can reach up to 10^{11}, so an O(N) solution (or worse) will surely fail. We therefore need to find another strategy to compute the answer.
Let’s call a number V viable if there is an n such that F(n) = V. Now, what does a viable number look like? Well, n and V are isomorphic, so each digit in n corresponds to a digit in V. Thus, we must choose a relabelling of n that corresponds to the smallest possible V. In this case, the greedy algorithm works: choose the next digit to relabel in n, and relabel it with the smallest digit not yet used. Care must be taken though that we do not introduce leading zeroes, so we use 1 in the first turn and 0 in the second. But for subsequent relabelings, we use the remaining digits in increasing order. For example, in the number 2424969, we replace 2 with 1, 4 with 0, and 9 with 2, so F(2424929) = 1010212. It is not a difficult task to prove why this works.
Count each F(n)
Now that we know how a viable number looks like, one possible strategy to compute the answer is to enumerate all viable numbers \le N and count for each viable number how many times it appears as F(n) for n \le N. In other words, if C(V) is this number for the viable number V, then the answer is \sum_V (V\bmod M)\cdot C(V) for all viable numbers V \le N. This is great, assuming we can do the following things:
- Enumerate all viable numbers V
- Compute C(V) for every viable number V
This also assumes that the number of viable numbers \le N is small enough for this algorithm to pass the time limit. Let’s count them; specifically, let us count the number of viable numbers < 10^{11}. It can be easily shown that the number of K-digit viable numbers is simply the K-th Bell number which is the number of ways to partition a set of K labelled elements (to see why, consider the digits as the “labelled” elements. Any given partition corresponds to exactly one assignment of digits to create a viable number using the greedy procedure above). Therefore, we conclude that there are exactly 820987 viable numbers < 10^{11}, which is definitely manageable!
Note: Notice that in the above, we only considered viable numbers of up to 11 digits. However, N can reach up to 10^{11}, which has 12 digits. To get around that, notice that there is exactly one N having 12 digits, i.e. 10^{11} itself, so if N = 10^{11}, then we should just decrement N by 1 and add F(N) \bmod M separately! Notice also that F(10^{11}) = 10^{11}, so we only need to add 10^{11} \bmod M to the final answer. Therefore, we can now assume that N has at most 11 digits
Enumerating all viable numbers
Let’s start by enumerating all viable numbers. There’s a way to enumerate all such numbers efficiently. To do so, we first write down an equivalent description of viable numbers:
A number V is viable if and only if, after we treat V as a string of digits and after removing every digit that has already appeared in the string, the resulting string of digits is a prefix of S := 1023456789.
This means that, if we try to construct a viable number from the most significant to the least significant digit, either we reuse a digit, or add the next digit in S that is unused. This gives us a hint to define the following function: E(K,D), which enumerates all K-digit viable “strings”, assuming D distinct digits have already been introduced. Here’s a possible pseudocode:
S = [1,0,2,3,4,5,6,7,8,9]
def E(K,D):
// enumerates all K-digit viable "strings", assuming D distinct digits can be reused
if K == 0:
// output only the empty string
output ""
else:
// try reusing a digit
for d in 0..D-1:
for t in E(K-1,D):
output S[d] + t
// try using a new digit from S
for t in E(K-1,D+1):
output S[D] + t
After defining E(K,D), we can now enumerate all K-digit viable numbers by calling E(K,0)
Note that the you should try to optimize your implementation of the above, because the above runs in 820987\cdot 11 iterations instead of just 820987 (because we’re appending strings). One possible implementation of the above would be to output “numbers” instead of “strings”, and to “append” digits in front of the others quickly, you should precompute powers of ten, multiply the digits with appropriate powers of ten and add. For example, to attach 5 to 1230, we use the fact that 51230 = 5\cdot 10^4 + 1230.
Computing C(V)
Now, let’s focus on computing C(V), which is the number of integers n \le N isomorphic to V. Let us forget the requirement n \le N first, i.e. let’s count how many integers are isomorphic to V.
Notice that if n is isomorphic to V then there is a mapping from the digits of V to the digits of n. If V has D distinct digits, then by the above, we know that exactly the digits 1, 0, 2, \ldots, D-1, appear. So we should count how many ways we can map these digits to other digits to form n. There are 9 choices for 1 (because leading zeroes are not allowed), 9 choices for 0 (because the digit 0 is now available), 8 choices for 1 (we can’t reuse digits), 7 choices for 2, etc. Therefore, there are \frac{9\cdot 9!}{(10-D)!} ways to map the digits, and there are \frac{9\cdot 9!}{(10-D)!} integers n isomorphic to V Note that \frac{9\cdot 9!}{(10-D)!} is just \frac{9}{10}P_{10,D} where P_{n,k} is the number of k-permutations of n, and \frac{9}{10} is a factor that filters out numbers with leading zeroes.
Now, what if we require n \le N? Some of the n's isomorphic to V might be greater than N. But note that n should have the same number of digits as V. This means that if V has fewer digits than N, then any number isomorphic to V will automatically be \le N, i.e. C(V) = \frac{9\cdot 9!}{(10-D)!}. Thus we can now focus on the case where V and N have the same number of digits.
Let’s say V and N have K digits, and also V has D distinct digits (so D \le K). Let’s refer to the digits of a K-digit integer n as n_{K-1}, \ldots, n_1, n_0, where n_0 is the least significant digit. Let’s define a function C(V,i,\phi), which returns the number of integers n \le N isomorphic to V with the following constraints:
- \phi is the mapping of digits from V to n we have assigned so far, i.e. \phi(V_j) = n_j for all 0 \le j < K.
- 0 \le i \le K, and all the digits from V_i to V_{K-1} have already been assigned digits, i.e. all \phi(V_j), j \ge i are defined and are consistent.
- \phi(V_j) = n_j = N_j for all j \ge i, i.e. the digits of n and N from the i th least significant match.
Note that C(V) is just equal to C(V,K,\{\}), where \{\} denotes an empty mapping.
Now, how do we compute C(V,i,\phi)? Let’s handle a few easy cases first. If i = 0, then all digits have been assigned already, so C(V,i,\phi) is simply 1. Otherwise, we have to figure out which digit to assign V_{i-1} to. But if it’s already assigned before, i.e. \phi(V_{i-1}) is defined, then we only have one choice. There are three cases:
- If \phi(V_{i-1}) < N_{i-1}, then any choice for the following digits of n will automatically guarantee n < N. Therefore, if we already assigned t digits, i.e. the number of keys of \phi is t, this means there are D-t digits left to be assigned. Since there are 10-t digits remaining, the result is P_{10-t,K-t} = \frac{(10-t)!}{(10-D)!}.
- If \phi(V_{i-1}) > N_{i-1}, then any choice for the following digits of n will guarantee n > N, so the result is 0.
- If \phi(V_{i-1}) = N_{i-1}, then we’re good so far, and the result, by definition, is C(V,i-1,\phi).
Now, what happens when V_{i-1} is not yet assigned, i.e. \phi(V_{i-1}) is not yet defined? Then we can choose it to be any digit \le N_{i-1} that isn’t taken yet, i.e. that is not a value \phi(k) for some key k. To do so, we enumerate all such untaken d s, and handle the case where d < N_{i-1} and d = N_{i-1}:
- If d < N_{i-1}, then any choice for the following digits of n will automatically guarantee n < N. Therefore, if we have already assigned t digits, i.e. the number of keys of \phi is t, and we plan to assign V_{i-1} to d, this means there are D-t-1 digits left to be assigned. Since there are 9-t digits remaining, the result is P_{9-t,D-t-1} = \frac{(9-t)!}{(10-D)!}.
- If d = N_{i-1}, then we’re good so far, and the result, by definition, is C(V,i-1,\phi'), where \phi' is just \phi with the additional mapping V_{i-1} \rightarrow N_{i-1}.
Care must also be taken to avoid adding leading zeroes. Therefore, if i = K, we should exclude the case d = 0 above.
We have now covered all cases, and we can show that the above runs in O(K) = O(\log N) time in the worst! Take note though that it runs faster in many cases.
Minor Optimizations
If you implement all the things above naïvely, you might get the TLE (time limit exceeded) verdict. If that’s the case, then you should try optimizing your implementation, because the time limit is a bit tight. Here are a few suggestions:
- When computing C(V,i,\phi), we also need the values K (the number of digits of N and V), D (the number of distinct digits of V) and \frac{(10-t)!}{(10-K)!}. You should precompute K and all the \frac{i!}{j!} values beforehand, and D can be computed for each viable number during enumeration by using bitmasks and bit counting to keep track which digits are present in each number.
- Since we need to access the digits of V in decreasing order, you must be able to extract the digits of V quickly. You can do this either by dividing V by a suitably chosen power of 10 and getting the last digit, or by simply generating the reversal of the digits of V during the enumeration.
- While computing C(V,i,\phi) and V_{i-1} is not yet assigned, we need to enumerate all digits d \le N_{i-1} that haven’t yet been assigned. But take note that for all cases d < N_{i-1}, the answer is the same, i.e. \frac{(9-t)!}{(10-D)!}, so you can ditch the loop by just counting all such digits in time using bitmasks to keep track which digits are still available.
By carefully implementing the above optimizations, you should be able to get your program accepted within the time limit
Time Complexity:
O(B(N) \log N) where B(N) is the number of distinct values in \{F(1), F(2), \ldots, F(N-1)\}. Note that B(10^{11}) = 820987.