以下、\(\mathrm{eval}(S_{i..j})\) を \(f(i,j)\) と書きます。

次の通り記号を定めます。

• \(i\) 文字目より前で最後に + が登場する位置を \(p(i)\) とする。存在しなければ \(p(i)=0\) とする。
• \(i\) 文字目より前で最後に + または * が登場する位置を \(s(i)\) とする。存在しなければ \(s(i)=0\) とする。

例えば 1+2*34 に対しては \(p(6)=2\)、\(s(6)=4\) となります。

各 \(i\) に対して、次の 4 つの情報を持つDPで答えを求めることができます。

• \(DP_0[i]\)：\(i\) 文字目までに含まれる数字の個数
• \(DP_1[i]=\sum_{k=s(i)+1}^{i}f(k,i)\)
• \(DP_2[i]=\sum_{k=p(i)+1}^{i}f(k,i)\)
• \(DP_3[i]=\sum_{k=1}^{i}f(k,i)\)

求めるものは \(\sum_{i=1}^{|S|}DP_3[i]\) です。

イメージとしては、文字列を \(p(i),s(i)\) で区切って考える気持ちです。例えば 1+2*3*4+5*6*78 であれば 1+2*3*4, 5*6, 78 で分けることで、末尾に文字を増やしたときの \(DP_3\) の変化を考えられるようにしています。

なお、持つべき情報は以上で十分ですが、

• \(DP_1'[i]=f(s(i)+1,i)\)
• \(DP_2'[i]=f(p(i)+1,i)\)

の2つを、\(DP_1,DP_2\) とは独立して持った方がわかりやすいかもしれません。また、\(S_i\) が記号のときの \(DP_2[i]\) の値を \(0\) 以外に定めると遷移が簡単になることがあります。

実装例(Python)