题意

题目链接

给出一个长度为 $m$ 的括号串，在其前后增添字符构造长度为 $n$ 的合法括号串，求方案数。满足 $n-m \le 2000$。

解析

容易发现这是一道 dp 且复杂度基于 $n-m$。

我们已知中间的那条括号串 $S$，需要构造出左边的 $P$ 和右边的 $Q$（当然也可能为空）。通过 dp 方程转移时，考虑需要满足的两个条件，及 ‘(‘ 和 ‘)’ 的数量以及前缀。由于对于任何前缀，均满足 ‘(‘ 的数量大于等于 ‘)’ 的数量，我们可以定义 $f_{i,j}$ 为 $i$ 个字符，'(‘ 的数量减去 ‘)’ 的数量为 $j$ 的总方案数。

求出 $f$ 数组后，接着我们可以枚举 $P$ 和 $Q$，考虑他们所需要满足的条件。

• 如果 $S$ 中有一段前缀 ‘)’ 比 ‘(‘ 多，那么 $P$ 显然是需要弥补的（即 ‘(‘ 要比 ‘)’ 多），而所最少需要弥补的数量就为 ‘)’ 比 ‘(‘ 多最多的那个前缀。
• $P$ 和 $S$ 总的 ‘(‘ 的数量减去 ‘)’ 的值不能比 $Q$ 长，这是显然的。

如此我们容易地枚举了 $P$ 和 $Q$，计算贡献显然就是乘法原理。$P$ 的价值显而易见为 $f_{i,j}$，而 $Q$ 的价值为 $f_{n-m-i,j+tmp}$( $tmp$ 为 $S$ 中 ‘(‘ 的数量减去 ‘)’ 的值)。为什么呢？我们可以逆向思维，从后往前构筑 $Q$，那么前缀条件的定义就反了一下，也就自然得到了这个式子，应当可以自行理解。

将每组的 $P$ 和 $Q$ 的贡献乘起来再累加即可得到答案

代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2050;
const int M=2e5+5;
const int mod=1e9+7;    
int n,m,f[N][N],minn,ans,tmp;//f 表示 i 个字符，j=num'(' - num')'
char s[M];
signed main(){
    scanf("%lld%lld",&n,&m);
    scanf("%s",s+1);
    f[0][0]=1; 
    for(int i=1;i<=2000;i++){//保证前缀和满足的情况下的方案数 
        f[i][0]=f[i-1][1];
        for(int j=1;j<=i;j++){
            f[i][j]=(f[i-1][j-1]+f[i-1][j+1])%mod;
        }
    }
    for(int i=1;i<=m;i++){//统计右括号最多比左括号多的，左边要补；
        if(s[i]=='(') tmp++;//以及 num'(' - num')'   
        else tmp--;
        minn=min(tmp,minn);
    }
    for(int i=0;i<=n-m;i++){
        for(int j=0;j<=i;j++){
            if(j+minn>=0&&j+tmp<=n-m-i){//左边及给出的串保证前缀符合且前缀不会大到右边补不回来 
                ans=(ans+(f[i][j]*f[n-m-i][j+tmp])%mod)%mod;//逆向思维 
            }
        }
    }
    printf("%lld\n",ans); 
    return 0;
}