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 翻译