No.2734 Addition and Multiplication in yukicoder (Hard)
タグ : / 解いたユーザー数 69
作問者 :
AngrySadEight
/ テスター :
kusirakusira
FplusFplusF
hiro1729
🦠みどりむし
この問題は、問題 B「Addition and Multiplication in yukicoder (Easy)」と似た設定です。問題文の相違点を赤字で示します。
問題文
$N$ 個の整数 $A_1, A_2, \dots, A_N$ があります。また、変数 $x$ があり、最初 $x = 0$ です。
あなたは、次に示す操作を $1$ 回行います。
- まず、$(1, 2, \dots, N)$ の順列 $(P_1, P_2, \dots, P_N)$ をひとつ選ぶ。
- 次に、$i = 1, 2, \dots, N$ の順に、$x$ を $10^{d(A_{P_i})} \times x + A_{P_i}$ で置き換える。ただし、$d(y)$ で $y$ の $10$ 進表記における桁数を表す。
このとき、最終的な $x$ の値として考えられる最小値を $998244353$ で割った余りを求めてください。なお、$x$ の値を $998244353$ で割った余りの最小値を求めるのではないことに注意してください。
制約
- 入力はすべて整数である。
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^{18}$
入力
入力は以下の形式で標準入力から与えられる。
$N$ $A_1$ $A_2$ $\dots$ $A_N$
出力
最終的な $x$ の値として考えられる最小値を $998244353$ で割った余りを出力せよ。
サンプル
サンプル1
入力
3 23 456 1
出力
123456
$(P_1, P_2, P_3) = (3, 1, 2)$ とすればよいです。このとき、操作の過程での $x$ の値は以下のようになります。
- 最初、$x = 0$ である。$P_1 = 3$ より、 $A_{P_1} = A_3 = 1$ である。$d(1) = 1$ より、$x$ を $10^1 \times 0 + 1 = 1$ に置き換える。
- $P_2 = 1$ より、 $A_{P_2} = A_1 = 23$ である。$d(23) = 2$ より、$x$ を $10^2 \times 1 + 23 = 123$ に置き換える。
- $P_3 = 2$ より、 $A_{P_3} = A_2 = 456$ である。$d(456) = 3$ より、$x$ を $10^3 \times 123 + 456 = 123456$ に置き換える。
よって、最終的な $x$ の値は $123456$ となり、これが実現可能な最小値です。
サンプル2
入力
5 31 41 5 9 2
出力
2314159
サンプル3
入力
9 1 22 333 4444 55555 666666 7777777 88888888 999999999
出力
808067813
$998244353$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。