CF2262E Paired Bracket Sequences

Farmer John 对具有公共配对的括号序列感兴趣。 一个平衡括号序列是指每一个左括号都能和后面的某个右括号配对，且任意前缀中，左括号的数量都不少于右括号。 对于一个平衡括号序列 $s$，一次配对是指一对下标 $(i, j)$，满足 $i < j$，且 $s_i$ 是左括号，$s_j$ 是右括号，并且 $s_{i+1} \ldots s_{j-1}$（即 $s_i$ 和 $s_j$ 之间的子串）本身也是一个平衡序列。 考虑一个有序对 $(s, t)$，其中 $s$ 和 $t$ 都是长度为 $2n$ 的平衡括号序列。若某一配对 $(i, j)$ 同时是 $s$ 和 $t$ 的配对，则称其是 $s$ 和 $t$ 的“公共配对”。例如，括号序列 $\texttt{(()())}$ 和 $\texttt{((()))}$ 有一个公共配对，即最外层配对 $(1,6)$。 两个有序对 $(s, t)$ 和 $(s', t')$ 是不同的，只要 $s \ne s'$ 或 $t \ne t'$。 对于每个 $0 \le k \le n$，Farmer John 想知道长度为 $2n$ 的平衡括号序列的有序对 $(s, t)$ 中，恰好有 $k$ 个公共配对的有序对的数量。由于结果可能很大，你需要将答案对 $M$ 取模输出。

每个测试点包含多个测试用例。第一行为测试用例数量 $t$（$1 \le t \le 500$）。每个测试用例包含一行，包含两个整数 $n$ 和 $M$（$1 \leq n \leq 500$，$10^8 \leq M \leq 10^9$），分别表示括号序列长度的一半和输出时对 $M$ 取模。保证 $M$ 是质数。 保证所有测试用例中 $n$ 的总和不超过 $500$。

对于每个测试用例，输出 $n+1$ 个整数，依次表示对每个 $0 \leq k \leq n$，有恰好 $k$ 个公共配对的有序对数量，对 $M$ 取模后的结果。

对于第一个测试用例，$n=1$ 时只有一种平衡括号序列：$\texttt{()}$。它只有一个配对 $(1,2)$。因此，唯一的有序对括号序列恰好有一个公共配对，所以答案为 $[0,1]$。 对于第二个测试用例，$n=2$ 时平衡括号序列有两种：$a=\texttt{(())}$ 和 $b=\texttt{()()}$。$a$ 的配对有 $(1,4)$ 和 $(2,3)$，$b$ 的配对有 $(1,2)$ 和 $(3,4)$。 因此，有序对 $(a, b)$ 和 $(b, a)$ 共有 $0$ 个配对；有序对 $(a, a)$ 和 $(b, b)$ 共有 $2$ 个配对。因此答案为 $[2,0,2]$。 由 ChatGPT 5 翻译