CODEFORCES 629 C Famil Door and Brackets

CODEFORCES 629 C Famil Door and Brackets

題意

給出 n,m(n≥m) $n, m(n ge m)$ 和一個長 m $m$ 的字符串 s$s$，字符串僅有 '(' 和 ')' 兩種字符組成。

現在讓你在 s $s$ 首尾分別加字符串 p,q$p,q$ （亦要僅有'(' 和 ')' 兩種字符，並且都可以是空串）。使得總串長度是 n $n$。並且滿足：1）總串的 '(' 和 ')' 兩種字符數目相同。2）總串的任意一個前綴都滿足 '(' 的數目大於等於 ')' 的數目。

請問加字符串的方案數是多少？答案取模 109+7$10^9 + 7$。

1≤n,m≤100000,n−m≤2000 $1 le n, m le 100000, n-m le 2000$

鏈接：

解答

如果 m=0 $m=0$，我們先考慮如何求。設 fi,j $f_{i,j}$ 表示前面 i $i$ 個字符有 j$j$ 個左括號的方案數。轉移並不難，這裡不細說了。结果是 fn,n2 $f_{n, frac{n}{2}}$。当然如果 n $n$ 是个奇数的话这个是没意义的，应该先特判。

考查中間的串，其實分別對 p,q$p,q$ 有限制。首先 p $p$ 要满足任意前缀都是左不少于右。但是我们还得考虑 p+s$p+s$ 的前缀（结尾在 s $s$ 的那些），这些前缀也要左不少于右应该要怎么满足呢？看来整个 p$p$ 左和右有可能不能正好相等，而是要左边多一些。那么最少多多少呢？那就要看中间的串的前缀左边比右边少多少。

int ritMore = 0;
int maxRitMore = 0;
for (int i = 0; i < m; ++i) {if (str.charAt(i) == ')')ritMore++;else ritMore--;maxRitMore = Math.max(maxRitMore, ritMore);
}

这个 maxRitMore 的值就是 p $p$ 左边比右边至少要多的数目。但是这样就可以了么？当然还不行，我们还没考察 p+s+q$p+s+q$ 的前缀（结尾在 q $q$ 中的部分）。要这些前缀左不少于右好似是不容易的，因为 q$q$ 是在变的。但是想到前綴的左括號多也就意味著剩下的部分右邊括號多，於是轉化為了對 q $q$ 限制是右邊括號要多一点（这个的求法就是前面的代码反过来来一次）。

最终我们可以先枚舉 p$p$ 的長度，再枚舉 p $p$ 中左括號有多少，利用前面的 f$f$ 得出結果。

long res = 0;
for (int p = 0; p <= k; p++) {int q = k - p;for (int plft = (maxRitMore + p - 1) / 2; plft <= p; ++plft) {int qlft = (n / 2) - plft - lftcnt;int qrit = q - qlft;if (qrit - qlft < maxLftMore || qlft < 0 || qrit < 0)continue;res = (res + c[p][plft] * c[q][qrit]) % MOD;}
}

其中的 k 等于 n−m $n-m$；plft 表示 p <script id="MathJax-Element-111" type="math/tex">p</script> 的做括号数。同理有剩下的命名。

这里是整个代码。