（英語解説にも参照してください。https://atcoder.jp/contests/abc224/editorial/2829 ）

まず、式\(T\)が与えられたとき\(T\)を評価するアルゴリズムを考えます。

\(T\)の先頭から\(i\)個の数字とその間の「+」からなる式に対して、一番右にある項以外のすべての項の和を\(s_i\)とし、一番右にある項を\(x_i\)とします。はじめ、\(s_1=0,x_1=d_1\)とします。式\(T\)の値は、\(s_N+x_N\)です。

\((i+1)\)番目の数字\(d_{i+1}\)をその式に追加するとき、二つのケースがあり得ます。

• \(d_{i+1}\)の前に「+」がある：\(s_{i+1}=s_i+a_i, x_{i+1}=d_{i+1}\)
• \(d_{i+1}\)の前に「+」がない：\(s_{i+1}=s_i,x_{i+1}=10x_i+d_{i+1}\)

どちらも\(s_i\)と\(x_i\)に関する線形関数なので、行列とベクトルで表されます。\(v_i=\begin{bmatrix} s_i & x_i & 1\end{bmatrix}^T\)とすれば

• \(d_{i+1}\)の前に「+」がある：\(v_{i+1}=A_{i+1}v_i\)、ただし

\[ A_{i+1}= \begin{bmatrix} 1 & 1 & 0 \\ 0 & 0 & d_{i+1} \\ 0 & 0 & 1 \end{bmatrix} \]

• \(d_{i+1}\)の前に「+」がない：\(v_{i+1}=B_{i+1}v_i\)、ただし

\[ B_{i+1}= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 10 & d_{i+1} \\ 0 & 0 & 1 \end{bmatrix} \]

よって、\(2^{N-1}\)通りのすべての式に対する\(s_N+x_N\)の和は、こうして表せます。

\[ \begin{bmatrix} 1 & 1 & 0 \end{bmatrix} (A_N+B_N)(A_{N-1}+B_{N-1})\dots(A_2+B_2) \begin{bmatrix} 0 \\ d_1 \\ 1 \end{bmatrix} \]

これは行列演算の定義に従って\(O(N)\)で計算できます。

実装例(C++): https://atcoder.jp/contests/abc224/submissions/26789924