括号序列相关计数 笔记

括号序列有一种做法，每次从最外层第一对配对的括号进行转移。

即对于区间 $\mathtt{\text{(}}\mathtt{\text{...}}\mathtt{\text{)}}\mathtt{\text{...}}$，从红色的这对括号转移。

1. CF1781F Bracket Insertion

对括号序列合法的定义进行转换：设 $\mathtt{\text{(}}$ 表示 $+1$，$\mathtt{\text{)}}$ 表示 $-1$，合法的前提是对于每个位置，前缀和 $\ge 0$。

于是考虑笔记开头说的转移方式，设 $f_{i,j}$ 表示长度为 $i$ 的区间，第一个位置代表的前缀和为 $j$ 的方案数。

考虑最终生成的括号序列，最外层的第一对括号。$\mathtt{\text{(*......}}$，因此我们加入的 $\mathtt{\text{()}}$ 或 $\mathtt{\text{)(}}$ 的第一个位置钦定在 $\mathtt{\text{*}}$，剩下一个括号在 $\mathtt{\text{\$}}$ 中任意放，对于 $\text{()}$，变成了

$$\mathtt{\text{(}}\mathtt{\text{(...}}\mathtt{\text{)...}}\mathtt{\text{..}}$$

的形式，其中红色是左括号统领的，前缀和增加 $1$，蓝色是右括号统领的，前缀和不变，可以递归成两个子问题求解，故

$$f_{i,j}\leftarrow \sum _{k1,k2}{f}_{k_1,j+1}\times f_{k_2,j}\times f_{i-1-k_1-k_2,j}\times p$$

插入 $\mathtt{\text{)(}}$ 同理

$$f_{i,j}\leftarrow \sum _{k1,k2}{f}_{k_1,j-1}\times f_{k_2,j}\times f_{i-1-k_1-k_2,j}\times p$$

状态数 $O(n^2)$，转移 $O(n^2)$，时间复杂度 $O(n^4)$，不能通过。

考虑优化，以第一种转移为例，考虑枚举 $K=k_1+k_2$，则有

$$f_{i,j}\leftarrow \sum _K{f}_{i-1-K,j}\times p\times \sum _{k1+k2=K}{f}_{k_1,j+1}\times f_{k_2,j}$$

后面的 $\sum$ 做 DP 即可优化到 $O(n)$ 预处理，$O(1)$ 查询。

这里还少考虑了个操作顺序的问题，因为当有多个部分转移过来时，不好处理操作总顺序，但是优化完后我们的代码一直都是从两个部分转移，假设一个部分大小为 $a$，另一部分大小为 $b$，我们在两个部分中的操作顺序是任意的，所以要乘上 $(\genfrac{}{}{0ex}{}{a+b}{a})$。

时间复杂度 $O(n^3)$。

2. CF888F Connecting Vertices

这个可以看作类括号序列问题，主要的思想还是一样的。

不复制并破环为链不影响答案。根据题意，发现所有的连边一定是包含或相离关系（称 $1-2$ 与 $2-3$ 也为相离）。

直接区间 DP 不对，因为和括号序列一样，会在 $\mathtt{\text{()()()}}$ 时枚举断点多次转移。

于是考虑钦定最外层第一个配对的位置进行转移，设 $f_{l,r,0/1}$ 表示考虑区间 $l\sim r$ 连通，$l\to r$ 是否直接连边的方案数，设 $f_{l,r}\leftarrow f_{l,r,0}+f_{l,r,1}$。初始时 $f_{i,i,1}\leftarrow 1$。

于是考虑最外层第一个连边，有两种情况：

1. 最外层第一对是 $l\to r$ 直接连边，于是在 $l,r$ 中枚举断点转移即可。

$$f_{l,r,1}=\sum _{\mathrm{mid}}{f}_{l,\mathrm{mid}}\times f_{\mathrm{mid}+1,r}$$

2. 最外层第一对是 $l\to \mathrm{mid}$，那么就是两个区间拼起来。

$$f_{l,r,1}=\sum _{\mathrm{mid}}{f}_{l,mid,1}\times f_{\mathrm{mid},\mathrm{r}}$$

时间复杂度是区间 DP 的 $O(n^3)$。