D - Another Sigma Problem Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

正整数 x,y に対して f(x,y) を以下で定義します。

  • 十進表記の x,y をそれぞれ文字列として解釈しこの順に連結して得られる文字列を z とする。z を十進表記の整数として解釈したときの値を f(x,y) とする。

例えば f(3,14)=314, f(100,1)=1001 です。

長さ N の正整数列 A=(A_1,\ldots,A_N) が与えられます。次の式の値を 998244353 で割ったあまりを求めてください。

\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j)


制約

  • 2\leq N\leq 2\times 10^5
  • 1\leq A_i \leq 10^9
  • 入力される数値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N 
A_1 \ldots A_N

出力

答えを出力せよ。

入力例 1

3
3 14 15

出力例 1

2044
  • f(A_1,A_2)=314
  • f(A_1,A_3)=315
  • f(A_2,A_3)=1415

なので、答えは f(A_1,A_2)+f(A_1,A_3)+f(A_2,A_3) = 2044 です。

入力例 2

5
1001 5 1000000 1000000000 100000

出力例 2

625549048

式の値を 998244353 で割ったあまりを求めることに注意してください。

Score: 400 points

Problem Statement

For positive integers x and y, define f(x, y) as follows:

  • Interpret the decimal representations of x and y as strings and concatenate them in this order to obtain a string z. The value of f(x, y) is the value of z when interpreted as a decimal integer.

For example, f(3, 14) = 314 and f(100, 1) = 1001.

You are given a sequence of positive integers A = (A_1, \ldots, A_N) of length N. Find the value of the following expression modulo 998244353:

\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^N f(A_i,A_j).


Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Print the answer.

Sample Input 1

3
3 14 15

Sample Output 1

2044
  • f(A_1, A_2) = 314
  • f(A_1, A_3) = 315
  • f(A_2, A_3) = 1415

Thus, the answer is f(A_1, A_2) + f(A_1, A_3) + f(A_2, A_3) = 2044.

Sample Input 2

5
1001 5 1000000 1000000000 100000

Sample Output 2

625549048

Be sure to calculate the value modulo 998244353.