PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
One solution is to precompute such valid numbers and store them in the solution. However, there are too many of them to store. The next step is to observe that most numbers actually have the same digits, but just differently arranged. Thus, we just precompute unique digit sequences such that permutations of these digits give valid numbers. There are only 13 such sequences. Precomputation shouldnt take too long (takes around 3 minutes for me).
Now, we start by generating all valid numbers. For each of these 13 sequences, we consider all permutations of them and check which ones are valid numbers. There are around 56000 of them. Now, each query can be answered in logarithmic time by sorting this array of valid numbers and performing binary search to see how many numbers in this sequence are in the range A…B.