K - Shuffle and Max Bracket Score Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : {100} 点

問題文

あおばさんは次の問題を思いつきました。

Max Bracket Score
長さ 2N の整数列 A=(A_1,A_2,\ldots,A_{2N}) が与えられます。長さ 2N の正しい括弧列 s に対して、 s のスコアを次のように定めます。

  • s_i が ( であるようなすべての i に対する A_i の総和

長さ 2N の正しい括弧列のスコアとしてあり得る最大の値を求めてください。

この問題はひろせさんにとって簡単だったので、以下のように改題しました。

Shuffle and Max Bracket Score
長さ 2N の整数列 A=(A_1,A_2,\ldots,A_{2N}) が与えられます。 A を一様ランダムにシャッフルした後の Max Bracket Score の答えの期待値を \mathrm{mod}\ 998244353 で求めてください。

Shuffle and Max Bracket Score を解いてください。

正しい括弧列とは 以下のいずれかの条件を満たす文字列を正しい括弧列と定義します。
  • 空文字列
  • ある正しい括弧列 S が存在して、(, S, ) をこの順に連結した文字列
  • ある空でない正しい括弧列 S, T が存在して、 S,T をこの順に連結した文字列

期待値 \text{mod} \ 998244353 とは 求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表したとき、Q \not \equiv 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この R を答えてください。

制約

  • 1\leq N \leq 10^5
  • 1\leq A_i\leq 10^9
  • 入力は全て整数

部分点

  • 追加の制約 N\leq 100 を満たすデータセットに正解した場合は 10 点が与えられる。

入力

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

N
A_1 A_2 \ldots A_{2N}

出力

求める期待値を \mathrm{mod}\ 998244353 で出力せよ。

入力例 1

1
1 2

出力例 1

499122178

A=(1,2) のとき Max Bracket Score の答えは 1 です。

  • s が () のときのスコアは 1 です。

A=(2,1) のとき Max Bracket Score の答えは 2 です。

  • s が () のときのスコアは 2 です。

求める期待値は \dfrac{1}{2}(1+2)=\dfrac{3}{2} です。

入力例 2

2
1 2 3 4

出力例 2

831870300

例えば A=(1,2,3,4) のとき Max Bracket Score の答えは 4 です。

  • s が ()() のときのスコアは 1+3=4 です。
  • s が (()) のときのスコアは 1+2=3 です。

また、 A=(4,3,2,1) のとき Max Bracket Score の答えは 7 です。

  • s が ()() のときのスコアは 4+2=6 です。
  • s が (()) のときのスコアは 4+3=7 です。

求める期待値は \dfrac{35}{6} です。

入力例 3

4
31415 92653 58979 32384 62643 38327 95028 84197

出力例 3

420993474