[PA 2025] 光滑排列 题解

· · 题解

可能更好的阅读体验

基本是官方题解的翻译……

先考虑第一问的答案是什么。考虑对于一个长为 n 的排列，我们对于每个位置 i 求出 f_i 表示以 i 结尾的 LIS 长度，g_i 为以 i 开头的 LDS 长度。那么我们可以定义一个二元组序列 a，其中 a_i = (f_i, g_i)。

显然 a 序列中的元素互不相同，假设有一对 (i, j) 满足 1 \le i < j \le n，那么 p_i > p_j 能推出 g_i > g_j，否则能推出 f_i < f_j。并且根据题目限制，显然有二元组 (x, y) 合法当且仅当 x \le A, y \le B, x + y - 1 \le C，a 序列中所有元素都应当合法。

那么我们得到了一个 n 的上界 AB - \binom{A + B - C}2，我们不妨猜测 n 一定能取到它。后面的过程中将会证明这一点。

考虑任意一个合法二元组 (x, y)，如果有 x > 1，那么 (x - 1, y) 在 a 中的位置 i 一定在 (x, y) 在 a 中的位置 j 之前，且满足 p_i < p_j。

同理，如果有 y > 1，那么 (x, y - 1) 在 a 中的位置 i 一定在 (x, y) 在 a 的位置 j 之后，且满足 p_i < p_j。

可以发现上述条件是长为 n 的排列 p 合法的充要条件，那么这个排列 p 与两个相同形状的 n 格杨表组成的杨表对 (\lambda, \mu) 构成双射：

具体的，从 (\lambda, \mu) 到长为 n 的合法排列 p，使 p_{\mu_{i, j}} = \lambda_{i, j} 即可；从长为 n 的合法排列 p 到 (\lambda, \mu)，求出文章一开始的 f, g，使 \lambda_{f_i, g_i} = p_i, \mu_{f_i, g_i} = i 即可。

显然，这样的杨表对一定存在，那么 n 也一定能够取到上界。\lambda 是标准杨表，它的个数可以用勾长公式直接 O(n + A^2) 求出，但是 \mu 不是，所以需要另外想办法计数。我们不直接求出 \mu 的方案数，而是转而求出等概率随机一个排列填入 \mu 使得其合法的概率 P，最后乘上 n! 即可。

考虑另一个杨表 \mu'，其中每个数都是 [1, x] 中的整数，且其满足 \mu'_{i, j} \textcolor{red}{\le} \mu'_{i, j - 1}, \mu'_{i, j} < \mu'_{i + 1, j}。设 \mu'_{i, j} 的每个位置都在 [1, x] 中等概率随机时，\mu' 合法的概率为 P'(x)，那么有 P = \lim_{x \to \infty} P'(x)，因为 x \to \infty 时，\mu' 中存在相等的两个数的概率为零。

考虑如何计算 P'(x)。令满足 i + j = C + 1 的格子所填的数对 i 从小到大分别为 s_1, s_2, \dots, s_{A + B - C}，那么我们固定 s 之后就能将合法的 \mu' 与平面上起终点分别为 (S_1, T_1), (S_2, T_2), \dots, (S_A, T_A) 的 A 条只往右或下走的不交路径组构成双射，具体的，有：

S_i = (i, x - A + i)\\ T_i = \begin{cases} (B + i, i) & i \le C - B\\ (C, s_{i - C + B}) & i > C - B\\ \end{cases}

那么根据 LGV 引理，有：

P'(x) = \frac{\sum_{1 \le s_1 < s_2 < \cdots < s_{A + B - C} \le x}|M|}{x^n}\\ P = \lim_{x \to \infty} \frac{\sum_{1 \le s_1 < s_2 < \cdots < s_{A + B - C} \le x}|M|}{x^n}\\ M_{i, j} = \begin{cases} \binom{x - A + B}{B + j - i} & j \le C - B\\ \binom{x - s_{j - C + B} + C - A}{C - i} & j > C - B\\ \end{cases}

由于我们求的是极值，而分子部分显然是一个多项式，那我们只需要保留最高次项的系数即可：

M_{i, j} = \begin{cases} \frac{x^{B + j - i}}{(B + j - i)!} & j \le C - B\\ \frac{(x - s_{j - C + B})^{C - i}}{(C - i)!} & j > C - B\\ \end{cases}

观察这个矩阵可以发现它的行列式展开后每一项的次数都是相同的，且恰好是 n - A - B + C 次，那么我们可以上下约掉这么多个 x：

P = \lim_{x \to \infty} \frac{\sum_{1 \le s_1 < s_2 < \cdots < s_{A + B - C} \le x}|M|}{x^{A + B - C}}\\ M_{i, j} = \begin{cases} \frac{1}{(B + j - i)!} & j \le C - B\\ \frac{(1 - \frac{s_{j - C + B}}x)^{C - i}}{(C - i)!} & j > C - B\\ \end{cases}

最后，由于 x \to \infty，所以我们将求和换成积分，将剩余的 x 全都约掉：

P = \int_0^1 \int_{s_1}^1 \cdots \int_{s_{A + B - C - 1}}^1 |M| ds_{A + B - C} \cdots ds_2 ds_1\\ M_{i, j} = \begin{cases} \frac{1}{(B + j - i)!} & j \le C - B\\ \frac{(1 - s_{j - C + B})^{C - i}}{(C - i)!} & j > C - B\\ \end{cases}

把 s 序列反转，值域翻转：

P = \int_0^1 \int_0^{s_1} \cdots \int_0^{s_{A + B - C - 1}} |M| ds_{A + B - C} \cdots ds_2 ds_1\\ M_{i, j} = \begin{cases} \frac{1}{(B + j - i)!} & j \le C - B\\ \frac{{s_{j - C + B}}^{C - i}}{(C - i)!} & j > C - B\\ \end{cases}

暴力展开每一项并计算积分的时间复杂度是 O(n + A \times A!) 的。事实上，可以通过归纳法证明：

\int_0^1 \int_0^{x_1} \cdots \int_0^{x_{n-1}} x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n} \, dx_n \cdots dx_1 = \prod_{k=1}^n \frac{1}{\sum_{i=k}^n (a_i + 1)}

那么我们对于矩阵 M，按列从右往左扫来状压 DP，设 f_S 表示已经选完了后 |S| 列，并选了 S 中的行的系数之和，每次转移时 \sum (a_i + 1) 就是已知的。那么我们可以用 O(n + A2^A) 的时间复杂度算出 \mu 的方案数，将其与 \lambda 的方案数乘起来即可。总时间复杂度为 O(n + A^2 + A2^A)。