题解

思路

两个整数相加时，若一共发生了 $c$ 次进位，则每次进位都会把当前位的 $10$ 换成高一位的 $1$，使数位和减少 $9$，所以 $f(x+y)=f(x)+f(y)-9c$。

做法

因此先得到不计进位时的总贡献 $2N\sum f(A_i)$，再减去所有有序数对在所有数位上产生的进位次数的 $9$ 倍即可。

对每个模数 $p=10,100,\ldots,10^{15}$，令 $B_i=A_i\bmod p$，该位发生向上进位当且仅当 $B_i+B_j\ge p$。将所有 $B_i$ 排序，对每个 $B_i$ 二分第一个不小于 $p-B_i$ 的位置，便能统计这一位产生进位的有序数对数量。

复杂度

共处理 $15$ 个模数，时间复杂度为 $O(15N\log N)$，空间复杂度为 $O(N)$。