C. Famil Door and Brackets
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
As Famil Door’s birthday is coming, some of his friends (like Gabi) decided to buy a present for him. His friends are going to buy a string consisted of round brackets since Famil Door loves string of brackets of length n more than any other strings!
The sequence of round brackets is called valid if and only if:
Gabi bought a string s of length m (m ≤ n) and want to complete it to obtain a valid sequence of brackets of length n. He is going to pick some strings p and q consisting of round brackets and merge them in a string p + s + q, that is add the string p at the beginning of the string s and string q at the end of the string s.
Now he wonders, how many pairs of strings p and q exists, such that the string p + s + q is a valid sequence of round brackets. As this number may be pretty large, he wants to calculate it modulo 109 + 7.
Input
First line contains n and m (1 ≤ m ≤ n ≤ 100 000, n - m ≤ 2000) — the desired length of the string and the length of the string bought by Gabi, respectively.
The second line contains string s of length m consisting of characters '(' and ')' only.
Output
Print the number of pairs of string p and q such that p + s + q is a valid sequence of round brackets modulo 109 + 7.
Examples
input
4 1
(
output
4
input
4 4
(())
output
1
input
4 3
(((
output
0
Note
In the first sample there are four different valid pairs:
In the second sample the only way to obtain a desired string is choose empty p and q.
In the third sample there is no way to get a valid sequence of brackets.
思路:dp;
dp[i][j]表示前i个括号,开口向右减开口向左的值SS。方程:dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1].在i的时候当前选向左开口或向右开口。
可以知道dp[0][0]=1;由于n-m<=2000;所以枚举p,因为最后要平衡所以q也可以知道了,并且q的取值也就是前面的dp,因为要和前面匹配,前面p+s结束时必定有向右的
括号数大于向左的括号数,所以在剩下的q只要取向左的括号数数-向右的括号数,与前面的匹配中和就行了,也就是将前面的dp看成在i时开口向右减开口向左的值SS,所以套用前面的dp就行了。 最后sum=((sum)%N+(dp[i][j]*dp[cc][ans])%N)%N;
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8 typedef long long LL;
9 LL dp[2205][2205];
10 char str[100005];
11 int QZ[100005];
12 const LL N=1e9+7;
13 int main(void)
14 {
15 LL i,j,k,p,q;
16 dp[0][0]=1;
17 for(i=1;i<=2200;i++)
18 {
19 for(j=0;j<=i;j++)
20 {
21 if(j>0)
22 {
23 dp[i][j]=(dp[i][j]+dp[i-1][j-1])%N;
24 }
25 dp[i][j]=(dp[i][j]+dp[i-1][j+1])%N;
26 }
27 }
28 while(scanf("%I64d %I64d",&p,&q)!=EOF)
29 {memset(QZ,0,sizeof(QZ));
30 scanf("%s",str);LL meq=1e8;LL maxx;
31 for(i=0;i=0&&ans<=cc)
54 {
55 sum=((sum)%N+(dp[i][j]*dp[cc][ans])%N)%N;
56 }
57 }
58 }
59 printf("%I64d\n",sum);
60 }
61 return 0;
62 }
手机扫一扫
移动阅读更方便
你可能感兴趣的文章