Hints → https://atcoder.jp/contests/arc158/editorial/5987

[1] The sum of digits and carries

When adding two integers \(a\) and \(b\), if there are no carries, we have \(f(a+b) = f(a) + f(b)\).

A carry trades \(10\) at some position for \(1\) at one higher position, so it decreases the sum of digits by \(9\). Thus, if there are \(k\) carries, \(f(a+b)=f(a)+f(b)−9k\).

Therefore, the answer can be computed as follows.

[a] Compute \(\sum_{i=1}^N\sum_{j=1}^N \bigl(f(A_i) + f(A_j)\bigr)\).
[b] Find the total number of carries when \(A_i+A_j\) is computed for every \((i,j)\).
[c] The answer is the sum in [a] minus the number in [b] multiplied by \(9\).

The sum in [a] equals \(2N\sum_{i=1}^Nf(A_i)\), which can be computed easily. Thus, we only have to compute the number in [b].

[2] Find the total number of carries

Let us find the total number of carries when \(A_i+A_j\) is computed for every \((i,j)\). This can be done by, for each \(k=0,1,\ldots\), finding the number of carries at the \(k\)-th lowest digit and summing them up.

For a fixed \(k\), the number of carries at the \(k\)-th lowest digit can be computed as follows.

• Let \(x_i\) be the remainder when \(A_i\) is divided by \(10^{k+1}\).
• Find the number of \((i,j)\) that satisfy \(x_i + x_j \geq 10^{k+1}\).

This number can be computed easily by sorting the sequence \((x_i)\) and then using binary search or two pointers.

Therefore, the problem can be computed in a time complexity of \(O(KN\log N)\) where \(K\) is the maximum number of digits in \(A_i\).

One can also solve it in a time complexity of \(O(KN)\) by using the result of sorting \(A_i\bmod 10^k\) in sorting \(A_i\bmod 10^{k+1}\) as in radix sort.