有一个初始为空的括号序列，依次执行 \(n(n\le 500)\) 次操作，每次有 \(p\) 的概率选取
()，\(1-p\) 的概率选取)(，随机插入首部、尾部、中间的空隙（也就是从 \(2i-1\) 个位置中随机选取一个插入，其中 \(i\) 为操作序号）。问最后的序列为合法括号序列的概率。
与合法括号序列相关的有效联想
- 括号树
- 扫描+维护栈
- 区间 DP
- 01 替换；±1 替换，变成所有前缀和非负
...
在本题中，区间 DP 明显不可行，第二条的连续性不符合，括号树经过尝试难以进行，因此只能 ±1 替换，变成所有前缀和 \(\ge 0\)。
发现子问题
子问题的形式通常由问题自带的特征勾勒。括号序列的特征是括号对，我们着眼于最近的一对——当前第一个字符及其匹配括号（同时加入的那个）。
分界点的存在往往将问题分割成内、外（或左、中、右等），子问题往往是其中的一个或多个。在本题中，如果大问题是整个括号序列的所有前缀和 \(\ge 0\)，那么在上述两个括号之间夹着的部分，就应该满足其所有前缀和 \(\ge 1\)(当这对括号是 )( 时)或 \(\ge -1\)(当这对括号是 () 时)，而由于当前第一个字符到其匹配括号的这一段前缀和必然是 0，因而右侧的部分只需同样满足 \(\ge 0\)。
至此子问题的参数已基本勾勒成形，设 \(f(i,s)\) 表示按照题意构成含 \(i\) 对括号的序列，其各个前缀和都 \(\ge s\) 的概率是多少。其中 \(s>0\) 是永远无法满足的，值为 0；\(s=0\) 就是我们终状态要的 \(f(n,0)\)；而 \(-n\le s\le 0\) 是我们 DP 递推的部分；\(f(i,-n-1)=1,f(0,s\le 0)=1\)。
转移时枚举两者中间包含的括号对数量 \(k\)，当 )( 时分成 \(f(k,s+1),f(n-k-1,s)\) 两个子问题，当 () 时分成 \(f(k,s-1),f(n-k-1,s)\) 两个子问题。值得注意的是，还要乘上中间恰夹着 \(k\) 对括号的前提概率，为此我们不得不设置一个辅助数组 \(g(i,k)\)。
依题意得 \(g(i,k)\cdot \frac{2i-2k-1}{2i+1}\to g(i+1,k)\)，\(g(i,k)\cdot \frac{2k+1}{2i+1}\to g(i+1,k+1)\)，\(g(i,k)\cdot \frac{1}{2i+1}\to g(i+1,0)\)。
#include <bits/stdc++.h>
using namespace std;
const int N=505,mod=998244353;
int n,qq,p,inv[N*2],f[N][N+3],g[N][N];
inline void add(int &x,int y){(x+=y)>=mod&&(x-=mod);}
inline int qp(int a,int b){
int c=1;
for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)c=1ll*c*a%mod;
return c;
}
int main(){
cin>>n>>qq;
p=qq*796898467ll%mod;
inv[0]=1; for(int i=1;i<=2*n+1;i++)inv[i]=qp(i,mod-2);
g[1][0]=1;
for(int i=1;i<n;i++)for(int k=0;k<n;k++){
add(g[i+1][k],1ll*g[i][k]*(2*i-2*k-1)%mod*inv[2*i+1]%mod);
add(g[i+1][k+1],1ll*g[i][k]*(2*k+1)%mod*inv[2*i+1]%mod);
add(g[i+1][0],1ll*g[i][k]*inv[2*i+1]%mod);
}
for(int s=-n;s<=0;s++)f[0][s+N]=1;
for(int i=0;i<=n;i++)f[i][-n-1+N]=1;
for(int i=1;i<=n;i++)for(int s=-n;s<=0;s++){
for(int k=0;k<i;k++)
add(f[i][s+N],1ll*g[i][k]*f[i-k-1][s+N]%mod*(f[k][s+1+N]*(mod+1ll-p)%mod+1ll*f[k][s-1+N]*p%mod)%mod);
}
cout<<f[n][N];
}