已经是老年选手了，却没有一个老年选手应有的科技树，这是为什么呢?
杨图
就是把ferrers图的点换成可以填数的格子。我们还是用从上往下每行的长度表示一个杨图。
杨表
杨图里填一个排列。标准杨表是每个格子填的数比右边和下边都小的杨表，如果连连边并固定所有极右下的格子，它就是一个拓扑序。
如果杨图里填的不是排列。比右边小，不比下边大的称为行严格杨表，反过来就是列严格，这两种统称为半标准杨表。非严格杨表是两个方向都不严格的杨表。
一般我们说杨表，说的都是标准杨表。
斜杨图，斜杨表
斜杨图是一个杨图挖去另一个杨图，我们可以用两个分拆$\lambda,\mu$来表示它为$\lambda/\mu$。斜杨表是斜杨图里填一个排列。
rsk algorithm
对于一个排列，我们从左往右把每个数插进一个杨表。每次插入，从上往下扫每一行，如果要插的数比这一行所有数都大(或者这一行没有数了)，把它附到这一行末尾，否则找到它的后继和它交换，转而插入它的后继。
有这么几个结论 : 把排列翻转，则得到的杨表转置。把$p_i$变成$n-p_i+1$，则得到的杨表形状转置，内容不一定。
第一行的长度是lis长度。第一列的长度是lds长度。前$k$行长度的和是最长的可以分解成$k$个上升子序列的子序列的长度，或者说只包含长不超过$k$的下降子序列，前$k$列反过来。
rsk对一般的序列也是有效的，只需要考虑给相同的随便钦点一个顺序就可以说明这件事。
ctsc2017 最长上升子序列
那么我们就直接维护前缀rsk杨表对吧。
注意到如果杨表很长，我们会跑的很慢，但是它大概很窄。考虑设最后durfee square的边长是$k$，那么我们只维护前$k$行和$k$列的形状就可以拼出整个杨表，而$k=O(\sqrt{n})$。前$k$列可以通过维护$n-p_i+1$的杨表来完成。复杂度$O(n\sqrt{n}\log n+q\sqrt{n})$。
hdu mutc 2019 D6 I. Three Investigators
选$5$次lis，那么也就是说我们选的部分lds长度不超过$5$，也就是杨表的前$5$行。但是这个是最长的，我们要求和最大的，考虑只需要把$x$插入$x$次就好啦。但是这样元素个数就爆炸了。当然把连续段缩起来，那么每次插入会把一些段换出来让它们降一级，这里是有均摊的，然后还可能有一段没被换完，我们需要给一个势能让这种事发生的时候势能总是减小的，可以想到给$k$级$2^k-1$的势能，那么没换完的时候新段增加的势能就是$2^{k-1}-1$，而插入之前发生的降段减少了$2^{k-1}$的势能，这就摊掉了。复杂度是$O(2^kn\log n)$，这里$k=5$。
rsk双射
注意到rsk是可逆的。我们插入的时候，记录下每个数最后停在哪，这可以用另一个杨表，称为记录表，来表示，也就是第$i$次插入的结束位置放一个$i$的杨表。那么我们就得到形状相同的杨表对到排列的双射，这里杨表对到排列就是把记录表中的数从大到小删除，并去第一个表中对应位置做rsk删除。那么我们证明了大小为$n$的每个形状杨表数量的平方之和是$n!$。
有趣的事情是，如果杨表对$\lambda,\mu$对应排列$p$，那么$\mu,\lambda$对应$p$的逆。我们可以用它计算杨表总数，它就是自己是自己的逆的排列个数，称为 involution number 卷数对合数。显然这样的排列是若干个单点和二元环，考虑$n$是单点还是二元环就得到一个整式递推。
杨表计数
hook formula用于计算一个杨图对应的标准杨表个数。定义一个位置的 hook length 钩长 是它，它正下方，它正右方的格子总数，那么答案就是$n!$除以各钩长的积。
容易在$O(n)$时间内算出一个杨表的所有钩长。
bjwc2018 最长上升子序列
那么我们枚举这个杨表的形状，它的个数是分拆数，非常小对吧!然后就可以hook formula一下了。
集训队论文题
求长$n$，lds长度$\leq 3$的排列个数。
那么也就是不超过三行。我们枚举三行的长度，这是$O(n^2)$的，问题是怎么$O(1)$地更新钩长乘积。考虑第二行变长$1$的时候，第一行只有一个钩长受影响，第二行几乎所有钩长都变长$1$所以实际上变化量只有两边的$O(1)$。考虑第三行变短$1$的时候，第一行只有一个钩长受影响，第二行只有一个钩长受影响，第三行几乎所有钩长都变短$1$所以实际上变化量只有两边的$O(1)$。
斜杨表计数
https://www.emis.de/journals/SLC/wpapers/s73vortrag/naruse.pdf
斜杨表的计数就没有一个hook formula这么劲爆的公式了。对于一个$d$行共有$n$个格子的斜杨表$\lambda/\mu$，我们构造$d\times d$的矩阵$A$满足$a_{i,j}=\frac{1}{((\lambda_i-i)-(\mu_j-j))!}$，如果$(\lambda_i-i)-(\mu_j-j)$是负数则是$0$，那么答案是$n!\det A$。
考虑刚才我们看到的那个游走问题，雅礼集训 path，斜杨表计数其实就是说在$d$维空间中从$\mu$走到$\lambda$，保持各维坐标递增的方案数。这让我们一定程度上想起lgv引理。
考虑这么一个构造，让每维从平面上的$(1,\mu_i-i)$走到$(n,\lambda_i-i)$，每一步可以选择往右或者往上走，要求路径不交，每次$i$维往上走我们就在$i$维的最后记下此时的横坐标，那么这是一个每个值在$1,…,n$中的列严格斜杨表数。$-i$是为了把本来要求的不互相穿过变成lgv中的不交。
发现问题在于我们可能在一个横坐标往上走很多步，并且可能有很多行都在这个横坐标上走了。考虑类似于lgv引理，如果路径交了则交换终点。我们枚举一个排列对逆序对数进行容斥，然后把每个横坐标的恰好一步的往上走分给每行，这里如果根据这个排列$i$最后走到$j$，那么就需要$(\lambda_i-i)-(\mu_j-j)$步，于是拿多项式系数选选就得到了公式中的$\frac{1}{((\lambda_i-i)-(\mu_j-j))!}$。
xix open cup gp of zhejiang G. Good Game
进行一个经典容斥dp之后，就是模板 斜杨表计数 了。你可以在boj19023找到这个题。
hook formula的证明
当所有$\mu_i=0$的时候，$a_{i,j}=\frac{1}{(\lambda_i-i+j)!}$，它的第$i$行是$\frac{1}{(\lambda_i-i+1)!},\frac{1}{(\lambda_i-i+2)!},…,\frac{1}{(\lambda_i-i+d)!}$。我们每行提出一个$\frac{1}{(\lambda_i-i+d)!}$，它就变成$(\lambda_i-i+d)^\underline{d-1},(\lambda_i-i+d)^\underline{d-2},…,(\lambda_i-i+d)^\underline{0}$。通过斯特林数我们可以做若干 把一列加到另一列 把下降幂变成普通幂，于是这变成一个范德蒙德矩阵，它的行列式就是$\prod\limits{i<j}((\lambda_i-i)-(\lambda_j-j))$，也就是说答案是$\frac{n!}{\prod\limits_i(\lambda_i-i+d)!}\prod\limits_{i<j}((\lambda_i-i)-(\lambda_j-j))$。
事实证明这确实是hook formula的另一种形式。一个劲爆观察是$(\lambda_i-i+d)!=\left(\prod\limits_{j>i}((\lambda_i-i)-(\lambda_j-j))\right)\left(\prod\limits_{j\leq\lambda_i}h(i,j)\right)$，$h$是钩长，后面那个$\prod$就是一行钩长的乘积。考虑一行有$\lambda_i$个格子，钩长不超过$\lambda_i-i+d$并且从左往右严格递减，每次值域上出现一个空位，说明后面的某行在这里结束了，此时补上各$(\lambda_i-i)-(\lambda_j-j)$是正好的。具体一点，如果$(i,j)$向下延伸到$k$行，那么钩长就是$\lambda_i-j+k-i+1$，如果$(i,j+1)$只延伸到$l$行，那么$\lambda_i-j+k-i,…,\lambda_i-j+l-i+1$都需要补上，这里$\lambda_k,…,\lambda_{l+1}$都是$j$，于是我们就得到这个式子。
列严格杨表
容易想到继续对着那个行列式嗯推列严格杨表的hook formula，但是这个难度比较大。你可以在洛谷8114 Cnoi2021 六边形战士 的题解找到一个特殊情况下利用Krattenthaler’s formula的证明，但是我不会证明Krattenthaler’s formula。
这里不加证明地给出列严格杨表的hook formula，如果我们填的数都在$1,…,k$中，那么列严格杨表的个数是$\prod\limits_{i,j}\frac{k-i+j}{h(i,j)}$，其中$h$是钩长。
看起来标准杨表的hook formula称为hook length formula，列严格杨表的称为hook content formula。
loj6677 EntropyIncreaser 与菱形计数
洛谷8114 Cnoi2021 六边形战士/zjoi2022 D2 B. 计算几何 也是同一个东西。
可以看一下六边形战士的题解图，对于三边长$a,b,c$的问题，这玩意可以转化成$a\times b$的，每个数在$0,…,c$中的非严格杨表个数(这里是$>$而不是$<$)。非严格杨表一般是不好数到1e6的，但是这里它是$a\times b$的，我们给第$i$行加上$a-i$，这就变成了每个数在$0,…,a+c$中的列严格杨表，容易验证这是一个双射。套用列严格杨表的hook formula，答案即为$\prod\limits_{i,j}\frac{a+c-i+j}{a+b-i-j+1}$。容易线性地算出每个$i+j$和$i-j$的出现次数。差分之后可以发现更劲爆的结论，答案就是$\frac{(a+b+c-1)?(a-1)?(b-1)?(c-1)?}{(a+b-1)?(b+c-1)?(a+c-1)?}$，其中$?$是阶乘前缀积。
雅礼集训2017 D11 path
排成一个第$i$行长$a_i$的杨图，对于每种方案，在$i$行$j$列填$i$维第一次到达$j$的时刻，那么合法当且仅当这是一个杨表，问题就是杨表计数啦。
但是这里$\sum a_i$可能很大。直接对着那个范德蒙德行列式的式子法法即可。
_rqy题
$01$序列，每次可以把一个$10$子串换成$01$，求有多少种方案换到不能再换。$n\leq 2\times 10^5$。
最后当然是变成$0…01…1$这样的，并且$01$内部的顺序分别没有变，并且每一对逆序对都会被换恰好一次。考虑我们把$0$编号为$0_1,…,0_{c_0}$，$1$同理，把操作序列写成每次选择一个$1_i$和一个$0_j$交换，那么一个操作序列合法当且仅当它是逆序对们的一个排列，并且交换$1_i,0_j$的时候$1_i$真的在$0_j$前面一位。可以发现这个等价于$1_{i+1},0_j$和$1_i,0_{j-1}$都已经换完了，于是考虑每一对是在第几步被换的，这就转化成杨表计数。和 雅礼集训2017 D11 path 一样做即可。