#P18329. Shuffle and Max Bracket Score

Shuffle and Max Bracket Score

Shuffle and Max Bracket Score

Aoba 提出了下面的问题。

Max Bracket Score

给定一个长度为 2N2N 的整数序列 A=(A1,A2,…,A2N)A=(A_1,A_2,\ldots,A_{2N})。对于一个长度为 2N2N 的合法括号序列 ss,它的得分定义为:

  • 将所有满足 sis_i 为左括号 ( 的位置 ii 所对应的 AiA_i 相加。

求所有合法括号序列中,能够获得的最大得分。

Hirose 认为这个问题太简单,于是提出了下面的问题。

Shuffle and Max Bracket Score

给定一个长度为 2N2N 的整数序列 A=(A1,A2,…,A2N)A=(A_1,A_2,\ldots,A_{2N})。将 AA 均匀随机地打乱后,计算 Max Bracket Score 问题答案的期望值,对 998244353998244353 取模。

请解决 Shuffle and Max Bracket Score。

合法括号序列的定义

一个字符串是合法括号序列,当且仅当它符合下列条件之一:

  • 它是空字符串;
  • 它可以写成 (、某个合法括号序列 ss、) 依次连接得到的字符串;
  • 它可以写成两个合法括号序列 s,ts,t 连接得到的字符串。

期望值取模的定义

所求期望是一个有理数。题目保证,在本题的数据范围内,将该期望化为最简分数 yx\dfrac{y}{x} 后,分母 xx 不被 998244353998244353 整除。

此时存在唯一整数 zz,满足 0≤z<9982443530\le z<998244353 且

y≡xz(mod998244353).y\equiv xz\pmod{998244353}.

请输出这个 zz。

输入格式

输入只有一组数据,格式如下:

N
A_1 A_2 ... A_{2N}

输出格式

输出一行一个整数,表示所求期望对 998244353998244353 取模的结果。

数据范围

  • 1≤N≤1051\le N\le10^5;
  • 1≤Ai≤1091\le A_i\le10^9;
  • 所有输入值均为整数。

样例输入 1

1
1 2

样例输出 1

499122178

样例输入 2

2
1 2 3 4

样例输出 2

831870300

样例输入 3

4
31415 92653 58979 32384 62643 38327 95028 84197

样例输出 3

420993474

样例说明

第一组中:

  • 当 A=(1,2)A=(1,2) 时,唯一的合法括号序列为 (),最大得分是 11;
  • 当 A=(2,1)A=(2,1) 时,最大得分是 22。

因此期望为 1+22=32\dfrac{1+2}{2}=\dfrac32。

第二组中:

  • 例如 A=(1,2,3,4)A=(1,2,3,4) 时,()() 的得分为 1+3=41+3=4,(()) 的得分为 1+2=31+2=3,最大得分为 44;
  • 例如 A=(4,3,2,1)A=(4,3,2,1) 时,()() 的得分为 4+2=64+2=6,(()) 的得分为 4+3=74+3=7,最大得分为 77。

综合所有打乱结果,期望为 356\dfrac{35}{6}。