This is a problem I met on a Chinese online judge six years ago.

~~I'm not sure if it is a problem from another place.~~

It's SGU 420 -- Number Permutations from 2007-2008 Summer Petrozavodsk Camp, Petr Mitrichev Contest 3. (Thanks to Claris.)

Here's the problem:

**Two different positive integers are considered similar if the numbers of their digits are the same, and the multisets of their digits are the same as well.**

**Given integers $$$l$$$ and $$$r$$$, count the number of integers $$$x$$$ ($$$l \leq x \leq r$$$) such that there is exactly one integer $$$y$$$ ($$$l \leq y \leq r$$$, $$$x \neq y$$$) satisfying that $$$x$$$ and $$$y$$$ are similar.**

**$$$1 \leq l \leq r \leq 10^{15}$$$**

A few random examples of similar numbers:

- 6892, 6928, 6982, 8269 are similar
- 5986656, 5986665, 6556689, 6556698 are similar
- 2983321011, 2983321101, 2983321110, 3011122389 are similar
- 797776555322101, 797776555322110, 901122355567777, 901122355576777 are similar

**UPD:** I've solved this problem. I'll soon elaborate my solution in the comment.

What is the meaning of the first constraint "numbers of their digits are the same"? It seems redundant given the multiset condition.

Yes, it's redundant. Probably the statement wants to emphasize that $$$x$$$ and $$$y$$$ both have no leading zeros.

Let $$$next(x)$$$ be the number $$$y$$$ whose digits are the next lexicographically-ordered permutation of digits of $$$x$$$. In case $$$y$$$ doesn't exist, let $$$next(x)$$$ be $$$\infty$$$.

Let $$$prev(y)$$$ be the number $$$x$$$ whose digits are the previous lexicographically-ordered permutation of digits of $$$y$$$. In case $$$x$$$ doesn't exist or $$$x$$$ contains leading zeros, let $$$prev(y)$$$ be $$$-\infty$$$.

It is equivalent to count the pairs of $$$(x, y)$$$ such that $$$next(x) = y$$$ and $$$prev(x) < l \leq x < y \leq r < next(y)$$$. Obviously, the answer is twice its number.

Let's take a look at the algorithm (in linear time complexity) to find the next permutation of an array $$$a_1, a_2, \ldots, a_m$$$:

For example, $$$12\color{red}{3}\color{blue}{4} \to 12\color{blue}{4}\color{red}{3}$$$, $$$\color{red}{1}\color{blue}{2}11 \to \color{blue}{2}11\color{red}{1}$$$ and $$$\color{red}{5}9866\color{blue}{6}5 \to \color{blue}{6}5\color{red}{5}6689$$$.

When we care about at most $$$4$$$ adjacent permutations of digits, those digits that are useful for the algorithm of finding next permutation must be in the lowest $$$3$$$

non-increasingblocks, for instance, $$$\color{red}{7}\color{green}{9777655532210}\color{blue}{1}, \color{red}{7}\color{blue}{97776555322110}, 9011223555\color{red}{6}\color{blue}{7777}, 9011223555\color{red}{76}\color{blue}{777}$$$. But actually, do we really need to care about maybe a huge number of situtations? No.In most cases, the difference between integers corresponding to $$$2$$$ adjacent permutations is quite small, such as $$$(6556689, 6556698)$$$ and $$$(797776555322101, 797776555322110)$$$. It is because the lowest

non-decreasingblock is long enough, and we can only consider them when finding the next permutation.The case that the difference between two adjacent similar integers $$$x, y$$$ is large is when the lower integer has a long

non-increasingblock. But in that case, the next similar integer $$$z$$$ usually comes with a fairly small difference of $$$(z - y)$$$.It inspires that, in most cases, we can enumerate $$$(prev(x), x)$$$ or $$$(y, next(y))$$$, such that the difference of those two is small enough. The reason we only enumerate these two kinds but $$$(x, y)$$$ is that no matter in which of those two cases, we know $$$x$$$ or $$$y$$$ is close to $$$l$$$ or $$$r$$$.

In case that $$$prev(x) = -\infty$$$ and $$$next(y) = \infty$$$, we can conclude $$$12 \leq x < y \leq 98$$$, since $$$x$$$ must have at least two types of digits, and thus the number of all possible permutations of its digits is no less than its length. Since the difference is small, this situation can be enumerated by the above method, so we can avoid discussing it.

In case that $$$prev(x) = -\infty$$$, the digits of $$$x$$$ is in non-decreasing order, which implies the difference $$$(prev(y) - y)$$$ may be considerable. So as for $$$next(y) = \infty$$$.

Let's assume that we have handled all the cases with differences less than $$$10^3$$$. What are the rest cases? You may observe that the rest case is only like $$$(677777, 767777)$$$ and $$$(676666, 667666)$$$. Why? Because if the lowest $$$3$$$ digits are not the same, it will form many permutations and be enumerated in the above. Hence, we can enumerate the lowest digits in the form of $$$(p q q \ldots q, q p q \ldots q)$$$, $$$(p q p \ldots p, q p p \ldots p)$$$, and determine if they could form an interval that covers $$$l$$$ or $$$r$$$.

In summary:

Time complexity: $$$\mathcal{O}(D^3 L + D^2 L^2)$$$, where $$$D = 10$$$ is the number of possible digits, $$$L = 15$$$ is the maximal length of a number.