给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。
两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。
例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()、()(())、(())()、(()()) 和 ((()))。
输入格式
输入一行包含一个字符串 s，表示给定的括号序列，序列中只有左括号和右括号。
输出格式
输出一个整数表示答案，答案可能很大，请输出答案除以 1000000007 的余数。
合法括号序列的定义: 对于任意前缀，左括号的数量
≥
\geq
≥右括号的数量。
首先
n
≤
5000
n\leq5000
n≤5000，那么我们要控制在
n
2
n^2
n2的复杂度内。
思考第一个问题 ：添加左括号和右括号的方案数是否独立？
因为题目要求得是最小的添加数量，假设我们添加一对括号，肯定是无用的。我们先添加完左括号，再添加右括号，那么可以肯定的是只有
)
)
(
(
) ) ( (
))((这一种排列方式，否则的话会相互抵消为一对，那么我们的添加将毫无意义。所以得出结论 ：二者相互独立，答案即为
a
n
s
=
添
加
左
括
号
的
数
量
×
添
加
右
括
号
的
数
量
ans = 添加左括号的数量\times添加右括号的数量
ans=添加左括号的数量×添加右括号的数量， 分开计算即可。
根据合法括号序列的性质，我们只需在每个右括号之前添加左括号使其满足前缀性质。那么显然该序列被右括号分成了
c
n
t
右
括
号
+
1
cnt_{右括号} + 1
cnt右括号+1段，我们只需在每一段添加左括号使其合法。
状态定义 ：
f
[
i
,
j
]
f[i,j]
f[i,j]表示对于前
i
i
i个字符，左括号数量比右括号数量多
j
j
j个的集合。
那么我们最后的答案就是满足
f
[
n
,
i
]
≠
0
f[n,i]\neq0
f[n,i]=0的最小的
i
i
i,输出
f
[
n
,
i
]
f[n,i]
f[n,i]。
状态转移
s
[
i
]
=
′
(
′
s[i]='('
s[i]=′(′：
f
[
i
,
j
]
=
f
[
i
−
1
,
j
−
1
]
f[i,j]=f[i-1,j-1]
f[i,j]=f[i−1,j−1]
s
[
i
]
=
′
)
′
s[i]=')'
s[i]=′)′ ：对集合进行划分：
添加0个左括号：
f
[
i
]
[
j
]
=
f
[
i
−
1
,
j
+
1
]
f[i][j]=f[i-1,j+1]
f[i][j]=f[i−1,j+1],当前的右括号抵消了一个变为
j
j
j个。
添加1个左括号：
f
[
i
]
[
j
]
=
f
[
i
−
1
,
j
]
f[i][j]=f[i-1,j]
f[i][j]=f[i−1,j],添加的和当前的抵消。
添加2个左括号：
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
−
1
]
f[i][j]=f[i-1][j-1]
f[i][j]=f[i−1][j−1]。
…
添加
j
+
1
j+1
j+1个左括号：
f
[
i
]
[
j
]
=
f
[
i
−
1
,
0
]
f[i][j]=f[i-1,0]
f[i][j]=f[i−1,0]。
综上 ：
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
0
]
+
f
[
i
−
1
]
[
1
]
+
.
.
.
+
f
[
i
−
1
]
[
j
+
1
]
f[i][j]=f[i-1][0]+f[i-1][1]+...+f[i-1][j+1]
f[i][j]=f[i−1][0]+f[i−1][1]+...+f[i−1][j+1]。
发现
f
[
i
]
[
j
−
1
]
=
f
[
i
−
1
]
[
0
]
+
f
[
i
−
1
]
[
1
]
+
.
.
.
+
f
[
i
−
1
]
[
j
]
f[i][j-1]=f[i-1][0]+f[i-1][1]+...+f[i-1][j]
f[i][j−1]=f[i−1][0]+f[i−1][1]+...+f[i−1][j]。
那么优化后：
f
[
i
]
[
j
]
=
f
[
i
]
[
j
−
1
]
+
f
[
i
−
1
]
[
j
+
1
]
f[i][j]=f[i][j-1]+f[i-1][j+1]
f[i][j]=f[i][j−1]+f[i−1][j+1]
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5100, mod = 1e9 + 7;
LL f[N][N];
int n;
char s[N];
LL solve(){
memset(f, 0, sizeof f);
f[0][0] = 1;
for(int i = 1; i <= n; i++){
if(s[i] == '(') {
for(int j = 1; j <= n; j++)
f[i][j] = f[i - 1][j - 1];
} else{
f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
for(int j = 1; j <= n; j++)
f[i][j] = (f[i][j - 1] + f[i - 1][j + 1]) % mod;
}
}
for(int i = 0; i <= n; i++)
if(f[n][i])
return f[n][i];
return 0;
}
int main(){
scanf("%s", s + 1);
n = strlen(s + 1);
LL x = solve();
reverse(s + 1, s + 1 + n);
for(int i = 1; i <= n; i++)
if(s[i] == '(') s[i] = ')';
else s[i] = '(';
LL y = solve();
cout << x * y % mod;
return 0;
}