CF2018F3 Speedbreaker Counting (Hard Version)

[DRG - Limbo](https://soundcloud.com/drg72711/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 翻译