#P18329. Shuffle and Max Bracket Score
Shuffle and Max Bracket Score
Shuffle and Max Bracket Score
Aoba 提出了下面的问题。
Max Bracket Score
给定一个长度为 的整数序列 。对于一个长度为 的合法括号序列 ,它的得分定义为:
- 将所有满足 为左括号
(的位置 所对应的 相加。
求所有合法括号序列中,能够获得的最大得分。
Hirose 认为这个问题太简单,于是提出了下面的问题。
Shuffle and Max Bracket Score
给定一个长度为 的整数序列 。将 均匀随机地打乱后,计算 Max Bracket Score 问题答案的期望值,对 取模。
请解决 Shuffle and Max Bracket Score。
合法括号序列的定义
一个字符串是合法括号序列,当且仅当它符合下列条件之一:
- 它是空字符串;
- 它可以写成
(、某个合法括号序列 、)依次连接得到的字符串; - 它可以写成两个合法括号序列 连接得到的字符串。
期望值取模的定义
所求期望是一个有理数。题目保证,在本题的数据范围内,将该期望化为最简分数 后,分母 不被 整除。
此时存在唯一整数 ,满足 且
请输出这个 。
输入格式
输入只有一组数据,格式如下:
N
A_1 A_2 ... A_{2N}
输出格式
输出一行一个整数,表示所求期望对 取模的结果。
数据范围
- ;
- ;
- 所有输入值均为整数。
样例输入 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
样例说明
第一组中:
- 当 时,唯一的合法括号序列为
(),最大得分是 ; - 当 时,最大得分是 。
因此期望为 。
第二组中:
- 例如 时,
()()的得分为 ,(())的得分为 ,最大得分为 ; - 例如 时,
()()的得分为 ,(())的得分为 ,最大得分为 。
综合所有打乱结果,期望为 。