AT_tupc2024_k.Shuffle and Max Bracket Score

あおば提出了如下问题。

最大括号分数（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$ 随机等概率地重排一次后，求其最大括号分数的期望值，并对 $998244353$ 取模输出。

请解决 Shuffle and Max Bracket Score 问题。

合法括号序列的定义如下。满足以下条件之一的字符串被称为合法括号序列：
- 空字符串；
- 存在一个合法括号序列 $S$，字符串 `(`, $S$, `)` 按顺序拼接而成；
- 存在非空合法括号序列 $S, T$，字符串 $S, T$ 按顺序拼接而成。

关于期望值取模 $998244353$ 的说明：
你所要求的期望值一定是有理数。在本题的约束下，设期望值为最简分数 $\frac{P}{Q}$，则 $Q\not\equiv 0 \pmod{998244353}$。因此，满足 $R\times Q\equiv P\pmod{998244353}, 0\leq R<998244353$ 的 $R$ 一定唯一。请输出此 $R$。

输入从标准输入以如下格式给出。

$N$ $A_1$ $A_2$ $ \ldots $ $A_{2N}$

请输出所求期望值对 $998244353$ 取模后的结果。

部分分

• 若你能正确解决满足 $N\leq 100$ 的数据集，可以得到 $10$ 分。

样例解释 1

$A=(1,2)$ 时，Max Bracket Score 答案为 $1$。

• $s$ 为 () 时得分为 $1$。

$A=(2,1)$ 时，Max Bracket Score 答案为 $2$。

• $s$ 为 () 时得分为 $2$。

因此期望值为 $\frac{1}{2}(1+2)=\frac{3}{2}$。

样例解释 2

比如 $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$。

所以期望值为 $\frac{35}{6}$。

数据范围

• $1\leq N\leq 10^5$
• $1\leq A_i \leq 10^9$
• 所有输入为整数。

由 ChatGPT 5 翻译