CF2018F3.Speedbreaker Counting (Hard 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 3000 $）。接下来是每组测试用例的描述。

每组测试用例的唯一一行包含两个整数 $ n, p $（$ 1 \le n \le 3000 $，$ 10^8 \leq p \leq 10^9 $，$ p $ 为质数），表示城市数量和取模的质数。

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

对于每组测试用例，输出 $ 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 翻译