CF2262E.Paired Bracket Sequences

Farmer John is interested in bracket sequences with common pairings.

A balanced bracket sequence is one in which every opening bracket is matched with a later closing bracket, and no prefix contains more closing brackets than opening brackets.

For a balanced bracket sequence $s$, a pairing is a pair of positions $(i,j)$ with $i \lt j$ such that $s_i$ is an opening bracket, $s_j$ is a closing bracket, and the substring strictly between them is balanced.

Consider an ordered pair $(s,t)$ of balanced bracket sequences, where both $s$ and $t$ have length $2n$. A pairing $(i,j)$ is common to $s$ and $t$ if $(i,j)$ is a pairing in both sequences. For example, the bracket sequences $\texttt{(()())}$ and $\texttt{((()))}$ have one common pairing, namely the outer pair $(1,6)$.

Two ordered pairs $(s,t)$ and $(s',t')$ are considered different if $s \ne s'$ or $t \ne t'$.

For each $0 \le k \le n$, Farmer John wants to know the number of ordered pairs $(s,t)$ of balanced bracket sequences of length $2n$ with exactly $k$ common pairings. Since these numbers may be large, output them modulo $M$.

农夫约翰对具有公共配对的括号序列很感兴趣。

一个平衡括号序列是指：每个左括号都与一个在其之后出现的右括号匹配，且该序列的任意前缀中右括号的数量都不超过左括号的数量。

对于一个平衡括号序列 $s$，一个配对是指一对位置 $(i,j)$，满足 $i \lt j$，其中 $s_i$ 是左括号，$s_j$ 是右括号，且 $s$ 中严格位于 $i$ 与 $j$ 之间的子串也是平衡括号序列。

考虑一对有序的平衡括号序列 $(s,t)$，其中 $s$ 和 $t$ 的长度均为 $2n$。若配对 $(i,j)$ 同时是 $s$ 和 $t$ 的配对，则称该配对为 $s$ 与 $t$ 的公共配对。例如，括号序列 $\texttt{(()())}$ 和 $\texttt{((()))}$ 恰好有一个公共配对，即最外层配对 $(1,6)$。

若 $s \ne s'$ 或 $t \ne t'$，则认为两对有序对 $(s,t)$ 与 $(s',t')$ 是不同的。

对每个 $0 \le k \le n$，农夫约翰想知道：长度为 $2n$ 的平衡括号序列的有序对 $(s,t)$ 中，恰好有 $k$ 个公共配对的个数。由于这些数值可能很大，请将结果对 $M$ 取模后输出。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each testcase will contain two integers, $n$ and $M$ ($1 \leq n \leq 500$, $10^8 \leq M \leq 10^9$) — half the length of the bracket sequence and the modulo to output the answer in. It is guaranteed that $M$ is prime.

It is guaranteed that the sum of $n$ over all test cases does not exceed $500$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $M$（$1 \leq n \leq 500$，$10^8 \leq M \leq 10^9$）——分别表示括号序列长度的一半，以及输出答案时所取模的模数。保证 $M$ 是质数。

保证所有测试用例中 $n$ 的总和不超过 $500$。

For each testcase, output $n + 1$ integers, the answer modulo $M$ for each $0 \leq k \leq n$.

对于每个测试用例，输出 $n + 1$ 个整数，即对每个 $0 \leq k \leq n$，输出答案对 $M$ 取模的结果。

For the first test case, there is only one balanced bracket sequence with $n=1$: $\texttt{()}$. It has exactly one pairing, namely $(1,2)$. Therefore, the only ordered pair of bracket sequences has exactly one common pairing, so the answer is $[0,1]$.

For the second test case, there are exactly two balanced bracket sequences with $n=2$: $a=\texttt{(())}$ and $b=\texttt{()()}$. The pairings of $a$ are $(1,4)$ and $(2,3)$, while the pairings of $b$ are $(1,2)$ and $(3,4)$.

Thus, the ordered pairs $(a,b)$ and $(b,a)$ have $0$ common pairings, while the ordered pairs $(a,a)$ and $(b,b)$ have $2$ common pairings. Therefore, the answer is $[2,0,2]$.

对于第一个测试用例，仅存在一个长度为 $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]$。