题目描述

难度分:$1908$

输入$n(2 \leq n \leq 10^6)$和长为$n$的数组$a(0 \leq a[i] \lt 10^6)$。

输出满足【十进制加法$a[i]+a[j]$的每个数位都没有产生进位】的下标对$(i,j)$个数，其中$i \lt j$。

输入样例$1$

4
4 8 12 90

输出样例$1$

3

输入样例$2$

20
313923 246114 271842 371982 284858 10674 532090 593483 185123 364245 665161 241644 604914 645577 410849 387586 732231 952593 249651 36908

输出样例$2$

6

输入样例$3$

5
1 1 1 1 1

输出样例$3$

10

算法

高维前缀和

假设有一个数$123456$，能和它相加不进位的数必须满足对应的$6$个数位与它相加都不超过$9$，即个位$\leq 3$，十位$\leq 4$，百位$\leq 5$，千位$\leq 6$，万位$\leq 7$，十万位$\leq 8$。

因此我们可以预处理出一个数组$cnt$，$cnt[123456]$就表示$a$数组中同时满足以上$6$个条件的数的个数。初始化$cnt[a[i]]$为数值$a[i]$在数组中出现的次数，然后枚举$6$个数位，逐位处理每个数位。如果$j$从低往高第$i$位（$i$从$0$开始取值）是非零，就把$cnt[j-10^i]$累加到$cnt[j]$上，即第$i$位上减去了一个$1$做前缀和，本质上$cnt$是个$6$维前缀和。

因此，能与$a[i]$相加不进位的数的个数就是$cnt[999999-a[i]]$，但需要去除$a[i]$自己与自己相加会进位的情况。最后，由于这样计算会导致$(a[i],a[j])$与$(a[j],a[i])$算作两个数对，因此答案还要除以$2$。

复杂度分析

时间复杂度

初始化前缀和遍历了$6$遍数组处理每一位，时间复杂度为$O(n)$，计算$6$维前缀和也一样。最后遍历一遍数组$a$计算每个$a[i]$的答案，时间复杂度$O(n)$，因此算法整体的时间复杂度也是$O(n)$。

空间复杂度

额外空间主要消耗在前缀和数组$cnt$上，它的规模仅与$a[i]$的范围有关，最坏情况下与$n$的上限$10^6$是同一规模的，因此额外空间复杂度为$O(n)$。

C++ 代码

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

using namespace std;
typedef long long LL;

const int N = 1000010;
int n, a[N], pw[7];
LL cnt[N];

int main() {
    scanf("%d", &n);
    pw[0] = 1;
    for(int i = 1; i <= 6; i++) {
        pw[i] = pw[i - 1]*10;
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        cnt[a[i]]++;
        int c = 1;
        for(int j = 0; j < 6; j++) {
            int d = a[i]/pw[j]%10;
            if(d > 4) c = 0;
        }
        if(c) ans--;      // 自己加自己不会进位
    }
    // 6维前缀和
    for(int i = 0; i < 6; i++) {
        for(int j = 0; j < pw[6]; j++) {
            if(j/pw[i]%10) {
                // j从低到高的第i位不为0
                cnt[j] += cnt[j - pw[i]];
            }
        }
    }
    for(int i = 1; i <= n; i++) {
        ans += cnt[999999 - a[i]];
    }
    printf("%lld\n", ans>>1);
    return 0;
}