【CF 629C】Famil Door and Brackets（dp，思维）

【CF 629C】Famil Door and Brackets（dp，思维）

目录

• 题目
• • 题面翻译
  • 描述
  • 输入
  • 输出
  • 数据规模
  • 题目描述
  • 输入格式
  • 输出格式
  • 样例 #1
  • • 样例输入 #1
    • 样例输出 #1
  • 样例 #2
  • • 样例输入 #2
    • 样例输出 #2
  • 样例 #3
  • • 样例输入 #3
    • 样例输出 #3
  • 提示
• 思路
• 代码

题目

题目传送门

题面翻译

描述

Family Door 的生日就要到了，Gabi（Family Door的好朋友）想要给他买一个礼物。Gabi决定买一个只包含 ‘(’、‘)’ 的字符串，毕竟 Family Door 最喜欢的字符串是长度为 n n n 的只包含 ‘(’、‘)’ 的字符串。

我们称一个只包含 ‘(’、‘)’ 的字符串“有效”当且仅当：

1. '(‘的数量等于’)'的数量；
2. 对于该字符串的任意前缀，均满足’(‘的数量大于等于’)'的数量；

Gabi 买了一个长度为 m m m 的只包含 ‘(’、‘)’ 的字符串 S S S。为了使它的长度达到 n n n ，Gabi要构造两个只包含’(‘、’)'的字符串 P , Q P,Q P,Q，然后将 P , S , Q P,S,Q P,S,Q 顺次连接得到字符串 S ′ S' S′ 。

给出Gabi买的字符串 S S S，要使 S ′ S' S′ 有效，Gabi有多少种构造 P , Q P,Q P,Q 的方案？（ P , Q P,Q P,Q都可以为空）。

输入

第一行包括整数 n , m n,m n,m；第二行为长度为 m m m 的字符串 S S S。

输出

输出一个正整数，表示构造 P , Q P,Q P,Q 的方案数，答案对 ( 1 0 9 + 7 ) (10^9+7) (109+7) 取模。

数据规模

1 ≤ m ≤ n ≤ 100000 , n − m ≤ 2000 1leq mleq nleq 100000,n-mleq 2000 1≤m≤n≤100000,n−m≤2000

题目描述

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 n n more than any other strings!

The sequence of round brackets is called valid if and only if:

1. the total number of opening brackets is equal to the total number of closing brackets;
2. for any prefix of the sequence, the number of opening brackets is greater or equal than the number of closing brackets.

Gabi bought a string s s s of length m m m ( m < = n m<=n m<=n ) and want to complete it to obtain a valid sequence of brackets of length n n n . He is going to pick some strings p p p and q q q consisting of round brackets and merge them in a string p + s + q p+s+q p+s+q , that is add the string p p p at the beginning of the string s s s and string q q q at the end of the string s s s .

Now he wonders, how many pairs of strings p p p and q q 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 1 0 9 + 7 10^{9}+7 109+7 .

输入格式

First line contains n n n and m m m ( 1 < = m < = n < = 100000 , n − m < = 2000 1<=m<=n<=100000,n-m<=2000 1<=m<=n<=100000,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 s s of length m m m consisting of characters ‘(’ and ‘)’ only.

输出格式

Print the number of pairs of string p p p and q q q such that p + s + q p+s+q p+s+q is a valid sequence of round brackets modulo 1 0 9 + 7 10^{9}+7 109+7 .

样例 #1

样例输入 #1

4 1
(

样例输出 #1

4

样例 #2

样例输入 #2

4 4
(())

样例输出 #2

1

样例 #3

样例输入 #3

4 3
(((

样例输出 #3

0

提示

In the first sample there are four different valid pairs:

1. p = p= p= “(”, q = q= q= “))”
2. p = p= p=“()”, q = q= q= “)”
3. p = p= p=“”, q = q= q= “())”
4. p = p= p=“”, q = q= q= “)()”

In the second sample the only way to obtain a desired string is choose empty p p p and q q q .

In the third sample there is no way to get a valid sequence of brackets.

思路

考虑 p , q p,q p,q 串所需满足的条件。
对于 s s s 串，我们可以将其化简，把合法的括号对去掉，这样 s s s 串剩下的形式应为 " ) ) ) ) ( ( ( " "))))(((" "))))((("。
注意题目条件，一个括号序列合法，说明对于该字符串的任意前缀，均满足 ′ ( ′ '(' ′(′ 的数量大于等于 ′ ) ′ ')' ′)′ 的数量。
那么对于接在开头的 p p p 串，所需要满足的条件应为 N l − N r ≥ P r N_{l}-N_{r}ge P_{r} Nl​−Nr​≥Pr​，其中 N l N_l Nl​ 为左括号个数， N r N_r Nr​ 为右括号个数， P r P_r Pr​ 为 s s s 串化简后的右括号个数。
对于接在末尾的 q q q 串，同理，应满足 N r − N l ≥ P l N_r-N_lge P_l Nr​−Nl​≥Pl​，其中 P l P_l Pl​ 为 s s s 串化简后左括号的个数。

考虑只枚举一边的字符串，不妨枚举 p p p。
记 f i , j f_{i,j} fi,j​ 为长度为 i i i，左括号个数比右括号个数多 j j j 个的方案数。
枚举 p p p 的长度 i i i，以及 N l − N r N_l-N_r Nl​−Nr​ 比 P r P_r Pr​ 多的个数 j j j，此时 p p p 串的方案数即为 f i , P r + j f_{i,P_r+j} fi,Pr​+j​。
显然， f i , j f_{i,j} fi,j​ 同时还表示长度为 i i i，右括号个数比左括号个数多 j j j 个的方案数。
那么，对应的 q q q 串长度就是 n − m − i n-m-i n−m−i， N r − N l N_r-N_l Nr​−Nl​ 比 P l P_l Pl​ 相应也要多 j j j，这样才能和 p p p 中多出来的 j j j 个左括号匹配，方案数即为 f n − m − i , P l + j f_{n-m-i,P_l+j} fn−m−i,Pl​+j​
两者相乘，再累加进 a n s ans ans 即可。

如何求 f i , j f_{i,j} fi,j​ 呢？这是一个很简单的 dp，考虑第 i i i 位加的左括号还是右括号即可。
转移方程： f i , j = f i − 1 , j − 1 + f i − 1 , j + 1 f_{i,j}=f_{i-1,j-1}+f_{i-1,j+1} fi,j​=fi−1,j−1​+fi−1,j+1​。
注意边界的处理。

代码

#include <bits/stdc++.h>
#define rep(i, a, b) for (register int i(a); i <= b; ++i)
#define per(i, a, b) for (register int i(a); i >= b; --i)
#define FILE(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define mem(a, x) memset(a, x, sizeof a)
#define pb push_back
#define umap unordered_map
#define pqueue priority_queue
#define mp make_pair
#define PI acos(-1)
#define int long longusing namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dp[2005][2005], n, m;
char a[100005];
const int mod = 1e9+7;template <typename _T>
void rd(_T &x) {int f = 1; x = 0;char s = getchar();while (s > '9' || s < '0') {if (s == '-') f = -1; s = getchar();}while (s >= '0' && s <= '9') x = (x<<3)+(x<<1)+(s^48), s = getchar();x *= f;
}template <typename _T>
void write(_T x) {if (x < 0) putchar('-'), x = -x;if (x > 9) write(x/10);putchar(x%10+'0');return ;
}signed main() {rd(n), rd(m);scanf("%s", a+1);int pl = 0, pr = 0;rep(i, 1, m) {if (a[i] == '(') ++pl;else {if (pl == 0) ++pr;else --pl;}}dp[0][0] = 1;rep(i, 1, 2000) {rep(j, 0, 2000) {dp[i][j] += dp[i-1][j+1];dp[i][j] %= mod;if (j > 0) dp[i][j] += dp[i-1][j-1], dp[i][j] %= mod;}}int ans = 0;rep(i, 0, n-m) {for (register int j = 0; pr+j <= 2000 && pl+j <= 2000; ++j) {ans += dp[i][pr+j]*dp[n-m-i][pl+j]%mod;ans %= mod;}}printf("%lld", ans);return 0;
}