Contest Duration: - (local time) (100 minutes) Back to Home

## F - Problem where +s Separate Digits Editorial by cai_lw

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

posted:
last update: