求める値は \(S_i\) に着目すれば次のようになります．ただし添字は 0-indexed で，\(R_i\) は \(1\) を \(i\) 個並べた整数です：

\[ \sum_{i=0}^{N-1}(i+1)\times S_i\times R_{N-i} \]

多倍長整数を用いて計算したいところですが，素直に一つずつ計算していくと良く見積もっても \(\Omega(N^2)\) なので高速化を頑張らない限りは間に合わないかと思います．

ここで分割統治することを考えます．

\(S[l,m)\) に対する結果と \(S[m,r)\) に対する結果をマージして \(S[l,r)\) に対する結果を得ることを考えると，次の値を求めればよいです．

• \(S[l,r)\) での答え
• \(\sum_{i=l}^{r-1}(i+1)S_i\)
• \(10^{r-l}\)
• \(R_{r-l}\)

全体の計算量は，乗算が Karatsuba 法（ \(n\) 桁の乗算が \(O(n^{\log_2 3})\) ）の場合 \(O(N^{\log_2 3})\) になります．

実装例(PyPy, 195ms)：https://atcoder.jp/contests/abc379/submissions/59631812