No.020 C

$A$ を数式で表すと,

$$A = \sum_{i=1}^N \left( \sum_{j=0}^{L-1} a_i \cdot 10^{jc_i+b_i} \right)$$

となる. ただし, $c_i$ は $a_i$ の桁数, $b_i = c_{i+1}L_{i+1} + c_{i+2}L_{i+2} + \dots c_NL_N$, である. ($b_i$ は後ろからの累積和を計算しておく)

カッコ内を変形すると,

$$a_i \cdot 10^{b_i} \sum_{j=0}^{L-1} 10^{jc_i}$$

となる.

$10^{b_i}$ は繰り返し二乗法を使えばいい.

和の部分は $L$ が偶数ならば

$$\sum_{j=0}^{L-1} 10^{jc_i} = (1 + 10^{(L/2)c_i}) \cdot \sum_{j=0}^{L/2-1} 10^{jc_i}$$

となるので, これを再帰的に適用すれば $O(\log^2 L)$ で計算できる. $L$ が奇数の場合は余りの項だけ別途足せばいい.