题解

思路

令 $F(n,m,k)$ 表示最长合法括号子序列至多含 $k$ 对括号的序列数。答案为 $F(n,m,k)-F(n,m,k-1)$。

子任务 1

枚举长度 $n+m$ 的所有二进制串，只保留左括号数为 $n$ 的序列。扫描序列并贪心匹配括号即可得到最长合法括号子序列。复杂度为 $O(2^{n+m}(n+m))$。

子任务 2

当 $k\ge\min(n,m)$ 时所有排列都合法，$F(n,m,k)=\binom{n+m}{m}$。否则按首字符分类：首字符为右括号时得到 $F(n,m-1,k)$；首字符为左括号时它必能贡献一对匹配，得到 $F(n-1,m,k-1)$。因此

记忆化递归即可。

子任务 3

上述递推与 Pascal 恒等式相同，可以归纳得到

因此当 $k\le\min(n,m)$ 时答案为

否则为零。预处理到 $4000$ 的阶乘和逆阶乘后每组 $O(1)$。

做法

预处理阶乘与逆阶乘。逐组检查 $k>\min(n,m)$，若成立输出零；否则计算两个组合数之差并调整到模数范围。

正确性证明

递推按第一个字符划分了全部序列且两类不交。边界 $k\ge\min(n,m)$ 时最长子序列不可能超过较少的括号数，故所有排列都满足。由相同边界和相同 Pascal 递推，$F(n,m,k)=\binom{n+m}{k}$。相邻“至多”计数之差恰好留下最长子序列为 $k$ 对的序列，因此公式正确。

复杂度

满分算法预处理 $O(4000)$，每组 $O(1)$，空间 $O(4000)$；中档最坏 $O(nmk)$；小档为指数复杂度。