我们重新理解一下 $f(x,y)$

有用的形式： $f(x,y) = 10^{\mathrm{len}(y)} x + y$ ，其中 $\mathrm{len}(y)$ 是解释为字符串的 $y$ 的长度。对于每个 $i$ ，让我们以 $f(*,A_i)$ 和 $f(A_i, *)$ 的形式找出 $A_i$ 的贡献。

前者很简单 $f(*,A_i)$ 本身就有项 $A_i$ ，所以对答案的贡献是 $(i-1)A_i$ 。

我们考虑后者。

贡献是 $\sum_{k=1}^{10} d_k 10^{k} A_i$ ，其中 $d_k$ 是 $i \lt j$ 并且 $\mathrm{len}(A_j) = k$ 的 $j$ 的数目，对于每个 $i$ ，可以在固定时间内更新 $d_k$

因此可以在 $\mathrm{O}(\log M)$ 中为每个 $i$ 计算后者的贡献，其中 $M$ 是 $A$ 中的最大值。因此，在总共 $\mathrm{O}(N\log M)$ 的时间内找到了答案。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MOD 998244353  // 定义模数

int main() {
    int n;
    cin >> n;
    vector<ll> A(n);      // 存储输入数字
    vector<ll> d(11, 0);  // d[k]: 记录当前剩余数字中长度为k的数量

    // 预处理数字长度并统计初始长度分布
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        d[to_string(A[i]).size()]++;  // 将数字转为字符串获取长度
    }

    // 预处理10的幂次模MOD的结果 (10^0, 10^1, ..., 10^10)
    vector<ll> p10(11, 1);
    for (int i = 1; i <= 10; i++) {
        p10[i] = (p10[i-1] * 10) % MOD;  // 递推计算10的幂次
    }

    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ll ai = A[i] % MOD;  // 当前数字取模后的值

        // 贡献1：A[i]作为y时的总贡献（对应公式中的 f(*, A[i]) 部分）
        // 当前元素前有i个元素，每个与它组合的形式为 f(A_j, A_i) = 10^{len(A_i)}*A_j + A_i
        // 其中A_i作为y的总贡献为 (i个元素) * A_i
        ans = (ans + ai * i % MOD) % MOD;  // 累加贡献到答案

        // 移除当前数字的长度统计（后续元素j必须满足i<j）
        int len = to_string(A[i]).size();
        d[len]--;

        // 贡献2：A[i]作为x时的总贡献（对应公式中的 f(A_i, *) 部分）
        // 对每个可能的长度k，贡献为 (剩余长度为k的数字数量) * A_i * 10^k
        for (int j = 1; j <= 10; j++) {  // 遍历所有可能的长度
            // 公式分解：d[j]（剩余长度j的数量） * p10[j]（10^j） * ai（A[i]）
            ans = (ans + ai * d[j] % MOD * p10[j] % MOD) % MOD; 
        }
    }

    cout << ans << endl;
    return 0;
}