组合数学计数.
求有多少个长度为 $n$ 的括号序列,满足其最长合法括号子序列长度恰好为 $k$ ,答案对 $10^9+7$ 取模.
$2\le k\le n\le 2\times 10^5$ ,数据组数 $T\le 2\times 10^5$ .
先考虑对于一个给定的括号序列,如何计算其最长合法括号子序列长度.
把左括号权值设为 $1$ ,右括号权值设为 $-1$ ,记 $s$ 表示这个序列权值的前缀和,则最长合法长度为 $n-s_n+2\min s_i$ .
简要证明,考虑 $\min s_i$ 对应的位置 $x$ ,之前有 $-s_x$ 个右括号无法匹配,剩下括号都能互相匹配,否则有更小的 $s_i$ .
同理, $x$ 之后有 $s_n-s_x$ 个左括号无法匹配,剩下都能互相匹配,用 $n$ 将两部分不合法的减掉,剩下的就是答案.
再考虑如何统计最长合法长度恰好为 $k$ 的序列长度,我们枚举左右括号分别有多少个, $s_n$ 和 $\min s_i$ 就都确定了.
于是记 $t=\frac{k-n+s_n}{2}$ ,只需要统计 $\min s_i=t$ 的方案数,可以用 $\min s_i\ge t$ 的方案数减掉 $\min s_i\ge t+1$ 的方案数.
限制了 $\min s_i\ge t$ ,相当于从 $(0,0)$ 走到 $(\frac{n-s_n}{2},\frac{n+s_n}{2})$ ,每次向上或向右一步,且不越过直线 $y=x+t$ 的方案数.
这可以容斥成两个组合数,即 $\binom n {(n+s_n)/2}-\binom{n}{n-t+1}$ ,再减掉 $\min s_i \ge t+1$ 的方案数 $\binom n {(n+s_n)/2}-\binom{n}{n-t}$ .
简单整理可以得到贡献为 $\binom{n}{ k /2}-\binom{n}{ k /2 -1}$ ,与我们枚举的 $s_n$ 无关,那么答案就是 $(n-k+1)\cdot (\binom{n}{ k/ 2}-\binom{n}{ k/ 2 -1})$ .