For simplicity, we consider \(X\) as a length-\(N\) string and denote by \(X[L:R]\) the integer represented by the substring consisting of \(L\)-th through \(R\)-th characters in base \(10\).

Utilizing Dynamic Programming (DP)

Let \(dp_i\) be the answer to this problem when \(N\) and \(X\) are \(i\) and \(X[1:i]\), respectively. Note that the new version may not satisfy the original Constraints, such as when \(dp_0 = 1\) and \(dp_1 = X[1:1]\).

Here, considering the maximum \(j \in S\), we have \(dp_i = \displaystyle\sum_{j=0}^{i-1}dp_{j} X[j+1:i]\) (when \(S\) is empty, there is no maximum, which is handled by \(j=0\).) However, a naive implementation leads to TLE (Time Limit Exceeded).

Optimization by deformation

Note that \(X[j:i] = 10X[j:i-1] + X[i:i]\) if \(j < i\) in general. For simplicity, let us define \(X[i:i-1] = 0\) so that the equation holds for \(j \leq i\). Then we realize that the result of \(dp_{i-1}\) can be reused when evaluating \(dp_i\).

When \(i \geq 2\), we have

\( \begin{aligned} dp_i &= \displaystyle\sum_{j=0}^{i-1}dp_{j}X[j+1:i] \\ &= \displaystyle\sum_{j=0}^{i-1}dp_{j} (10X[j+1: i - 1] + X[i:i]) \\ &= 10dp_{i-1} + X[i:i]\sum_{j=0}^{i-1}dp_j , \end{aligned} \)
so the cumulative sum of the DP array enables an optimization down to \(O(N)\). Note that the equation above does not hold when \(i = 1\).