CF2018F1.Speedbreaker Counting (Easy Version)

DRG - Limbo

⠀

这是该问题的简单版本。在三个版本中，$n$ 的限制和时间限制不同。只有当你解决了所有版本的问题后，才能进行 hack。

以下是 D1B 问题的描述：

• 有 $n$ 个城市排成一行，从左到右编号为 $1, 2, \ldots, n$。

  • 在第 $1$ 时刻，你征服恰好一个城市，称为起始城市。
  • 在第 $2, 3, \ldots, n$ 时刻，你可以选择一个与已征服城市相邻的城市并征服它。

  如果对于每个 $i$，你在不晚于 $a_i$ 的时刻征服了城市 $i$，则你获胜。是否存在获胜策略，也取决于起始城市。问有多少个起始城市可以让你获胜？

对于每个 $0 \leq k \leq n$，统计有多少个正整数数组 $a_1, a_2, \ldots, a_n$ 满足：

• 对于每个 $1 \leq i \leq n$，$1 \leq a_i \leq n$；
• D1B 问题的答案为 $k$。

答案可能非常大，因此你需要对给定的质数 $p$ 取模后输出。

每组测试数据包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 80$）。接下来是每个测试用例的描述。

每个测试用例仅一行，包含两个整数 $n$ 和 $p$（$1 \le n \le 80$，$10^8 \leq p \leq 10^9$，$p$ 为质数），分别表示城市数量和模数。

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

对于每个测试用例，输出 $n+1$ 个整数，第 $i$ 个整数表示满足条件且 $k = i-1$ 的数组数量。

在第一个测试用例中：

• 有 $1$ 个好的起始城市的数组为：$[1]$。

在第二个测试用例中：

• 有 $0$ 个好的起始城市的数组为：$[1, 1]$；
• 有 $1$ 个好的起始城市的数组为：$[1, 2]$，$[2, 1]$；
• 有 $2$ 个好的起始城市的数组为：$[2, 2]$。

在第三个测试用例中：

• 有 $0$ 个好的起始城市的数组为：$[1, 1, 1]$，$[1, 1, 2]$，$[1, 1, 3]$，$[1, 2, 1]$，$[1, 2, 2]$，$[1, 3, 1]$，$[1, 3, 2]$，$[2, 1, 1]$，$[2, 1, 2]$，$[2, 2, 1]$，$[2, 2, 2]$，$[2, 3, 1]$，$[2, 3, 2]$，$[3, 1, 1]$；
• 有 $1$ 个好的起始城市的数组为：$[1, 2, 3]$，$[1, 3, 3]$，$[2, 1, 3]$，$[3, 1, 2]$，$[3, 1, 3]$，$[3, 2, 1]$，$[3, 3, 1]$；
• 有 $2$ 个好的起始城市的数组为：$[2, 2, 3]$，$[2, 3, 3]$，$[3, 2, 2]$，$[3, 3, 2]$；
• 有 $3$ 个好的起始城市的数组为：$[3, 2, 3]$，$[3, 3, 3]$。

由 ChatGPT 4.1 翻译