Hints → https://atcoder.jp/contests/arc153/editorial/5524

---

Let \(N\) denote the number of digits in \(Y\).

[1] An \(\Theta(N^2)\)-time solution

It is clear that the following greedy strategy obtains \(f(X)\) from \(X\).

• Initialize \(S\) as an empty string.
• Let \(N\) be the number of digits in \(X\). For \(i = 1, \ldots, N\) in this order, do the following: if the \(i\)-th character in the decimal notation of \(X\) is greater than the first character of \(S\) at that point, insert it at the end of \(S\); otherwise, insert it at the beginning of \(S\).
• Let \(Y\) be the positive integer represented by the string \(S\).

Thus, the problem can be solved in a time complexity of \(\Theta(N^2)\) by dynamic programming where the following is computed in appropriate order.

• \(\text{dp}[L][R]\): the number of integers \(X\) that yield the \(L\)-th through \(R\)-th characters of \(Y\).

When \(L < R\), \(\text{dp}[L][R]\) can be computed using \(\text{dp}[L+1][R]\) and \(\text{dp}[L][R-1]\). More specifically,

• if \(Y_L \leq Y_{L+1}\), add \(\text{dp}[L+1][R]\) to \(\text{dp}[L][R]\);
• if \(Y_L < Y_R\), add \(\text{dp}[L][R-1]\) to \(\text{dp}[L][R]\).

---

For instance, the transitions in this dynamic programming for the case \(Y = 12234433442\) (sample 3) are shown below.

The answer is the number of paths from the cells on the diagonal to the top-right corner.

---

[2] Deleting useless transitions

In the above transitions, let us remove the computations that clearly do not affect the answer.

When \(Y_i > Y_{i+1}\), one does not have to compute \(\text{dp}[L][R]\) for \(L\) such that \(i < L\), because there are no transitions from \(\text{dp}[i+1][-]\) to \(\text{dp}[i][-]\).

When \(L < i\) and \(Y_L \geq Y_i\), one does not have to compute \(\text{dp}[L][R]\) for \(R\) such that \(i \leq L\), because such \(\text{dp}[L][R]\) are always \(0\).

---

[3] Speeding up the computation

Let us consider computing \(\text{dp}[L][-]\) in the order \(L = N, N-1, \ldots, 1\). After deleting the useless transitions above, it can be seen that one can obtain \(\text{dp}[L-1][-]\) from \(\text{dp}[L][-]\) by the following operations:

• add \(1\) to the beginning, and
• compute the cumulative sums for some range determined by the value of \(Y_L\).

For the same value of \(Y_L\), the cumulative sums are repeatedly computed for the same range, so the computation for this part can be combined into convolution with some sequence of binomial coefficients.

Therefore, the problem can be solved in a time complexity of \(O(N\log N)\) by computing the convolution of length-\(N\) sequences at most \(9\) times.