Let \(x_i\) be the \(i\)‘th digit of \(X\) from the top. Let \(a_i\) be the answer in case we use only the first \(i\) digits of \(X\). Assume we fix \(x_{i-1}\) and before. Then we can see that \(a_i\) is a linear function of \(x_i\), by considering the contributions to \(a_i\). More specifically, we have two contributions:

• the slope of the function is \(s_i:=1+\displaystyle\sum_{j<i} a_j\)
• the constant is \(10a_{i-1}\)

For the slope, consider where we have the last separator. For the constant, consider in the case when \(x_i=0\). Now we have \(a_i=10a_{i-1} + x_i s_i\), which can be calculated in \(O(N)\) time, with managing cumulative sum appropriately.

AC code （PyPy3）