ABC224 F - Problem where +s Separate Digits (500)
最初の考察
部分文字列毎に考える
全体長を$ N、部分文字列長を$ Mとするとその部分文字列長は$ 2^{\max(n-m-1,0)}回登場する
部分文字列毎には$ \mathcal{O}(N^2)個あるのでそれぞれについて計算すると間に合わない
最終的な考察
各文字毎にどの位で何度使われるかについて考える
考察すると1の位では$ 2^{n-2}、10の位では$ 2^{n-3}、$ 10^kの位では$ 2^{n-k-1}回使われることが分かる
ただし、$ i番目の文字について$ 10^{n-i}の位以降で使われる回数は代わりに$ 10^{n-i-1}に加算される
使われ方を文字毎に計算すると計算量が落ちない
各位毎にまとめて計算すると$ 10^kの位では$ \left(\sum_{i=0}^{n-k-1} a_i + a_k \right) \times 10^{k} \times 2^{n-k-1}
最大でも$ 10^{n-1}桁なので$ \mathcal{O}(N)で解ける