#261 CF1781F
题目传送门
首先，套路地将括号序列转化为包含 \(-1,1\) 的序列。
那么考虑到插入一个 () 就是将前缀和 \(x\) 扩展为 \(x,x+1,x\)，插入一个 )( 就是将前缀和 \(x\) 扩展为 \(x,x-1,x\)。
那么记 \(f_{i,x}\) 表示 \(0\) 位置的前缀和为 \(x\)，往后插入 \(i\) 个括号的合法方案数，转移枚举在哪插入：
\[f_{n,x}=\sum_{i=0}^{n-1}\sum_{j=0}^{n-i-1}pf_{i,x}f_{j,x+1}f_{n-i-j-1,x}\binom{n-1}{i}\binom{n-1-i}{j}+\cdots
\]
省略了插入 )( 的方案。此时时间复杂度是 \(O(n^4)\)。
注意到 \(i,j\) 转移相对独立，且两部分除了中间的部分都一样，尝试分离。
\[f_{n,x}=\sum_{i=0}^{n-1}\binom{n-1}{i}(pf_{i,x+1}+(1-p)f_{i,x-1})\sum_{j=0}^{n-i-1}\binom{n-i-1}{j}f_{j,x}f_{n-i-j-1,x}
\]
那么用辅助数组记录后面那一部分内容即可。
时间复杂度 \(O(n^3)\)。
#262 P9522
题目传送门
首先将限制转化为：（以较小数为 \(L\)，较大数为 \(R\)）
- 一类限制：区间 \([L,R]\) 内第一个满足 \(s_L \neq s_k\) 的位置 \(k\)，要求 \(s_k >s_L\)；
- 二类限制：区间 \([L,R]\) 内第一个满足 \(s_L \neq s_k\) 的位置 \(k\)，要求 \(s_k <s_L\)；
那么记 \(f_{i,j}\) 表示已经确定了前 \(i\) 个字符，且 \(s_i=j\) 时的方案数。那么枚举 \(s_i\) 和 \(s_{i-1}\) 的大小关系。如果相等，那么没有任何限制，直接从 \(f_{i-1,j}\) 转移过来；否则需要在前面找上一次满足相同大小关系的点，满足 \(i\) 和这个点间没有另一种大小关系的限制，这是显然可以通过前缀和算的，转移时也要前缀和优化。
时间复杂度 \(O(n|\Sigma|)\)。