Let’s first consider evaluating a given \(T\) in a fashion similar to dynamic programming (DP).

When only considering \(T\)’s first \(i\) digits and all “+” signs among them as a formula, let \(s_i\) be the sum of all terms except for the rightmost one , and \(x_i\) be the rightmost term. Initially, \(s_1=0,x_1=d_1\). Finally, \(s_N+x_N\) is the answer.

There are two cases when appending the \((i+1)\)-th digits \(d_{i+1}\) to the formula:

• There is a “+” sign before \(d_{i+1}\): \(s_{i+1}=s_i+a_i, x_{i+1}=d_{i+1}\)
• There is no “+” sign before \(d_{i+1}\): \(s_{i+1}=s_i,x_{i+1}=10x_i+d_{i+1}\)

Since both of them are linear functions of \(s_i\) and \(x_i\), they can be expressed in matrices and vectors. Let \(v_i=\begin{bmatrix} s_i & x_i & 1\end{bmatrix}^T\):

• There is a “+” sign before \(d_{i+1}\): \(v_{i+1}=A_{i+1}v_i\) where

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

• There is no “+” sign before \(d_{i+1}\): \(v_{i+1}=B_{i+1}v_i\) where

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

Thus, the sum of \(s_N+x_N\) for all \(2^{N-1}\) possible formulae is:

\[ \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} \]

which can be easily computed in \(O(N)\) by following the definition of matrix operations.

Sample implementation (C++): https://atcoder.jp/contests/abc224/submissions/26789924