\(\displaystyle\sum _ {1\leq i\lt j\leq N}f(A _ i,A _ j)\) を、\(j\) を固定して考えることによって整理します。

公式解説の \(\operatorname{len}(y)\coloneqq y\) を十進法で表したときの長さ と、これによる \(f\) の表式 \(f(x,y)=y+x\times10 ^ {\operatorname{len}(y)}\) を利用します。

\[\begin{aligned} &\sum _ {1\leq i\lt j\leq N}f(A _ i,A _ j)\\ =&\sum _ {1\leq j\leq N}\sum _ {1\leq i\lt j}f(A _ i,A _ j)\\ =&\sum _ {1\leq j\leq N}\sum _ {1\leq i\lt j}(A _ j+A _ i\times10 ^ {\operatorname{len}(A _ j)})\\ =&\sum _ {1\leq j\leq N}\left((j-1)A _ j+10 ^ {\operatorname{len}(A _ j)}\sum _ {1\leq i\lt j}A _ i\right) \end{aligned}\]

つまり、\(j\ (1\leq j\leq N)\) について、\(f(A _ i,A _ j)\ (1\leq i\lt j)\) の総和は

• \(A _ j\) を \(j-1\) 個加えたもの（\(f(A _ i,A _ j)\) の下 \(\operatorname{len}(A _ j)\) 桁の部分の総和）
• \(\displaystyle\sum _ {1\leq i\lt j}A _ i\) を \(10 ^ {\operatorname{len}(A _ j)}\) 倍したもの（\(f(A _ i,A _ j)\) の \(\operatorname{len}(A _ j)\) 桁より上の部分の総和）

の和として計算できます。

ここから、以下のようなアルゴリズムを考えることができます。

• はじめ、\(S=0,\operatorname{ans}=0\) とする。
• \(i=1,2,\ldots,N\) に対して、以下を行う。
  • \(\operatorname{ans}\) に \((i-1)A _ i\) を加算する。
  • \(\operatorname{len}(A _ i)\) を求め、\(\operatorname{ans}\) に \(10 ^ {\operatorname{len}(A _ i)}S\) を加算する。
  • \(S\) に \(A _ i\) を加算する。

繰り返しが終了したあとの \(\operatorname{ans}\) の値が求める答えになります。

時間計算量は、\(\operatorname{len}(A _ i)\) や \(10 ^ {\operatorname{len}(A _ i)}\) を求めるところで \(\displaystyle O(\log\log A _ i)\) などの時間がかかるので、全体で \(O(N\log\log\max _ i A _ i)\) などになります（公式解説とは \(\operatorname{len}(A _ i)\) を求める方法が違うだけで、どちらも同じ時間計算量のオーダーで実装ができます）。

\(A\) の値が定数ワードに収まるという前提のもと、実装例の方針では空間計算量は \(O(\log\log\max _ iA _ i)\) ワードになります。整数をうまく詰めたり \(\operatorname{len}(A _ i)\) を求める時間計算量の悪化を許すことで、全体で \(O(1)\) ワードにすることもできます。

実装例は以下のようになります。

#include <iostream>
#include <array>
#include <ranges>
#include <atcoder/modint>

int main() {
    using namespace std;
    using modint = atcoder::static_modint<998244353>;
    unsigned N;
    cin >> N;
    modint ans{}, prefix_sum{};
    for (unsigned i{}, A; i < N; ++i) {
        cin >> A;
        // 10^k <= A であるような最大の 10^k を求める
        unsigned pow_ten_floor{1};
        for (const auto pow_ten : array<unsigned, 4>{10, 100, 10000, 100000000} | views::reverse)
            if (A / pow_ten >= pow_ten_floor)
                pow_ten_floor *= pow_ten;
        
        // 答えに A[i] * i + 10^(k+1)S を足す
        ans += modint::raw(A) * i + prefix_sum * pow_ten_floor * 10;
        
        // S に A[i] を足す
        prefix_sum += A;
    }
    cout << ans.val() << endl;
    return 0;
}