\(0 \le i \le N\) に対し、文字列 \(X\) を長さ \(i\) の suffix \(s(i) := X[N - i: N]\) に置き換えたときの答えを \(\mathtt{dp}(i)\) と置くと

\[ \begin{aligned} \mathtt{dp}(0) &= 1 \\ \mathtt{dp}(i) &= \sum _ { 0 \le j \lt i } \mathtt{dp(j)} X[N - i: N - j] \ (0 \lt i \lt N) \end{aligned} \]

が成り立ちます。（先頭のチャンクの長さを \(i - j\) と置いて導出しました。）

さらに \(0 \lt i \lt N\) に対する \(\mathtt{dp}(i) \) は、次のように簡単になります。

\[ \begin{aligned} \mathtt{dp}(i) &= \sum _ { 0 \le j \lt i } \mathtt{dp(j)} \frac { s(i) - s(j) } { 10 ^ j } \\ &= s(i) \sum _ { 0 \le j \lt i } \mathtt{dp(j)} 10 ^ { -j } - \sum _ { 0 \le j \lt i } \mathtt{dp(j)} s(j) 10 ^ { -j } \end{aligned} \]

従って、\(\mathtt{dp}(i)\) と一緒に次のものも計算することで、\(O(N)\) 時間になります。

• \(10 ^ { -i }\)
• \(s(i)\)
• \(\sum _ { 0 \le j \lt i } \mathtt{dp(j)} 10 ^ { -j } \)
• \(\sum _ { 0 \le j \lt i } \mathtt{dp(j)} s(j) 10 ^ { -j } \)