先不考虑 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 个放左括号。