题解 Bracket Insertion

· · 题解

Bracket Insertion

神仙 DP 题，不愧是 tourist。

容易发现，括号序列一共有 1\cdot 3\cdot 5...\cdot (2n-1) 种生成方式。

假如 ( 为 1，) 为 -1，那么一个序列合法的充要条件为：最小前缀和为 0，且以 0 结尾。

现在考虑维护这些前缀和。

如果我们在当前序列某一位后插入一个 ()，且那一位的前缀和为 x,那么相当于把 x 替换成 [x,x+1,x]。

同理可知，插入 )( 相当于把 x 替换成 [x,x-1,x]。

定义 f_{n,x} 为，执行 n 次操作，初始前缀和为 x 的方案数。

那么显然有两种转移：

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

其中，i 对应第一个 x，j 对应 x+1 和 x-1，n-i-j-1 对应第二个 x。

由于每个部分的操作都是独立的，所以还要乘上组合数。

状态 n^2，转移枚举 O(n^2)，总复杂度 O(n^4)，无法接受。

我们考虑优化掉一个 \sum。将与 j 有关的都提到前面来。

f_{n,x}=\sum\limits_{j=0}^{n-1}\dbinom{n-1}{j}\cdot\left[p\cdot f_{j,x+1}+(1-p)\cdot f_{j,x-1}\right]\cdot \sum\limits_{i=0}^{n-j-1}\dbinom{n-j-1}{i}\cdot f_{i,x}\cdot f_{n-i-j-1,x}

定义 g_{n,x}=\sum\limits_{i=0}^{n}\dbinom{n}{i}\cdot f_{i,x}\cdot f_{n-i,x}

那么转移方程最终可化简为：

f_{n,x}=\sum\limits_{j=0}^{n-1}\dbinom{n-1}{j}\cdot\left[p\cdot f_{j,x+1}+(1-p)\cdot f_{j,x-1}\right]\cdot g_{n,n-j-1}

最后输出 \frac{f_{n,0}}{1\cdot 3\cdot 5...\cdot (2n-1)} 即可。

复杂度 O(n^3)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 500 + 5, mod = 998244353;
ll n, p, c[N][N], f[N][N], g[N][N];
ll ksm(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> p; p = p * ksm(10000, mod - 2) % mod;
    for (int i = 0; i <= n; ++i) c[i][0] = 1;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    for (int i = 0; i <= n; ++i) f[0][i] = g[0][i] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int x = 0; x <= n; ++x) {
            for (int j = 0; j < i; ++j) {
                f[i][x] = (f[i][x] + (p * f[j][x + 1] + (1 - p + mod) * (x ? f[j][x - 1] : 0)) % mod * c[i - 1][j] % mod * g[i - j - 1][x] % mod) % mod;
            }
            for (int j = 0; j <= i; ++j) {
                g[i][x] = (g[i][x] + c[i][j] * f[j][x] % mod * f[i - j][x] % mod) % mod;
            }
        }
    }
    ll ans = f[n][0];
    for (int i = 1; i <= 2 * n; i += 2) ans = ans * ksm(i, mod - 2) % mod;
    cout << ans << endl;
    return 0;
}