杨表

杨表的概念

见 OIWiki。

勾长公式

$$\operatorname{dim} \pi_{\lambda}=\frac{n !}{\prod_{x \in Y(\lambda)} \operatorname{hook}(x)}$$

杨表行列长度的意义

$n\text{thlis}$：

1. $n=1$

   $n\text{thlis}$：等同于 $\text{lis}$。

2. $n>1$

   $n\text{thlis}$：删除掉 $1\text{thlis}\sim (n\!-\!1)\text{thlis}$ 剩下的序列的 $\text{lis}$ 中最长的。

   例：序列 $(3,1,4,2,5)$ 的 $\text{lis}$ 有 $(3,4,5)$， $(1,4,5)$，$(1,2,5)$。

   删去后剩的序列为 $(1,2)$，$(3,2)$，$(3,4)$。

   剩余序列的 $\text{lis}$ 为 $(1,2)$，$(3)$、$(2)$，$(3,4)$。

   则原序列的 $2\text{thlis}$ 为 $(1,2)$ 和 $(3,4)$。

$n\text{limlis}$：原序列的一个子序列，满足该子序列的 $\text{lis}$ 的长度不超过 $n$，且该子序列的长度在满足要求的所有子序列中最大。

$n\text{thlds}$ 和 $n\text{limlds}$ 的定义与之类似。

杨表的变换

定义以下符号：

$A=(a_1,a_2\cdots a_n)$：数列。

$\lVert A\rVert$：数列 $A$ 生成的杨表。

$\overline{\lVert A\rVert}$：杨表 $\lVert A\rVert$ 的形状（忽视杨表内数字）。

$-A=(-a_1,-a_2\cdots -a_n)$。

$A^{-1}=(a_n,a_{n-1}\cdots a_1)$。

$\lVert A\rVert^{-1}$：$\lVert A\rVert$ 的转置，及交换行和列。

有以下结论：

不管 $A$ 中有没有重复元素，$\overline{\lVert A^{-1}\rVert}=\overline{\lVert -A\rVert}$。

如果 $A$ 中没有重复元素，$\lVert A\rVert^{-1}=\lVert A^{-1}\rVert$，$\overline{\lVert A\rVert^{-1}}=\overline{\lVert -A\rVert}$。

代码

vector<int> yt[MAXn + 10];
void Insert(int v) {
    for (int i = 1; ; ++i) {
        int siz = yt[i].size();
        if (siz == 0 || yt[i][siz - 1] < v) {
            yt[i].push_back(v);
            break;
        } else {
            swap(*lower_bound(begin(yt[i]), end(yt[i]), v), v);
        }
    }
}

杨表的其他性质

1. 求有重复元素的数列的严格上升子序列时，可以给数列里的元素附加第二关键字，将 $a_i$ 变为 $(a_i,n-i+1)$，这样不会影响答案并且能使数列里没有相同的元素。

2. 一个排列和两个形状相同但是内部数字顺序不一定相同的杨表（这两个杨表有先后顺序）形成双射，也就是说，对于一个杨表的形状 $\lambda$，他的填发有 $dim_{\lambda}$ 种，那么满足 $\overline{\lVert P\rVert}=\lambda$ 的排列 $P$ 有 $dim^2_{\lambda}$ 个。

3. 对于任意一个杨表，试图用 $1\times 2$ 和 $2\times 1$ 的骨牌不重叠可不完全覆盖地覆盖这个杨表，最大覆盖的骨牌数量为行列编号和为奇数的格子数量和行列编号和为偶数的格子数量的最小值。