問題一覧 > 通常問題

No.2734 Addition and Multiplication in yukicoder (Hard)

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 73
作問者 : 👑 AngrySadEight / テスター : kusirakusira FplusFplusF hiro1729 みどりむし🦠
お気に入りにしたユーザー ProblemId : 10762 / 自分の提出
問題文最終更新日: 2024-04-14 20:12:28
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 428 (順位表) の他の問題:

This problem has a setting similar to Problem B "Addition and Multiplication in yukicoder (Easy)". The differences in the problem statement are shown in red.

Problem Statement

There are $N$ integers $A_1, A_2, \dots, A_N$. There is also a variable $x$, which is initially $x = 0$.

You perform the following operation $1$ time.

  • First, choose a permutation $(P_1, P_2, \dots, P_N)$ of $(1, 2, \dots, N)$.
  • Then, in the order $i = 1, 2, \dots, N$, replace $x$ with $10^{d(A_{P_i})} \times x + A_{P_i}$. Here, $d(y)$ denotes the number of digits of $y$ in base $10$ notation.

Find the minimum possible final value of $x$, modulo $998244353$. Note that you are not asked to find the minimum of the value of $x$ modulo $998244353$.

Constraints

  • All inputs are integers.
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^{18}$

Input

The input is given from standard input in the following format.

$N$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the minimum possible final value of $x$, modulo $998244353$.

Sample

Sample 1
Input
3
23 456 1
Output
123456

You can choose $(P_1, P_2, P_3) = (3, 1, 2)$. In this case, the value of $x$ during the operation changes as follows.

  • Initially, $x = 0$. Since $P_1 = 3$, we have $A_{P_1} = A_3 = 1$. Since $d(1) = 1$, replace $x$ with $10^1 \times 0 + 1 = 1$.
  • Since $P_2 = 1$, we have $A_{P_2} = A_1 = 23$. Since $d(23) = 2$, replace $x$ with $10^2 \times 1 + 23 = 123$.
  • Since $P_3 = 2$, we have $A_{P_3} = A_2 = 456$. Since $d(456) = 3$, replace $x$ with $10^3 \times 123 + 456 = 123456$.

Thus, the final value of $x$ is $123456$, which is the minimum achievable value.

Sample 2
Input
5
31 41 5 9 2
Output
2314159
Sample 3
Input
9
1 22 333 4444 55555 666666 7777777 88888888 999999999
Output
808067813

Print the value modulo $998244353$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。