分析：
本题妙就妙在没有直接计算每种深度，而是逐层扩展，考虑新增括号的方案贡献。因为假如外面有一层括号，那么所有区间内方案的深度都要加1，这个贡献是可以算的。
//Interval DP #include<bits/stdc++.h> #define int long long using namespace std; const int N=2005; const int mod=998244353; int n,dp[N][N],g[N]; char s[N]; int kpow(int x,int y) { int tot=1; for(;y;y>>=1) { if(y&1) tot=(tot*x)%mod; x=(x*x)%mod; } return tot; } signed main() { scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<=n;i++) { if(s[i]=='?') g[i]=g[i-1]+1; else g[i]=g[i-1]; } for(int len=2;len<=n;len++) { for(int i=1;i<=n-len+1;i++) { int j=i+len-1; if(s[i]=='('&&s[j]==')') dp[i][j]=dp[i+1][j-1]+kpow(2,g[j-1]-g[i]); if(s[i]=='('&&s[j]=='(') dp[i][j]=dp[i][j-1]; if(s[i]==')'&&s[j]=='(') dp[i][j]=dp[i+1][j-1]; if(s[i]==')'&&s[j]==')') dp[i][j]=dp[i+1][j]; if(s[i]==')'&&s[j]=='?') dp[i][j]=dp[i+1][j]; if(s[i]=='('&&s[j]=='?') dp[i][j]=dp[i+1][j-1]+kpow(2,g[j-1]-g[i])+dp[i][j-1]; if(s[i]=='?'&&s[j]=='(') dp[i][j]=dp[i][j-1]; if(s[i]=='?'&&s[j]==')') dp[i][j]=dp[i+1][j-1]+kpow(2,g[j-1]-g[i])+dp[i+1][j]; if(s[i]=='?'&&s[j]=='?') dp[i][j]=dp[i+1][j-1]+kpow(2,g[j-1]-g[i])+dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]; dp[i][j]%=mod; //printf("dp[%d][%d]=%d\n",i,j,dp[i][j]); } } printf("%lld",dp[1][n]); }