题目描述

难度分:$1875$

输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 1 \times 10^{15})$。

定义$f(x)$为$x$的数位和。例如$f(123)=1+2+3=6$。

输出$\Sigma_{i=1}^{n}\Sigma_{j=1}^{n}f(a[i]+a[j])$。

输入样例$1$

2
53 28

输出样例$1$

36

输入样例$2$

1
999999999999999

输出样例$2$

135

输入样例$3$

5
123 456 789 101 112

输出样例$3$

321

算法

拆位+双指针

这个题首先要能发现一个性质：$f(x+y)=f(x)+f(y)-9 \times k(x,y)$，其中$k(x,y)$是计算$x+y$时产生的进位次数，没有这个性质的话又是坐牢。先化简一下这个公式减号前面的部分：

$\Sigma_{i=1}^{n}\Sigma_{j=1}^{n}(f(a[i])+f(a[j]))$
$=\Sigma_{j=1}^{n}\Sigma_{i=1}^{n}f(a[i])+\Sigma_{i=1}^{n}\Sigma_{j=1}^{n}f(a[j])$
$=n\Sigma_{i=1}^{n}f(a[i])+n\Sigma_{j=1}^{n}f(a[j])$
$=2n\Sigma_{i=1}^{n}f(a[i])$

上式通过$O(nlog_{10}n)$的时间复杂度就能计算出来，而进位次数$k(x,y)$通过拆位来计算，按顺序检查：

1. 有多少$a[i]+a[j]$时，个位数发生了进位？也就是看$a[i] \% 10+a[j] \% 10 \geq 10$是否成立。
   把数组按照$a[i] \% 10$排序，然后用相向双指针统计。

2. 有多少$a[i]+a[j]$时，十位数发生了进位？也就是看$a[i] \% 100+a[j] \% 100 \geq 100$是否成立。
   把数组按照$a[i] \% 100$排序，然后用相向双指针统计。

3. 依此类推，直到$100…00 \gt 2 \times max(a)$时停止。

分别检查“个、十、百、……”这些数位，检查第$k$位（$k=0$表示个位，以此类推）时，先将$a$数组按照$a[i] \% 10^{k+1}$排序。然后遍历$i \in [1,n]$，对于每个$a[i]$，利用双指针来确定最后一个不满足$a[i] \% 10+a[j] \% 10 \geq 10$的$j$，这样满足这个不等式的$j$就有$n-j$个。

复杂度分析

时间复杂度

排序+双指针的时间复杂度为$O(nlog_2n)$，由于$a[i]$最大可以达到$10^{15}$，所以需要遍历的位数最大就是$15$，是个常数，记为$A$。预处理出每个元素$a[i]$的数位和时间复杂度为$O(nlog_{10}n)$，因此算法整体的时间复杂度为$O(nlog_{10}n)+O(Anlog_2n)$。

空间复杂度

排序的额外空间复杂度为$O(log_2n)$（快速排序），而除了排序之外，仅使用了有限几个变量。因此，额外空间复杂度的痛点就在于排序，为$O(nlog_2n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 200010;
int n;
LL a[N];

// 数位和
int f(LL x) {
    int sum = 0;
    while(x) {
        sum += x%10;
        x /= 10;
    }
    return sum;
}

int main() {
    scanf("%d", &n);
    LL ans = 0, mx = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        ans += f(a[i]);
        mx = max(mx, a[i]);
    }
    ans *= 2ll*n;
    LL carry = 0;
    for(LL pow10 = 10; pow10 <= 2*mx; pow10 *= 10) {
        sort(a + 1, a + n + 1, [&](LL x, LL y) {
            return x % pow10 < y % pow10;
        });
        int j = n;
        for(int i = 1; i <= n; i++) {
            while(j && a[i]%pow10 + a[j]%pow10 >= pow10) {
                j--;
            }
            carry += n - j;
        }
    }
    ans -= 9ll*carry;
    printf("%lld\n", ans);
    return 0;
}