CF1781F Bracket Insertion

· · 题解

场上差一步，于是被别人区分了。其实也不算是很难的题，但是还是需要对这个类型的 DP 比较熟练。

首先插入括号串可以画出折线，如果我们维护原串的前缀和，把 ( 看做 +1，) 看做 -1，那么括号串合法的充要条件是前缀和所有元素非负。原本还需要最后一项为 0，但是本题的限制显然符合。

考虑每次插入一对括号对前缀和序列的影响。由于总是有一个 ( 和一个 )，所以它后面的前缀和一定不会变化。假设插入位置前面的前缀和是 x，那么可以得到：如果插入 ()，会生成 x,x+1；如果插入 )(，会生成 x,x-1。所以容易发现这和序列每个元素的位置也无关。

问题转化为：给定一个集合，初始为 \{0\}，每次随机选择一个元素 x，有 p 的概率将 x+1,x 加入集合，有 1-p 的概率将 x-1,x 加入集合，求最终所有元素非负的概率。

到这里其实不难。接下来我们把概率转方案数：注意到 k 次操作后的集合大小一定为 2k+1，所以其实概率是可以计算的。如果我们给每次操作赋权值 p 和 1-p，一个合法操作集合的权值是每次操作的权值积，那么我们可以将问题转化为：所有合法操作集合的权值和。

这个问题考虑 DP。定义 f(n,x) 表示初始为 x 这个数，进行 n 次操作后仍然合法的操作集合的权值和。我们可以得到：

f(n,x)= \sum\limits_{i=0}^{n-1} \sum\limits_{j=0}^{n-1-i} p \cdot \binom{n-1}{i} \cdot \binom{n-1-i}{j} \cdot f(i, x) \cdot f(j, x + 1) \cdot f(n - 1 - i - j, x) + + \sum\limits_{i=0}^{n-1} \sum\limits_{j=0}^{n-1-i} (1 - p) \cdot \binom{n-1}{i} \cdot \binom{n-1-i}{j} \cdot f(i, x) \cdot f(j, x - 1) \cdot f(n - 1 - i - j, x)

这个式子的含义是，考虑这个 x 第一次操作会变成什么，有 p 权值会变成 x,x,x+1，有 1-p 权值会变成 x,x,x-1。考虑接下来 n-1 次操作，每次可以分配到这三个集合里的一个，所以是用组合数相乘。

这样喜提 O(n^4)，过不去。但是注意到这个式子太特殊了，有重复项，可以提出来。这一步并不困难。考虑定义

g(k, x) = \sum\limits_{i=0}^{k} \binom{k}{i} \cdot f(i, x) \cdot f(k - i, x)

可以得到

f(n, x) = \sum\limits_{j=0}^{n-1} (p \cdot f(j, x + 1) + (1 - p) \cdot f(j, x - 1)) \cdot \binom{n-1}{j} \cdot g(n - 1 - j, x)

这样我们就得到了 O(n^2) 状态，O(n) 转移，时间复杂度是 O(n^3)。其实这样优化是把两个 x 合并在一起算了。

注意到最终算的是权值和，要除以 1\times 3\times ...\times (2n-1)=(2n-1)!!。

以上部分公式来自 tourist 题解，膜拜 tourist。