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

输入从标准输入以如下格式给出。 > $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 翻译