杨表简介

· · 算法·理论

杨表和 LIS、LDS、排列与序列等有紧密关系。

定义

设 x=(x_1,\dots,x_m) 是 n 的一个划分。x_1\ge x_2\ge\cdots\ge x_m。

定义 1（杨图）：一个 m 行的表格，第 i 行有 x_i 列（左对齐）。

定义 2（杨表）：将 1\sim n 填入杨图，满足每一行和每一列严格递增。

定义 3（半杨表）：将 n 个正整数填入杨图，满足每一行不严格递增，每一列严格递增。

定义 4（行插入）：设当前有一个杨表，一个行插入操作有一个参数 x。找到第一行第一个 >x 的数 x'，用 x 替换 x'；然后找到第二行第一个 >x' 的数 x''，用 x' 替换 x'' …… 循环往复，直到把一个数插入新的一行（空行）或者这一行不存在更大的数（放在末尾）。

容易发现杨表插入后还是杨表。

定义 5（列插入）：与行插入类似。

定义 6（行删除）：可以看作是行插入的还原操作。取最后一行的数 x，找到上一行最后一个 <x 的数 x' ……

定义 7（列删除）：与行删除类似。

定义 8（勾长）：记 h(i) 为格子 i 的勾长。h(i)= i 下方格子数 + 右方格子数 + 1。

Hook Formula：假设有一个杨图 x，c(x)=\dfrac{n!}{\prod_i h(i)}，i 是 x 里的格子。

RSK Correspondence

设当前有一个排列 \pi=(\pi_1,\dots,\pi_n)，按顺序把 \pi 行插入一个初始为空的杨表。得到的杨表记作 P_{\pi}。

另外构造一个杨表 Q_{\pi}，在 \pi_i 插入时新增的格子里填 i。

把 P_{\pi} 叫做正表，Q_{\pi} 叫做副表。容易发现 P_{\pi},Q_{\pi} 是形态相同的杨表。

定理：排列 \pi 与杨表对 (P_{\pi},Q_{\pi}) 构成一一对应。

证明：因为有删除操作，从 \pi 构建 P_{\pi},Q_{\pi} 的过程是可逆的。

推论：n!=\sum_{x}c(x)^2，x 为 n 的一个划分（对应了一个杨图的形态），c(x) 为形态为 x 的杨表个数。

证明：排列与杨表对一一对应，枚举杨图然后枚举 P,Q 的填法。

定理：不严格递增的坐标序列与半杨表对一一对应。 （这里比较坐标的大小是按字典序比较）

证明：设坐标序列为 (u_1,v_1),(u_2,v_2),\dots,(u_k,v_k)，把 v_1\sim v_k 插入一个表，得到半杨表 P_x；Q_x 定义为在每次新增加的格子里填 u_i。

性质

性质 1：若 \pi 对应 (P_{\pi},Q_{\pi})，则 \pi^{-1} 对应 (Q_{\pi},P_{\pi})。（拓展：如果一个递增坐标序列 x 对应半杨表对 (P_x,Q_x)，交换 x_i 的两维后对应半杨表对 (Q_x,P_x)）

证明：直接证明拓展版本，也就是普通序列和半杨表。这显然拓展版本强于原命题。

先来几个定义。

考虑一个不严格递增坐标序列 x 对应到一个 2\times n 的矩阵 A：A[1][i]=x_i 的第一维，A[2][i]=x_i 的第二维。

同时考虑一个不严格递增坐标序列 x 对应到一个 V\times V 的方阵 M：M[i][j]= 两维分别等于 i,j 的 x_k 个数。

显然序列、矩阵、方阵是一一对应的。

如果 x 对应方阵 M，定义 P_M=P_x。

开始正式证明。

观察到若 x 对应了 A，则 x^{-1} 对应 A^{T}。 因此可以转化命题为：P_{M^T}=Q_M,Q_{M^T}=P_M。

简单起见，假设没有重复元素（坐标互不相等），此时 A 是 0/1 方阵。

考虑 P_A,Q_A 的第一行。玩一个例子：(1,3)(1,4)(2,3)(3,1)(3,4)(4,2)。

发现每一列上曾经存在过的数，构成一个递减序列。进一步观察，每一列都是从剩下没选的元素里贪心取 LDS 的结果，也就是贪心地把序列划分成若干个下降序列。

在方阵里看，这样的划分实际上是从一个 1 出发，向右上方贪心找链。定义极值点为方阵里左上方没有 1 的点，那么第一条链是所有极值点、第二条链是剩下点里的极值点 ……

观察到 P_M 的第一行（设 t 列）就是每条链的链尾列号。而 Q_M 的第一行呢？显然也是 t 列，而且观察发现是链头的行号。

然后考虑之后的行。在填了第一行之后有一些数被挤下去了，而这些挤下去的数是什么样子？

设一条链为 (u_{i_1},v_{i_1})\cdots(u_{i_k},v_{i_k})，观察到在 P 中会留下 v_{i_k}，在 Q 中会留下 u_{i_1}，然后 (u_{i_2},v_{i_1})\cdots(u_{i_k},v_{i_{k-1}}) 下传到第二行。 我们设第一行的点构成的方阵为 M，下传到第二行的点构成的方阵为 N。

有了这些观察就可以证明性质 1 了。

正式证明里的正式证明。

$Q_M$ 第一行 $=M$ 各链的链头行号 $=M^T$ 各链的链尾列号 $=P_{M^T}$ 第一行。 巨大进步！我们已经证明了第一行是相等的。 一个强烈的想法是用归纳法。那我们就用归纳法。 把 $P_M$ 的第一行去掉，会得到 $P_N$（根据定义）。 把 $Q_M$ 的第一行去掉，会得到 $Q_N$（根据定义）。 根据上面两条，有：$Q_{M^T}$ 的第一行去掉，会得到 $Q_{N^T}$。 根据归纳假设，$P_N=Q_{N^T}$，而 $P_N$ 是 $P_M$ 去掉第一行，$Q_{N^T}$ 是 $Q_{M^T}$ 去掉第一行。所以 $P_M$ 和 $Q_{M^T}$ 去掉第一行之后是一样的，而上面又证明了它俩的第一行是一样的，所以 $P_M=Q_{M^T}$。 对于 $Q_M=P_{M^T}$，证明类似，在此略去。 上面的证明和元素是否相等关系不大，套用证明的流程可以把有相等的情况证了。 **性质 1 推论 1**：因为 $P_M=Q_{M^T}$，所以如果 $M$ 是对称方阵，$P_M=Q_M$。也就是每一个对称矩阵对应**一个**半杨表。 **性质 1 推论 2**：一个对称矩阵对应一个半杨表，那什么对应一个杨表呢？类似有 $\pi=\pi^{-1}$ 的结论。这种排列叫做**对合排列（involution）**，满足 $\pi_i=j\iff \pi_j=i$（$i=j$ 允许）。 **推论 2 应用**：可以求杨表个数。大小 $n$ 的杨表个数就是 $n$ 长度的对合排列个数。 法一：这个个数就是 $1\sim n$ 匹配的个数（不要求完美匹配）。记个数 $a_n$，有 $a_n=a_{n-1}+(n-1)a_{n-1}$，前一种是 $1$ 不参与匹配，后一种是 $1$ 选一个匹配。这样可以 $O(n)$ 求杨表个数。 法二：这个个数就是由若干各环组成，每个环大小为 $1/2$ 的图个数。可以用母函数：它的母函数是 $e^{z+\frac{z^2}{2}}$。 ----- **性质 2**：若 $\pi$ 对应 $(P_{\pi},Q_{\pi})$，$\pi^{R}=(\pi_n,\dots,\pi_1)$ 的主表为 $P_{\pi}^T$。 **证明**： 记杨表 $S$ 行插入 $x$ 的结果为 $S\leftarrow x$，列插入 $x$ 的结果为 $x\rightarrow S$。 **引理**：$y\rightarrow(S\leftarrow x)=(y\rightarrow S)\leftarrow x$。（分类讨论可证，具体过程暂略） 记 $S(x_1,\dots,x_n)=((x_1\leftarrow x_2)\leftarrow \cdots )\leftarrow x_n$，$S'(x_1,\cdots,x_n)=x_1\rightarrow (x_2\rightarrow \cdots(x_{n-1}\rightarrow x_n))$。 根据归纳法易证 $S(x_1,\dots,x_n)=S'(x_1,\dots,x_n)$。 而 $P_{\pi}=S(\pi_1,\dots,\pi_n)=S'(x_1,\dots,x_n)=(((x_n\leftarrow x_{n-1})\leftarrow\cdots)\leftarrow x_1)^T=P_{\pi^{R}}^{T}$。 ----- **性质 3**：$P_\pi$ 列数 $=|LIS(\pi)|$，$P_{\pi}$ 行数 $=|LDS(\pi)|$。 证明： 1. 对于列数。 考虑这么一个 LIS 的贪心算法：从前往后扫，维护一个小根堆的序列。若当前数比当前末尾的堆顶大，新开一个堆；否则放入堆中。堆的个数就是 LIS 长度。容易发现这其实模拟了构造杨表的过程。 2. 对于行数。 $|LDS(\pi)|=|LIS(\pi^{R})|=P_{\pi^{R}}\text{宽度}=P_{\pi}^{T}\text{宽度}=P_{\pi}\text{高度}$. ----- **性质 3 推论**：在 $\pi$ 中找 $k$ 个不相交的 LIS，最长总长 $=P_{\pi}\text{前 k 行总长}$；找 $k$ 个不相交的 LDS，最长总长 $=P_{\pi}\text{前 k 列总长}$。 证明太难，略。 ## 快速求杨表 可以在 $O(n\sqrt n\log n)$ 的复杂度内，根据一个排列 $\pi$ 求出 $(P_{\pi},Q_{\pi})$。 我们只需要考虑 $P_{\pi}$ 即可，因为根据性质 1，$Q_{\pi}=P_{\pi^{-1}}$，用 $\pi^{-1}$ 求一次 $P$ 即可。 怎么求 $P_{\pi}$？ 令 $B=\lceil\sqrt n\rceil$，则求这个杨表等价于求前 $B$ 行和前 $B$ 列。因为 $P_{\pi}$ 不可能填到行列都 $>B$ 的位置，否则 $|P_{\pi}|>n$。 我们只需要知道求前 $B$ 行的方法，因为前 $B$ 列等于 $P_{\pi}^T$ 的前 $B$ 行，根据性质 2 等于 $P_{\pi^{R}}$ 的前 $B$ 行。同样的方法再做一遍即可。 怎么求 $P_{\pi}$ 的前 $B$ 行？ 直接暴力行插入，如果到达 $>B$ 的行就直接退出。一次插入是 $O(\sqrt n\cdot \log n)$。（一共 $B$ 行，每行内部二分）一共插入 $n$ 次，复杂度 $O(n\sqrt n\log n)$。 # 题目应用 ## Gym 102538D 题意：计数排列，满足有两个不相交的 LIS。$n\le 75$。 这样的排列对应的杨表形态就是第一、二行长度相等。因此枚举 $n$ 的拆分 $\lambda$ 使得 $\lambda_1=\lambda_2$。 ## LIS 3（无题号） 题意：计数排列，满足 LDS 长度 $\le 3$。$n\le 50$。 即杨表的高度 $\le 3$，枚举 $\lambda=(\lambda_1,\lambda_2,\lambda_3)$ 求和 $c(\lambda)$ 即可。 另解：$dp[i][j][k]$ 为前 $i$ 个数，$1$ 长度 LDS 结尾最大为 $j$，$2$ 长度 LDS 结尾最大为 $k$。 ## [P4484](https://www.luogu.com.cn/problem/P4484) 题意：随机排列，求 LIS 期望长度。$n\le 28$。 即 $(\sum_{\lambda} c(\lambda)^2\cdot \lambda_1)/n!$。 注：本题推论得到随机 LIS 的长度是 $O(\sqrt n)$ 的。 ## [P3774](https://www.luogu.com.cn/problem/P3774)（偏门结论） 题意： 给定一个序列 $B=(b_1\sim b_n)$ 和 $q$ 次询问。每次询问给定两个参数 $m,k$，求 $b_1\sim b_m$ 的最长 k-LIS 子序列长度。 一个序列是 k-LIS 的，当且仅当其 LIS 长度 $\le k$。 $b_i\le 5e4$，$q\le 2e5$，$k\le m\le n\le 5e4$。 首先去除 $B$ 里的重复数字，例如对于 $2,2,2$，可以改成 $2.2,2.1,2.0$，这是等价的。所以下面可以假设 $B$ 是个排列。 然后考虑一个询问 $(m,k)$ 是问什么。这其实是问 $b_1\sim b_m$ 杨表的前 $k$ 列长度之和。（性质 3 推论） 容易想到把询问离线，然后按 $m$ 从小到大排序后处理。 为了确定 $b_1\sim b_m$ 的杨表形态，只需确定其前 $\sqrt n$ 行和前 $\sqrt n$ 列。前 $\sqrt n$ 行是容易的，只需要每次 $O(\sqrt n\log n)$ 暴力行插入即可（快速构建杨表的方法）。 考虑前 $\sqrt n$ 列。第一个想法是利用性质 2，$P_{\pi}=P_{\pi^R}^T$。问题变成求 $b_m\sim b_1$ 杨表的前 $\sqrt n$ 行。 但是发现这是做不了的，因为插入只能向后插入，不能在开头插入。 这里需要另一个**结论**：$\pi$ 为排列，记 $\pi'=(n+1-\pi_1,n+1-\pi_2,\dots,n+1-\pi_n)$，有 $P_{\pi}$ 和 $P_{\pi'}$ 的**杨图形态**是反转的，注意里面的数是不一定反转的。 这个结论来自某篇 paper，具体证明我也不会。 根据这个结论，取 $(-b_1,-b_2,\dots,-b_m)$ 杨表的前 $\sqrt n$ 行即可，这就可以直接往后插入了。注意其实我们不需要杨表里面的数，只需要杨图的长度即可。