题意：
给出一个只由\((\)和\()\)构成的字符串s，其长度为m，在其前后分别添加字符串p和q，使其总长度为n，并且字符串的\((\)和\()\)数量相等，任意前缀的\((\)的数量不少于\()\)，求有多少种p和q使字符串成立。
思路：
设\(dp_{i,j}\)为字符串长度为i，\((\)的个数比\()\)多j个的方案数，初始化为\(dp_{0,0}=1\)，转移为\(dp_{i,j}=\begin{cases}dp_{i-1,j-1}+dp_{i-1,j+1},&j>0\\dp_{i-1,j+1},&j=0\end{cases}\) 又\((\)和\()\)可以互换，所以\(dp_{i,j}=dp_{i,-j}\)，然后枚举串s，求出\((\)和\()\)数量的最小差值minum和最终的差值finum。因为括号要匹配，所以p和q是对称的，通过枚举p可得到q，枚举p的长度i，当\(j>-minum\)并且\(finum+j<=n-m-i\)时，可以把p放在s前面，q放在后面，此时q的方案数为\(dp_{n-m-i,j}+minum\)，根据乘法原则，总的方案数增加\(dp_{i,j}*dp_{n-m-i,j}+minum\)
#include <iostream>
using namespace std;
#define FIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define FILEREAD freopen("input.txt", "r", stdin);
long long dp[2001][2001];
char s[100001];
const long long MOD = 1000000007;
int main()
{
#ifndef ONLINE_JUDGE
FILEREAD
#endif
FIO
int n, m;
cin >> n >> m;
cin >> s;
dp[0][0] = 1;
for (int i = 1; i <= n - m; ++i)
for (int j = 0; j <= i; ++j)
if (j == 0)
dp[i][j] = dp[i - 1][j + 1];
else
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;
int finum = 0, minum = m;
for (int i = 0; i < m; ++i)
{
if (s[i] == '(')
++finum;
else
--finum;
if (minum > finum)
minum = finum;
}
long long ans = 0;
for (int i = 0; i <= n - m; ++i)
for (int j = 0; j <= i; ++j)
if (j > -minum && finum + j <= n - m -i)
ans = (ans + dp[i][j] * dp[n - m - i][j + finum]) % MOD;
cout << ans << '\n';
return 0;
}