ヒント → https://atcoder.jp/contests/arc158/editorial/5901

[1] 各桁の和と繰り上がり

2 つの整数 \(a, b\) を足すとき，もし繰り上がりが起こらなければ \(f(a+b) = f(a) + f(b)\) が成り立ちます．

繰り上がりとは，ある桁の \(10\) をひとつ上の桁の \(1\) に取り換える操作なので，この操作によって各桁の和は \(9\) 減少します．したがって，\(k\) 回の繰り上がりが起こるならば \(f(a+b)=f(a)+f(b)−9k\) が成り立ちます．

したがって，本問題の答は次のように計算できます．

[a] \(\sum_{i=1}^N\sum_{j=1}^N \bigl(f(A_i) + f(A_j)\bigr)\) を計算する．
[b] すべての \((i,j)\) に対して \(A_i+A_j\) を計算したときの繰り上がり回数の総和を求める．
[c] [a] で求めた値から [b] で求めた値の \(9\) 倍を引いたものが答である．

[a] の値は \(2N\sum_{i=1}^Nf(A_i)\) に等しく，これは容易に計算できます．よって，[b] の値を計算できればよいです．

[2] 繰り上がり回数の計算

すべての \(i,j\) に対して \(A_i+A_j\) を計算するときの繰り上がりの回数を求めましょう．これは，各 \(k=0,1,\ldots\) に対して，\(10^k\) の位で起こる繰り上がりの回数を求めて足し合わせることで計算できます．

\(k\) を固定したとき，\(10^k\) の位で起こる繰り上がりの回数は次のように計算できます：

• \(A_i\) を \(10^{k+1}\) で割った余りを \(x_i\) とする．
• \(x_i + x_j \geq 10^{k+1}\) を満たす \((i,j)\) の個数を求める．

この個数の計算は，列 \((x_i)\) をソートしたあとで二分探索や尺取り法を用いれば容易に計算できます．

以上により，\(A_i\) の桁数の最大値を \(K\) とすると本問題は時間計算量 \(O(KN\log N)\) で解くことができます．

なお，基数ソートの要領で \(A_i\bmod 10^{k+1}\) のソートに \(A_i\bmod 10^k\) のソート結果を利用することで，時間計算量 \(O(NK)\) で解くこともできます．