• index は 0-indexed とする。
• 文字列 \(S\) の \(i\) 文字目を \(S_i\) とおき、\(i\) 文字目以降 \(j\) 文字目より前からなる部分文字列を \(S[i:j]\) とおく。例えば \(S\) が abcdef のとき、\(S_2\) は c であり、\(S[2:4]\) は cd である。
• 数字及び数字のみからなる文字列を、それを整数とみなしたときの値と同一視する。
• \(f(i)\) を \(X[0:i]\) に対する答えとする。ただし、\(f(0)=1\) と定める。求めるものは \(f(N)\) である。
  • \(f(0)=1\) と定めるのは、次の式で \(i=k\) のケースの場合分けを除くためである。

文字列の末尾から遡って初めて \(\times \) が登場する位置で場合分けすることで次の式を得る。

\(\displaystyle f(k)=\sum_{i=1}^{k}f(k-i)S[k-i:k]\\ =\sum_{i=1}^{k}f(k-i)\sum_{j=1}^{i}S_{k-j}10^{j-1}\\ =\sum_{j=1}^{k}\sum_{i=j}^{k}f(k-i)S_{k-j}10^{j-1}\\ =\sum_{j=1}^{k}S_{k-j}10^{j-1}\sum_{i=j}^{k}f(k-i)\\ =\sum_{j=1}^{k}S_{k-j}10^{j-1}\sum_{i=0}^{k-j}f(i)\\ =\sum_{j=0}^{k-1}S_{j}10^{k-j-1}\sum_{i=0}^{j}f(i)\)

ここで、\(g(j)=\sum_{i=0}^{j}f(i)\) として \(f\) の累積和 \(g\) を定めると、\(k+1>1\) のとき、

\(\displaystyle f(k+1)=\sum_{j=0}^{k}S_j10^{k-j}g(j)\\ =S_{k}g(k)+\sum_{j=0}^{k-1}S_j 10^{k-j}g(j)\\ =S_{k}g(k)+10f(k)\)

となる。したがって、以下の漸化式により、\(O(N)\) で \(f(N)\) を求めることができる。

\(f(k)=\begin{cases} 1 & k=0\\ S_0 & k=1 \\ S_{k-1}g(k-1)+10f(k-1) & k>1 \end{cases}\)

\(g(k)=\begin{cases} 1 & k=0 \\ g(k-1)+f(k) & k>0 \end{cases}\)