No.2729 Addition and Multiplication in yukicoder (Easy)
タグ : / 解いたユーザー数 156
作問者 :
AngrySadEight
/ テスター :
kusirakusira
FplusFplusF
hiro1729
🦠みどりむし
この問題は、問題 G「Addition and Multiplication in yukicoder (Hard)」と似た設定です。問題文の相違点を赤字で示します。
問題文
$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$ を $10x + A_{P_i}$ で置き換える。
このとき、最終的な $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
出力
786
$(P_1, P_2, P_3) = (3, 1, 2)$ とすればよいです。このとき、操作の過程での $x$ の値は以下のようになります。
- 最初、$x = 0$ である。$P_1 = 3$ より、 $A_{P_1} = A_3 = 1$ である。よって、$x$ を $10 \times 0 + 1 = 1$ に置き換える。
- $P_2 = 1$ より、 $A_{P_2} = A_1 = 23$ である。よって、$x$ を $10 \times 1 + 23 = 33$ に置き換える。
- $P_3 = 2$ より、 $A_{P_3} = A_2 = 456$ である。よって、$x$ を $10 \times 33 + 456 = 786$ に置き換える。
よって、最終的な $x$ の値は $786$ となり、これが実現可能な最小値です。
サンプル2
入力
9 1 22 333 4444 55555 666666 7777777 88888888 999999999
出力
993305167
$998244353$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。