Two Sorts
Contest: Codeforces Round 751 (Div. 1)
Difficulty rating: 3400
Tags: binary search, dfs and similar, math, meet-in-the-middle

Integers from $$$1$$$ to $$$n$$$ (inclusive) were sorted lexicographically (considering integers as strings). As a result, array $$$a_1, a_2, \dots, a_n$$$ was obtained.

Calculate value of $$$(\sum_{i = 1}^n ((i - a_i) \mod 998244353)) \mod 10^9 + 7$$$.

$$$x \mod y$$$ here means the remainder after division $$$x$$$ by $$$y$$$. This remainder is always non-negative and doesn't exceed $$$y - 1$$$. For example, $$$5 \mod 3 = 2$$$, $$$(-1) \mod 6 = 5$$$.

Input format:
The first line contains the single integer $$$n$$$ ($$$1 \leq n \leq 10^{12}$$$).

Output format:
Print one integer — the required sum.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

For example, $$$42$$$ is lexicographically smaller than $$$6$$$, because they differ in the first digit, and $$$4 < 6$$$; $$$42 < 420$$$, because $$$42$$$ is a prefix of $$$420$$$.

Let's denote $$$998244353$$$ as $$$M$$$.

In the first example, array $$$a$$$ is equal to $$$[1, 2, 3]$$$.

- $$$(1 - 1) \mod M = 0 \mod M = 0$$$
- $$$(2 - 2) \mod M = 0 \mod M = 0$$$
- $$$(3 - 3) \mod M = 0 \mod M = 0$$$

As a result, $$$(0 + 0 + 0) \mod 10^9 + 7 = 0$$$

In the second example, array $$$a$$$ is equal to $$$[1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9]$$$.

- $$$(1 - 1) \mod M = 0 \mod M = 0$$$
- $$$(2 - 10) \mod M = (-8) \mod M = 998244345$$$
- $$$(3 - 11) \mod M = (-8) \mod M = 998244345$$$
- $$$(4 - 12) \mod M = (-8) \mod M = 998244345$$$
- $$$(5 - 2) \mod M = 3 \mod M = 3$$$
- $$$(6 - 3) \mod M = 3 \mod M = 3$$$
- $$$(7 - 4) \mod M = 3 \mod M = 3$$$
- $$$(8 - 5) \mod M = 3 \mod M = 3$$$
- $$$(9 - 6) \mod M = 3 \mod M = 3$$$
- $$$(10 - 7) \mod M = 3 \mod M = 3$$$
- $$$(11 - 8) \mod M = 3 \mod M = 3$$$
- $$$(12 - 9) \mod M = 3 \mod M = 3$$$

As a result, $$$(0 + 998244345 + 998244345 + 998244345 + 3 + 3 + 3 + 3 + 3 + 3 + 3 + 3) \mod 10^9 + 7$$$ $$$=$$$ $$$2994733059 \mod 10^9 + 7$$$ $$$=$$$ $$$994733045$$$

Example input:
3

Example output:
0

Example input:
12

Example output:
994733045

Editorial:
Suppose $$$b$$$ is an inverse permutation of $$$a$$$, that is $$$a_{b_{i}} = b_{a_i} = i$$$, that is $$$b_i$$$ is an index of $$$i$$$ in the lexicographical sorting. Rewrite desired sum replacing $$$i \to b_i$$$: $$$\sum_{i=1 \ldots n} ((i - a_i) \bmod p) = \sum_{i=1 \ldots n} ((b_i - a_{b_i}) \bmod p) = \sum_{i=1 \ldots n} ((b_i - i) \bmod p)$$$.
First, we need to understand how to calculate $$$b_i$$$'s. Observe that $$$b_i$$$ equals $$$1$$$ plus number of integers $$$x$$$ ($$$1 \le x \le n$$$) so that $$$x <_{lex} i$$$. These integers are of two possible kinds: own prefixes of $$$i$$$ (the number of such $$$x$$$ depends only on the length of $$$i$$$) and integers $$$x$$$ having a common prefix with $$$i$$$ of some length $$$t$$$ and a smaller digit $$$c$$$ in $$$(t+1)$$$-th index.
If we fix values of $$$t$$$, $$$c$$$, length of $$$x$$$, we have a "mask" of the following kind: "123???", and we are interested in the number of $$$x$$$ matching this mask. This number almost always depends on the number of "?" with minor exceptions concerning $$$n$$$. E. g. consider $$$n = 123456$$$ for the example above.
So in the desired sum, we group summands by the following markers of $$$i$$$ (brute force the value of these markers):
• Length of $$$i$$$,
• Position of first digit different in $$$i$$$ and $$$n$$$ (cases, where $$$i$$$ is an own prefix of $$$n$$$, shall be considered separately).
• The value of this digit.
So we know description of $$$i$$$ of the following kind: $$$i = \overline{c_1 c_2 \ldots c_k x_1 \ldots x_l}$$$, where $$$c_j$$$ are fixed, and $$$x_1, \ldots, x_l$$$ are arbitrary integer variables in $$$[0, 9]$$$. Observe that both $$$b_i$$$ and $$$i$$$ are linear combination of variables $$$x_j$$$ and $$$1$$$, so $$$b_i - i$$$ is also a linear combination of them. The only issue is computing $$$b_i - i$$$ modulo $$$p$$$.
To do summing over all $$$x_1, \ldots, x_l$$$ we use the meet-in-the-middle method: bruteforce separately the values for the first half and the second half, and then match one with another.
If $$$n \le 10^L$$$, the solution works in $$$\mathcal{O}(10^{\frac{L}{2}} \operatorname{poly}(L))$$$, or $$$\mathcal{O}(\sqrt{n}\, \operatorname{poly}(\log n))$$$.