[题解] [Mivik Round nurture] Something Comforting

[题解] [Mivik Round nurture] Something Comforting

给出 一个生成括号序列的算法 和一个长度为 $2n$ 的合法括号序列,问这个括号序列通过这种算法被生成的概率。答案对 $998244353$ 取模。

$1\le n\le 5\cdot 10^5$

题目链接


思路

我们还是把括号序列转换成那个经典的“走右上右下”的形式,即从 $(0,0)$ 开始行走,左括号是向右上走,右括号是向右下走,那么一个括号序列合法等价与行走轨迹不越过 X 轴。比如下图是 ()(()) 对应的行走轨迹:

轨迹

我们发现,算法最开始随机 random_shuffle 出来的括号序列,对应着一个可能越过了 X 轴,但最终走到了 $(2n,0)$ 的行走轨迹(因为左括号右括号数目相等)。然后仔细观察我们的算法,实际上就是找到第一个低于 X 轴的位置和在这个位置后第一次走回 X 轴的位置,并把中间的一段翻到 X 轴上去了。这样必定能形成最终的合法括号序列。

于是答案就显而易见了。由于在翻转过程中我们的行走轨迹中与 X 轴相交的那些点是不变的,所以如果一个合法的括号序列对应的行走轨迹有 $m$ 个点与 X 轴相交,它就可能由 $2^{m-1}$ 次方种括号序列得到(每一个部分在 X 轴上方或者下方),所以答案就是 $\frac{2^{m-1}}{\binom{2n}n}$。

代码

mivik.h

代码

作者

Mivik

发布于

2021-01-10

更新于

2021-05-31

许可协议

评论