杨表
\(\lambda\) 是一个递减的 \(n\) 的整数拆分，假设 \(\lambda\) 有 \(m\) 项，杨图就是每行有 \(\lambda_{i}\) 列的表格，把 \(1-n\) 填入杨图，保证同行递增，同列递增，就得到标准杨表，如果同行非严格递增，同列严格递增，就得到半标准杨表。
RSK算法¶
将一个排列转化为杨表：考虑一个初始的空杨图，依次把元素插入，插入算法与删除算法又叫RSK算法。
将 \(x\) 插入杨表：从第一行开始，在当前行找到最小的大于 \(x\) 的 \(y\) ，然后用 \(x\) 替换 \(y\) ，用同样的方法从下一行开始插入 \(y\) ，如果找不到 \(y\) ，直接放到该行末尾。
该方法可以引申到对列插入。
根据插入算法倒推可以得到删除算法，目的是删除 \((s,t)\) 位置的元素。每次找到上一行比 \(x\) 小的最大数，替换，重复，直到第一行，删除即可。
LIS和LDS¶
杨表的一些性质：
-
将一个排列翻转之后得到的排列所对应的杨表 \(P_2\) 可以通过对原杨表 \(P_1\) 交换行列得到。
-
杨表前 \(k\) 列长度总和是 \(k-LIS\) 长度，前 \(k\) 行就是 \(k-LDS\) 长度。(\(K-LIS\) 是 \(LIS\) 长度不超过 \(k\) 的最长子序列)。
- 杨表第一行长度是 \(LIS\) 长度，第一列是 \(LDS\) 长度。
- \(LIS\) 长度为 \(\alpha\) ,\(LDS\) 长度为 \(\beta\) 的排列数是杨表数平方和。
- 非严格\(LIS\) 长度为 \(\alpha\) ,严格\(LDS\) 长度为 \(\beta\) 的排列数为\(\sum{g_{\lambda/\mu}f_{\lambda}}\)，\(\mu\) 为序列权重，\(g_{\lambda/\mu}\) 为相应半标准杨表数，当\(\mu = (1,1,…,1)\) 时，\(g_{\lambda/\mu}\) 为 \(f_\lambda\)。
于是就有了一些题
[CTSC2017]最长上升子序列(不会维护)
[BJWC2018]最长上升子序列(还没做)
钩子公式¶
定义 \(h_\lambda(i,j)\) 为杨表中 \((i,j)\) 元素下方和右方(包含自己)的格子数量。
则有杨表数计算公式 \(f_\lambda=\frac{n!}{\prod h_\lambda(i,j)}\)