No.2734 Addition and Multiplication in yukicoder (Hard)
タグ : / 解いたユーザー数 73
作問者 : 👑
kusirakusira
FplusFplusF
みどりむし🦠
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もしくは右上の雲マークをクリックしてアカウントを作成してください。