AT_jsc2025_final_c.Prefix Bounding Box, Mod, Minimize

给定正整数 $N, M$ 和素数 $P$，以及 $Y = (Y_1, Y_2, \dots, Y_N)$，它是 $1$ 到 $N$ 的一个全排列。

对于 $1$ 到 $N$ 的一个全排列 $X = (X_1, X_2, \dots, X_N)$，定义函数 $f(X)$ 如下：

• 对于所有 $2 \leq k \leq N$ 的整数，定义 $B_k$ 为以下值：
  • 对于集合 $S=\{(X_1,Y_1),(X_2,Y_2),\dots,(X_k,Y_k)\}$，在二维平面上画出这些点，取覆盖 $S$ 的、边与 $x$ 轴平行的最小面积的矩形，即集合 $S$ 的最小“包围盒”，记这个矩形面积模 $M$ 的余数为 $B_k$。
• $f(X) = \max(B_2, B_3, \dots, B_N)$

请你计算满足 $f(X)$ 最小的 $X$ 的个数，并对 $P$ 取模。

现在有 $T$ 组测试数据，请分别作答。

“包围盒”是指：对于给定点集 $S$，找一个边与坐标轴平行的最小矩形，恰好包含 $S$ 的所有点，且面积最小。

输入通过标准输入给出，格式如下：

$T$
每组测试包含：$N$ $M$ $P$
$Y_1$ $Y_2$ … $Y_N$

输出 $T$ 行。

第 $i$ 行输出第 $i$ 个测试用例，$f(X)$ 取得最小值的 $X$ 的个数，对 $P$ 取余。

样例解释 1

对于第 $1$ 组测试，例如 $X = (3,1,4,2)$ 时，$(B_2, B_3, B_4) = (2, 0, 3)$，因此 $f(X) = 3$。$f(X)$ 的最小值是 $3$，满足 $f(X) = 3$ 的 $X$ 有 $12$ 个。

对于第 $2$ 组测试，对于所有 $X$，都有 $f(X) = 0$，因此答案为 $13!$ 对 $P=10007$ 取余。

数据范围

• $1 \leq T \leq 100$
• $2 \leq N \leq 3000$
• $1 \leq M \leq 10^7$
• $10^4 \leq P \leq 10^9$
• $P$ 是素数
• $Y$ 是 $1$ 到 $N$ 的全排列
• 所有测试用例中 $N$ 的总和不超过 $3000$
• 输入均为整数

由 ChatGPT 5 翻译