← 返回题目列表

AtCoder · tupc2024_k

K. 随机播放和最大括号分数

中文机器翻译题面 查看原题

配点 : {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