本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-03-03 11:50:20

前段时间模拟赛做到的题，是同学分享的做法，感觉妙，写个题解。

先不考虑 $k$ 的限制，通过容斥计算答案。设不考虑限制时答案为 $f_{n,m}$，则再钦定一部分盒子内放长为 $2k$ 的括号序列，容斥一下可以得到答案为 $\sum_{i=0}^{\min(n,\lfloor\frac mk\rfloor)} (-1)^i\times {n\choose i} \times C_k^i\times f_{n-i,m-ik}$，其中 $C_k^i$ 为卡特兰数第 $k$ 项的 $i$ 次方，表示所钦定盒子内的方案数。因此只需要实现多次求解 $f_{n,m}$ 即可。

考虑把 $n$ 个串塞到一个新串里，构造一个双射。方式是在新串开头预先放置 $(n-1)$ 个左括号，后面继续构造合法括号串，要求后面部分还要再加入 $m$ 个左括号。对新串做括号匹配，以与前 $(n-1)$ 个左括号匹配的 $(n-1)$ 个右括号为分界点，把后面分成 $n$ 部分，每一部分均为合法括号串且总长为 $2m$，感性理解可以证明构成双射。

所以 $f_{n,m}$ 等价于长为 $2(n+m-1)$ 且开头 $(n-1)$ 位均为左括号的合法括号串数量。考虑反射容斥求解，经典地把左括号看成 $1$，右括号看成 $-1$，并以下标和前缀和建立坐标系。则答案即为从 $(n-1,n-1)$ 走到 $(2n+2m-2,0)$，且全程不跨过 $x$ 轴的方案数。推一推式子发现无后一条限制时方案数为 ${n+2m-1}\choose m$，也即在后面部分的 $(n+2m-1)$ 个位上随便选 $m$ 个放左括号。

那么还要减去跨过 $x$ 轴的方案数。注意到这些方案都经过了 $y=-1$ 这条直线，考虑把这种方案第一次经过 $y=-1$ 之后的部分沿 $y=-1$ 对称，终点变为 $(2n+2m-2,-2)$，感性理解可以证明起点到新终点的路径与原来的不合法路径形成双射，所以推一推得到不合法方案数为 ${n+2m-1}\choose {m-1}$，因此也有 $f_{n,m}={{n+2m-1}\choose m}-{{n+2m-1}\choose {m-1}}$。

这样就做完了，预处理阶乘和逆元，时间复杂度线性，这是代码。