P11929 [PA 2025] 光滑排列 / Gładkie permutacj

PA 2025 R5A.

对于序列 $a=[a_1,a_2,\ldots,a_k]$，我们说： - $a$ 是递增的，当且仅当 $a_1\lt a_2\lt \ldots\lt a_k$； - $a$ 是递减的，当且仅当 $a_1\gt a_2\gt \ldots\gt a_k$； - $a$ 是**单峰的**，当且仅当存在 $1\le l\le k$，使得 $[a_1,a_2,\ldots,a_l]$ 是递增的，且 $[a_l,a_{l+1},\ldots,a_k]$ 是递减的。 特别地，若 $k=1$，则 $a$ 既是递增的，也是递减的，也是单峰的。 对于正整数 $a,b,c$，我们说一个排列 $p$ 是好的，当且仅当： - $p$ 的最长上升子序列（LIS）长度为 $a$； - $p$ 的最长下降子序列（LDS）长度为 $b$； - $p$ 的最长单峰子序列长度为 $c$。 > **例** > > $a=2,b=3,c=4$ 时，排列 $[4, 5, 2, 3, 1]$ 是好的，因为： > - LIS 为 $[4, 5]$（长度 $2$）； > - LDS为 $[4, 2, 1]$（长度 $3$）； > - 最长单峰子序列为 $[4, 5, 3, 1]$（长度 $4$）。 给定 $a,b,c$ 满足 $1\le a\le b\le c\lt a+b$。求出： 1. 好的排列 $p$ 的长度的最大值（记为 $n$）； 2. **长度为 $n$ 的**好的排列的数量对大素数 $\mathrm{mod}$ 取模后的结果。 可以证明，在题目条件下，好的排列至少有一个，且只有有限个。

一行四个正整数 $a,b,c,\mathrm{mod}$。

一行两个正整数： - 最长的好的排列的长度 $n$； - 长度为 $n$ 的好的排列的数量对 $\mathrm{mod}$ 取模后的结果。

### 样例解释 - 样例 $1$ 解释： 样例 $1$ 中，$a=2,b=2,c=3$。 所有好的排列为： - $[1, 3, 2]$； - $[2, 3, 1]$； - $[2, 1, 4, 3]$； - $[2, 4, 1, 3]$； - $[3, 1, 4, 2]$； - $[3, 4, 1, 2]$。 其中最长的排列长度为 $4$。 - 样例 $2$ 解释： 样例 $2$ 中，$a=2,b=3,c=3$。 所有好的排列为： - $[3, 2, 1, 5, 4]$； - $[3, 2, 5, 1, 4]$； - $[4, 2, 1, 5, 3]$； - $[4, 2, 5, 1, 3]$； - $[4, 3, 1, 5, 2]$； - $[4, 3, 5, 1, 2]$； - $[5, 2, 1, 4, 3]$； - $[5, 2, 4, 1, 3]$； - $[5, 3, 1, 4, 2]$； - $[5, 3, 4, 1, 2]$。 ### 子任务 在大于 $0$ 分的子任务中，保证 $c = a + b - 1$。 ### 数据范围 - $1 \leq a \leq 20$； - $ a \leq b \leq 5\times 10^4$； - $b \leq c \lt a + b$； - $10^7 \leq \mathrm{mod} \leq 10^9$； - $\mathrm{mod}$ 是素数。