也许是一个简单一点的做法？
假如我们要求一个表达式的值，我们求的顺序显然是，按照加号划分为若干段，段内只有数字和乘号，计算出段内结果后全部加起来。
称一个只有数字和乘号的表达式是基本表达式，我们将每个表达式的贡献拆分为若干个基本表达式之和，那么我们就可以枚举每个基本表达式，算它在多少个表达式里出现过，它在最终答案里的贡献也就算出来了。
假设我们现在要计算基本表达式 \([i,j]\) 的贡献，\([i,j]\) 的意思是题目给出的原串的的 \([i,j]\) 这一段子串。
首先考虑如何计算它在多少个表达式里出现过，注意到若 \(i\) 左侧不是加号，那么左侧的选择已经唯一了，否则就是 \([1,i]\) 中数字的个数，另一侧同理。
接下来考虑如何计算它的值，假设我们有一个二元组 \((Q,Q*x)\) ，\(Q\) 表示上一个乘号之前的积， \(Q*x\) 表示当前表达式的值，\(x\) 是当前的数字，那么我们从左往右扫描该基本表达式。
碰到数字 \(d\) ，那么 \((Q,Q*x)->(Q,Q*(10x+d))->(Q,10*Q*x+d*Q)\)，碰到乘号，那么 \((Q,Q*x)->(Q*x,0)\) ，然后你发现这两个变换都可以写成矩阵乘法的形式。
所以 \(Ans=\sum\limits_{i,j} lways(i)*rways(j)*(\prod\limits_{k=i}^jmat[k])_{0,1}\)
\(lways\) 表示可选左端点个数， \(rways\) 同理，这个上面已经分析过了， \(mat\) 是矩阵， \(0,1\) 是矩阵积的 \(0\) 行 \(1\) 列的值，原因是二元组初始为 \((1,0)\) 手动矩阵乘法即可得。
那么我们从左往右扫描 \(j\) ，\(j\) 已知，假设我们已经维护出 \(\sum\limits_{i} lways(i)*\prod\limits_{k=i}^j mat[k]\) ，那么对答案的贡献好算，提取对应位置后乘上 \(rways(j)\) 即可，怎么 \(j->j+1\) 呢，你发现只要右乘 \(mat[j+1]\) 之后加上 \(lways(j+1)*mat[j+1]\) 即可。
进一步的，你发现矩阵只需要保留第 \(0\) 行的两个位置就好了，含义就是，所有以 \(j\) 为右端点的基本表达式的 \(Q*lways(i)\) 之和， \(Q*x*lways(i)\) 之和。
碰到加号的时候 \((Q,Q*x)->(0,0)\) ，原因是基本表达式不含加号。
代码：Submission #50104472 - AtCoder Beginner Contest 338
代码很短，很好写，要维护的东西很少，很简洁。
标签：lways,limits,题解,矩阵,ABC338G,加号,表达式,mat From： https://www.cnblogs.com/llzer/p/18012303