题意：给你一个长度为n的括号匹配串(不一定恰好匹配)，让你在这个串的前面加p串和后面加上q串，使得这个括号串平衡(平衡的含义是对于任意位置的括号前缀和大于等于0，且最后的前缀和为0)。
思路：枚举这个字符串前面p字符串的长度，我们可以使得p字符串的前缀和大于等于字符串s的最小前缀和minx，那么p+s就符合前缀和大于等于0，然后q的方案数也能确定了。我们用dp[i][j]表示i个括号平衡度为j的方案数，那么可以先预处理出来dp的值。然后我们算出s字符串的最小前缀和minx，最后我们只要枚举p的长度i和平衡度j，那么sum+=dp[i][j]*dp[n-m-i][per_s+j],(per_s是整个s字符串的平衡度,per_s+j为q的平衡度).
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<cstring>
#include<stack>
#include<cmath>
#include<queue>
#define clc(a,b) memset(a,b,sizeof(a))
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn= ;
const int inf=0x3f3f3f3f;
char s[maxn];
const int mod=;
LL dp[][]; int main()
{
int n,m;
scanf("%d%d",&n,&m);
scanf("%s",s+);
clc(dp,);
dp[][]=;
for(int i=; i<=n-m; i++)
{
for(int j=; j<=i; j++)
{
if(j>)
dp[i][j]=(dp[i][j]+dp[i-][j-])%mod;
dp[i][j]=(dp[i][j]+dp[i-][j+])%mod;
}
}
int minx=inf;
int per_s=;
for(int i=; i<=m; i++)
{
if(s[i]=='(')
per_s++;
else
per_s--;
minx=min(minx,per_s);
}
LL sum=;
for(int i=; i<=n-m; i++)
for(int j=; j<=i; j++)
{
if(j+minx>=&&j+per_s<=n-m-i)
sum=(sum+dp[i][j]*dp[n-m-i][j+per_s])%mod;
}
cout<<sum<<endl;
return ;
}