問題一覧 > 通常問題

No.2729 Addition and Multiplication in yukicoder (Easy)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 178
作問者 : 👑 AngrySadEight / テスター : kusirakusira FplusFplusF hiro1729 🦠みどりむし
0 ProblemId : 10761 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-04-13 00:46:18

この問題は、問題 G「Addition and Multiplication in yukicoder (Hard)」と似た設定です。問題文の相違点を赤字で示します。

問題文

NN 個の整数 A1,A2,…,ANA_1, A_2, \dots, A_N があります。また、変数 xx があり、最初 x=0x = 0 です。

あなたは、次に示す操作を 11 回行います。

  • まず、(1,2,…,N)(1, 2, \dots, N) の順列 (P1,P2,…,PN)(P_1, P_2, \dots, P_N) をひとつ選ぶ。
  • 次に、i=1,2,…,Ni = 1, 2, \dots, N の順に、xx を 10x+APi10x + A_{P_i} で置き換える。

このとき、最終的な xx の値として考えられる最小値を 998244353998244353 で割った余りを求めてください。なお、xx の値を 998244353998244353 で割った余りの最小値を求めるのではないことに注意してください。

制約

  • 入力はすべて整数である。
  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤Ai≤10181 \leq A_i \leq 10^{18}

入力

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

NN
A1A_1 A2A_2 …\dots ANA_N

出力

最終的な xx の値として考えられる最小値を 998244353998244353 で割った余りを出力せよ。

サンプル

サンプル1
入力
3
23 456 1
出力
786

(P1,P2,P3)=(3,1,2)(P_1, P_2, P_3) = (3, 1, 2) とすればよいです。このとき、操作の過程での xx の値は以下のようになります。

  • 最初、x=0x = 0 である。P1=3P_1 = 3 より、 AP1=A3=1A_{P_1} = A_3 = 1 である。よって、xx を 10×0+1=110 \times 0 + 1 = 1 に置き換える。
  • P2=1P_2 = 1 より、 AP2=A1=23A_{P_2} = A_1 = 23 である。よって、xx を 10×1+23=3310 \times 1 + 23 = 33 に置き換える。
  • P3=2P_3 = 2 より、 AP3=A2=456A_{P_3} = A_2 = 456 である。よって、xx を 10×33+456=78610 \times 33 + 456 = 786 に置き換える。

よって、最終的な xx の値は 786786 となり、これが実現可能な最小値です。

サンプル2
入力
9
1 22 333 4444 55555 666666 7777777 88888888 999999999
出力
993305167

998244353998244353 で割った余りを出力してください。

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