簡単のため、\(X\) を長さ \(N\) の文字列とみなし、\(L\) 文字目から \(R\) 文字目までからなる部分文字列を \(10\) 進表記された整数とみなしたものを \(X[L:R]\) と表記することにします。

動的計画法の利用

\(dp_i\) を \(N\) を \(i\)、\(X\) を \(X[1:i]\) に置き換えたときの本問題の答えとします。ただし、本問題の制約から外れる範囲においても \(dp_0 = 1, dp_1 = X[1:1]\) として DP 配列を定義することに注意してください。

ここで、\(j \in S\) なる最大の \(j\) について場合分けすることで \(i \geq 1\) について \(dp_i = \displaystyle\sum_{j=0}^{i-1}dp_{j} X[j+1:i]\) が成り立つことがわかります（\(S\) が空集合のときは最大値が存在しませんが、\(j=0\) に対応します）。しかし、これをそのまま実装すると TLE してしまいます。

式の形を利用した高速化

一般に、\(j < i\) ならば \(X[j:i] = 10X[j:i-1] + X[i:i]\) が成り立つことに注意します。簡単のため \(X[i:i-1] = 0\) と定めることによって上の式が \(j \leq i\) で成り立つようにします。すると、\(dp_i\) を計算するときに \(dp_{i-1}\) の計算結果が使えることがわかります。

\(i \geq 2\) のとき、

\( \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} \)
であるため、DP 配列の累積和を持っておくことで DP を \(O(N)\) に高速化できました。上の式は \(i = 1\) では成り立たないことに注意してください。