CF1750G Doping

我们称长度为 $n$ 的数组 $a$ 为“花式数组”，如果对于每个 $1 < i \le n$，都有 $a_i = a_{i-1} + 1$。 我们定义 $f(p)$ 作用于一个长度为 $n$ 的排列 $^\dagger$，表示将其划分为若干个子数组，每个子数组都是花式数组的最小划分数。例如 $f([1,2,3]) = 1$，$f([3,1,2]) = 2$，$f([3,2,1]) = 3$。 给定 $n$ 和一个长度为 $n$ 的排列 $p$，我们定义长度为 $n$ 的排列 $p'$ 是 $k$-特殊的，当且仅当： - $p'$ 字典序小于 $p$ $^\ddagger$，且 - $f(p') = k$。 你的任务是，对于每个 $1 \le k \le n$，计算 $k$-特殊排列的个数，对 $m$ 取模。 $^\dagger$ 排列是一个包含 $n$ 个 $1$ 到 $n$ 的不同整数的数组，顺序任意。例如 $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但有 $4$）。 $^\ddagger$ 长度为 $n$ 的排列 $a$ 的字典序小于排列 $b$，当且仅当：在第一个不同的位置，$a$ 的元素小于 $b$ 的对应元素。

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2000$，$10 \le m \le 10^9$）——排列的长度和取模的数。 第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$）——排列 $p$。

输出 $n$ 个整数，第 $k$ 个整数表示 $k$-特殊排列的个数，对 $m$ 取模。

在第一个样例中，字典序小于 $[1,3,4,2]$ 的排列有： - $[1,2,3,4]$，$f([1,2,3,4])=1$； - $[1,2,4,3]$，$f([1,2,4,3])=3$； - $[1,3,2,4]$，$f([1,3,2,4])=4$。 因此答案为 $[1,0,1,1]$。 在第二个样例中，字典序小于 $[3,2,1]$ 的排列有： - $[1,2,3]$，$f([1,2,3])=1$； - $[1,3,2]$，$f([1,3,2])=3$； - $[2,1,3]$，$f([2,1,3])=3$； - $[2,3,1]$，$f([2,3,1])=2$； - $[3,1,2]$，$f([3,1,2])=2$。 因此答案为 $[1,2,2]$。 由 ChatGPT 4.1 翻译