Ever-Hungry Krakozyabra
Contest: Codeforces Round 426 (Div. 1)
Difficulty rating: 2700
Tags: brute force, combinatorics, greedy, math

Recently, a wild Krakozyabra appeared at Jelly Castle. It is, truth to be said, always eager to have something for dinner.

Its favorite meal is natural numbers (typically served with honey sauce), or, to be more precise, the zeros in their corresponding decimal representations. As for other digits, Krakozyabra dislikes them; moreover, they often cause it indigestion! So, as a necessary precaution, Krakozyabra prefers to sort the digits of a number in non-descending order before proceeding to feast. Then, the leading zeros of the resulting number are eaten and the remaining part is discarded as an inedible tail.

For example, if Krakozyabra is to have the number 57040 for dinner, its inedible tail would be the number 457.

Slastyona is not really fond of the idea of Krakozyabra living in her castle. Hovewer, her natural hospitality prevents her from leaving her guest without food. Slastyona has a range of natural numbers from L to R, which she is going to feed the guest with. Help her determine how many distinct inedible tails are going to be discarded by Krakozyabra by the end of the dinner.

Input format:
In the first and only string, the numbers L and R are given – the boundaries of the range (1 ≤ L ≤ R ≤ 1018).

Output format:
Output the sole number – the answer for the problem.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first sample case, the inedible tails are the numbers from 1 to 9. Note that 10 and 1 have the same inedible tail – the number 1.

In the second sample case, each number has a unique inedible tail, except for the pair 45, 54. The answer to this sample case is going to be (57 - 40 + 1) - 1 = 17.

Example input:
1 10

Example output:
9

Example input:
40 57

Example output:
17

Editorial:
Prerequisites: Combinatorics or strong faith :)
At first we might assume (without loss of generality) that both left and right bounds are strictly less than 1018 (otherwise we just append 1 to the list of unedible tails) and hence consider only numbers with no more than 18 decimal digits.
Notice that there are not than many numbers without leading zeros: they are no more than $$( \frac { 1 8 + 9 } { 9 } )$$ (the number of solutions to c1 + c2 + ... + cn ≤ 18, where ci — the number of i-s in a number). To be precise, there are only 4686824 such numbers in range 1  →  1018. Thus we might simply brute all such numbers and for a fixed candidate (let's denote it as A), whether it is possible (using some additional zeros if neccessary) to form the number A' from the range [L, R].
How do we check it rapidly? Let's represent L and R as vectors of length n (we might add some leading zeros to L if neccessary), and A — as an array num (with possible additional zeros).
We will brute it in the following way: go(pos, lflag, rflag), which keeps out current position and indicates whether the currently obtained number is equal to the corresponding prefix of L / R. Several cases to consider:
• If (pos = n), we return true.
• If (lflag = 1) и (rflag = 1), we strictly follow the prefixes of L and R. There are two deeper cases:   If L(pos) = R(pos), the only way out is to place L(pos), decrease the number of corresponding digits in num and proceed to go(pos + 1, 1, 1).  Else if L(pos) < R(pos), we have to check if there's an element in [L(pos) + 1, R(pos) - 1]. It's obvious that the answer is true in this case (since after we get right between L and R we can assign the suffix whichever way we want). Otherwise we first consider the possibility of placing L(pos) and proceeding to go(pos + 1, 1, 0) or placing R(pos) and proceeding to go(pos + 1, 0, 1). If nothing returns true, the answer is false;
• If L(pos) = R(pos), the only way out is to place L(pos), decrease the number of corresponding digits in num and proceed to go(pos + 1, 1, 1).
• Else if L(pos) < R(pos), we have to check if there's an element in [L(pos) + 1, R(pos) - 1]. It's obvious that the answer is true in this case (since after we get right between L and R we can assign the suffix whichever way we want). Otherwise we first consider the possibility of placing L(pos) and proceeding to go(pos + 1, 1, 0) or placing R(pos) and proceeding to go(pos + 1, 0, 1). If nothing returns true, the answer is false;
• If only left flag is active (lflag = 1), we need a random digit from the suffix [L(pos) + 1, 9]. If we find it — the answer is true. If no — we try L(pos) and go(pos + 1, 1, 0) or return false.
• A lone right flag is processed in a simular way with the only difference that we try the [0, R(pos) - 1] prefix or R(pos) and go(pos + 1, 0, 1).
At a first glance it seems that out bruteforce will end up being O(2n). But an easy observation shows that there can be no more that two separate branches here. The total bruteforce complexity is O(10·n).
Complexity: $$O \left( {K+9 \choose 9} \cdot K \right)$$, where K stands for the maximum number length.