菜王的 blog

先考虑第一问的答案是什么。考虑对于一个长为 $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$。

• 若 $i > j$，则根据 $f_i < f_j$ 推出 $f_j$ 不能转移到 $f_i$，也就是 $p_j > p_i$，这样 $g_i$ 就能转移到 $g_j$，与 $g_i = g_j$ 这一条件矛盾。
• 那么有 $i < j$，则根据 $g_i = g_j$ 推出 $g_j$ 不能转移到 $g_i$，所以 $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)$ 构成双射：

• 两个杨表都包含了所有坐标形如 $(i, j)$ 的格子，满足 $(i, j)$ 为一个合法二元组，且这两个杨表中 $1 \sim n$ 恰好出现一次。
• 对于第一个杨表，有 $\lambda_{i, j} < \lambda_{i, j + 1}, \lambda_{i, j} < \lambda_{i + 1, j}$。
• 对于第二个杨表，有 $\mu_{i, j} < \mu_{i, j - 1}, \mu_{i, j} < \mu_{i + 1, j}$。

具体的，从 $(\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)$。