ヒント → https://atcoder.jp/contests/arc153/editorial/5482

---

\(Y\) の桁数を \(N\) と書きます．

[1] \(\Theta(N^2)\) 時間での解法

次の貪欲法により \(X\) から \(f(X)\) が得られることは明らかです：

• 文字列 \(S\) を空文字列で初期化する．
• \(X\) の桁数を \(N\) とするとき，\(i = 1, \ldots, N\) の順に次を行う：\(X\) の \(10\) 進法表記の \(i\) 文字目が，その時点での \(S\) の先頭より大きいならば \(S\) の末尾，そうでなければ \(S\) の先頭に追加する．
• 文字列 \(S\) が表す正整数を \(f(X)\) とする．

したがって，本問題は次を適切な順に計算する動的計画法によって，時間計算量 \(\Theta(N^2)\) で解くことができます：

• \(Y\) の \(L\) 文字目から \(R\) 文字目までが得られるような \(X\) の個数を \(\text{dp}[L][R]\) と定める．

\(L < R\) のとき，\(\text{dp}[L][R]\) は \(\text{dp}[L+1][R]\) と \(\text{dp}[L][R-1]\) から計算することができます．より詳しくは次の通りです：

• \(Y_L \leq Y_{L+1}\) ならば \(\text{dp}[L][R]\) に \(\text{dp}[L+1][R]\) を加算する．
• \(Y_L < Y_R\) ならば \(\text{dp}[L][R]\) に \(\text{dp}[L][R-1]\) を加算する．

---

例えば \(Y = 12234433442\) （入出力例 3）の場合について、この動的計画法の遷移を図示してみると，次のようになります．

この図において，対角線部分のセルから右上隅までの経路数を数え上げると答になります．

---

[2] 無駄な遷移の削除

[1] の動的計画法の遷移において，明らかに答に影響しない計算を間引きましょう．

\(Y_i > Y_{i+1}\) であるとき，\(i < L\) であるような \(L\) に対する \(\text{dp}[L][R]\) は計算する必要がありません．\(\text{dp}[i+1][-]\) から \(\text{dp}[i][-]\) への遷移がないためです．

\(L < i\) かつ \(Y_L \geq Y_i\) のとき，\(i \leq R\) であるような \(R\) に対する \(\text{dp}[L][R]\) は計算する必要がありません．そのような \(\text{dp}[L][R]\) は常に \(0\) 通りだからです．

---

[3] 計算の高速化

\(L = N, N-1, \ldots, 1\) の順に \(\text{dp}[L][-]\) を計算することを考えます．上述のように無駄な遷移を削除すると，\(\text{dp}[L][-]\) から \(\text{dp}[L-1][-]\) を得るには

• 先頭に \(1\) を追加する
• \(Y_L\) の値によって決まる適当な範囲の累積和をとる

という操作をすればよいことが分かります．

\(Y_L\) が一定である間は，同じ範囲で累積和をとることが繰り返されるため，この部分は適当な二項係数の列との畳み込みでまとめて計算することができます．

以上により，本問題は長さ \(N\) の列の畳み込みの計算を \(9\) 回以下行うことによって，時間計算量 \(O(N\log N)\) で解くことができます．