配点 : {100} 点
問題文
青叶想出了下一个问题。
Max 括号分数
长度 小于或等于 2N 整数序列 给出 A=(A_1,A_2,\ldots,A_{2N}) 。长度 2N 的正确括号序列 s , s 的分数确定如下。
- s_i 是 在
(的所有 i 以同样的方式定义 A_i 之和 计算长度 小于或等于 2N 正确括号序列可能的最大分数。
由于这个问题对广濑来说很简单,所以进行了如下修改。
Shuffle and Max 括号分数
长度 小于或等于 2N 整数序列 给出 A=(A_1,A_2,\ldots,A_{2N}) 。 对于 A 在将 Shuffle and Max 括号分数均匀随机打乱后的 Max 括号分数的期望值 \mathrm{mod}\ 998244353 找到它。
请解 Shuffle and Max 括号分数。
正确的括号序列为
定义满足以下任何条件的字符串为正确括号序列。- 空文字列
- 一些正确的括号序列 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