神仙 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;
}