CF1781F Bracket Insertion（2700*） 题解（括号匹配DP）

题解（括号匹配DP）"/>

CF1781F Bracket Insertion（2700*） 题解（括号匹配DP）

题目

题面
简要题意：

        你需要执行一下步骤 n n n 次来构建括号序列：
        ⋅ \cdot ⋅ 等概率选择一个空位（若当前有 k k k 个字符，则有 k + 1 k + 1 k+1 个空位）。
        ⋅ \cdot ⋅ 以 p p p 的概率插入字符串 () 或以 1 − p 1 - p 1−p 的概率插入字符串 )(，插入后长度增加 2 2 2。
        给定 n , p n,p n,p，求出最后得到一个合法括号序列的概率，对 998244353 998244353 998244353 取模。
        注意：读入的是 q q q，而 p = q × 1 0 − 4 p = q \times 10^{-4} p=q×10−4。
        1 ≤ n ≤ 500 , 0 ≤ q ≤ 1 0 4 1 \leq n \leq 500, 0 \leq q \leq 10^4 1≤n≤500,0≤q≤104。

分析

        首先，括号匹配 的经典想法是 把左括号看成 1 1 1，把右括号看成 − 1 -1 −1。那么一个序列合法的 充要条件 是 任意前缀非负并且整个序列和为 0 0 0。

        那么我们考虑维护前缀和序列，初始时前缀和序列为 { 0 } \left \{ 0 \right \} {0}。那么一次插入 () 操作，就是随机从前缀和序列里面选一个数 x x x，在它的后面加上 { x + 1 , x } \left \{ x + 1, x \right \} {x+1,x}。一次插入 )( 操作，就是随机从前缀和序列里面选一个数 x x x，在它的后面加上 { x − 1 , x } \left \{ x - 1, x \right \} {x−1,x}。

        我们给操作附上一个权值：如果插入 ()，那么这次操作的权值为 p p p；如果插入 )(，那么这次操作的权值为 1 − p 1 - p 1−p。然后定义一个操作序列的权值为 所有操作权值的积。那么我们只需要考虑怎样求出所有合法的操作序列的权值和就行了。

        设 f n , x f_{n, x} fn,x​ 表示当前集合里面只有一个数 x x x，需要进行 n n n 次操作，所有合法操作序列的权值和。那么有转移：

        f n , x = ∑ i = 0 n − 1 ∑ j = 0 n − 1 − i p × C n − 1 i × C n − 1 − i j × f i , x × f j , x + 1 × f n − 1 − i − j , x + ∑ i = 0 n − 1 ∑ j = 0 n − 1 − i ( 1 − p ) × C b − 1 i × C n − 1 − i j × f i , x × f j , x − 1 × f n − 1 − i − j , x f_{n, x} = \sum_{i = 0}^{n - 1}\sum_{j = 0}^{n - 1 - i} p \times C_{n - 1}^{i} \times C_{n - 1 - i}^{j} \times f_{i, x} \times f_{j, x + 1} \times f_{n - 1 - i - j, x} + \sum_{i = 0}^{n - 1}\sum_{j = 0}^{n - 1 - i}(1 - p) \times C_{b - 1}^{i} \times C_{n - 1 - i}^{j} \times f_{i, x} \times f_{j, x - 1} \times f_{n - 1 - i - j, x} fn,x​=∑i=0n−1​∑j=0n−1−i​p×Cn−1i​×Cn−1−ij​×fi,x​×fj,x+1​×fn−1−i−j,x​+∑i=0n−1​∑j=0n−1−i​(1−p)×Cb−1i​×Cn−1−ij​×fi,x​×fj,x−1​×fn−1−i−j,x​。

        上面这个转移的含义就是：讨论第一次操作是插入 () 还是 插入 )(。如果插入()，那么第一次操作完后会多两个元素。并且还剩下 n − 1 n - 1 n−1 次操作。我们枚举分别分给这三个集合多少个操作，乘组合数是因为顺序不同方案是不同的，然后乘上它们的权值和。如果插入 )( 也是同理。

        那么这样我们就有了一个 O ( n 2 ) O(n^2) O(n2) 的状态和 O ( n 2 ) O(n^2) O(n2) 的转移。这样总复杂度是 O ( n 4 ) O(n^4) O(n4) 的。考虑优化：
        发现有很多 公共项，我们把这两个式子合并，得到：

        f n , x = ∑ i = 0 n − 1 ∑ j = 0 n − 1 − i C n − 1 i × C n − 1 − i j × f i , x × f n − 1 − i − j , x × [ p × f j , x + ( 1 − p ) × f j , x − 1 ] f_{n, x} = \sum_{i = 0}^{n - 1}\sum_{j = 0}^{n - 1 - i}C_{n - 1}^{i} \times C_{n - 1 - i}^{j} \times f_{i, x} \times f_{n - 1 - i - j, x} \times \left [ p \times f_{j, x} + (1 - p) \times f_{j, x - 1} \right ] fn,x​=∑i=0n−1​∑j=0n−1−i​Cn−1i​×Cn−1−ij​×fi,x​×fn−1−i−j,x​×[p×fj,x​+(1−p)×fj,x−1​]。

        我们尝试把 i i i 看做是一个定量，把它拿出来：

        f n , x = ∑ i = 0 n − 1 C n − 1 i × f i , x × ∑ j = 0 n − 1 − i C n − 1 − i j × f n − 1 − i − j , x × [ p × f j , x + ( 1 − p ) × f j , x − 1 ] f_{n, x} = \sum_{i = 0}^{n - 1} C_{n - 1}^{i} \times f_{i, x} \times \sum_{j = 0}^{n - 1 - i}C_{n - 1 - i}^{j} \times f_{n - 1 - i - j, x} \times \left [ p \times f_{j, x} + (1 - p) \times f_{j, x - 1} \right ] fn,x​=∑i=0n−1​Cn−1i​×fi,x​×∑j=0n−1−i​Cn−1−ij​×fn−1−i−j,x​×[p×fj,x​+(1−p)×fj,x−1​]。

        观察 j j j 的那一块，发现上界是 n − 1 − i n - 1 - i n−1−i，然后式子里面含 i i i 的都是含有 n − 1 − i n - 1 - i n−1−i 这一个整体。

        然后我们设 g k , x = ∑ i = 0 k C k i × f k − i , x × [ p × f i , x + ( 1 − p ) × f i , x − 1 ] g_{k, x} = \sum_{i = 0}^{k}C_{k}^{i} \times f_{k - i, x} \times [p \times f_{i, x} + (1 - p) \times f_{i, x - 1}] gk,x​=∑i=0k​Cki​×fk−i,x​×[p×fi,x​+(1−p)×fi,x−1​]。

        那么 f n , x = ∑ i = 0 n − 1 C n − 1 i × f i , x × g n − 1 − i , x f_{n, x} = \sum_{i = 0}^{n - 1} C_{n - 1}^{i} \times f_{i, x} \times g_{n - 1 - i, x} fn,x​=∑i=0n−1​Cn−1i​×fi,x​×gn−1−i,x​。

        此时就可以 O ( n ) O(n) O(n) 转移了。时间复杂度 O ( n 3 ) O(n^3) O(n3)。

        因为我们还要考虑每一步随机选数的概率， 所以最后答案是 f n , 0 1 × 3 × 5 × 7 × . . . × ( 2 × n − 1 ) \frac{f_{n, 0}}{1 \times 3 \times 5 \times 7 \times ... \times (2 \times n- 1)} 1×3×5×7×...×(2×n−1)fn,0​​。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
typedef long long LL;
const LL mod = 998244353;
LL p, q, f[N][N], g[N][N], c[N][N];
LL inv;
int n;
LL Pow(LL x, LL y){LL res = 1, k = x % mod;while(y){if(y & 1) res = res * k % mod;y >>= 1;k = k * k % mod;}return res;
}
int main(){// 目标 f[n][0] for(int i = 0; i <= 500; i++){for(int j = 0; j <= i; j++){if(j == 0) c[i][j] = 1LL;else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;}}scanf("%d%lld", &n, &p);inv = 1LL;for(int i = 1; i <= n; i++){inv = inv * Pow(2LL * i - 1LL, mod - 2) % mod;}p = p * Pow(10000LL, mod - 2LL) % mod;q = ((1LL - p) % mod + mod) % mod;for(int i = 0; i <= n; i++) f[0][i] = 1LL;for(int i = 1; i <= n; i++){for(int j = 0; j <= n; j++){// g[i - 1][j]for(int k = 0; k <= i - 1; k++){g[i - 1][j] = (g[i - 1][j] + c[i - 1][k] * f[i - 1 - k][j] % mod * ((p * f[k][j + 1] + q * f[k][j - 1]) % mod) % mod) % mod;}}for(int j = 0; j <= n; j++){for(int k = 0; k <= i - 1; k++){f[i][j] = (f[i][j] + c[i - 1][k] * f[k][j] % mod * g[i - 1 - k][j] % mod) % mod;}}}printf("%lld\n", f[n][0] * inv % mod);return 0;
}