题目描述

难度分:$844$

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

定义$f(x,y)$表示拼接$x$和$y$得到的数字，例如$f(3,14)=314$。

输出所有$f(a[i],a[j])$之和，其中$i \lt j$。答案模$998244353$。

输入样例$1$

3
3 14 15

输出样例$1$

2044

输入样例$2$

5
1001 5 1000000 1000000000 100000

输出样例$2$

625549048

算法

前后缀分解

枚举前缀的$x \in a$，即$x=a[i],i \in [1,n-1]$，这时候需要知道$[i+1,n]$上每一个数字有多长，对于一个长度为$len$的数字$a[j]$，$a[i]$与它拼起来的结果就是$a[i] \times 10^{len} + a[j]$。因此$a[i]$与后面的数字拼接之后的总和分为两个部分，第一个部分就是后缀和$\Sigma_{j \in [i+1,n]}a[j]$，第二个部分就是$\Sigma_{len}a[i] \times 10^{len}$，其中$len$就是后缀$[i+1,n]$每个数字的长度，由于$a[i] \leq 10^9$，所以$len \leq 10$，可以用一个哈希表$counter$维护后缀每个长度的数字有多少个。

复杂度分析

时间复杂度

遍历$a[i]$的时间复杂度为$O(n)$。而对于每个$a[i]$，需要遍历$counter$表，$counter$表的大小与$a$数组中每个数字的长度有关，在最差情况下长度为$1$到$10$的数字都有，时间复杂度为$O(log_{10}U)$，其中$U$是数组$a$的值域。因此，整个算法的时间复杂度为$O(nlog_{10}U)$。

空间复杂度

$counter$表在最差情况下大小为$10$，空间复杂度为$O(log_{10}U)$。除此之外还有$sz$数组，$sz[i]$表示$a[i]$的长度，空间复杂度为$O(n)$。因此瓶颈在于$sz$数组，整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010, MOD = 998244353;
const LL p[11] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000ll};
int n, a[N], sz[N];

int main() {
    scanf("%d", &n);
    unordered_map<int, int> counter;
    int tot = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        tot = (tot + a[i]) % MOD;
        int num = a[i];
        while(num > 0) {
            sz[i]++;
            num /= 10;
        }
        counter[sz[i]]++;
    }
    int ans = 0;
    for(int i = 1; i < n; i++) {
        counter[sz[i]]--;
        if(counter[sz[i]] == 0) {
            counter.erase(sz[i]);
        }
        tot = ((tot - a[i]) % MOD + MOD) % MOD;
        ans = (ans + tot) % MOD;
        for(auto&[len, cnt]: counter) {
            ans = (ans + p[len] * cnt % MOD * a[i] % MOD) % MOD;
        }
    }
    printf("%d\n", ans);
    return 0;
}