杨氏矩阵（杨表）学习笔记

发表于 2020-07-31 更新于 2021-06-17 分类于 OI 阅读次数：

其实学这个并不能帮我改变NOI要打铁这件事从19年集训队论文里抄了一下。省略证明，记一些不严谨，仅仅是能用级别的结论。

杨表的插入

比如插入行，扫每一行，找到比它大的最小值，交换一下继续下一行。注意到杨表的单调性，可以二分。b找不到就丢这一行后面

杨表与LIS

杨表第一行的长度就是LIS。

排列计数

枚举$n$的所有拆分，把它们的$f$（有多少种杨表）的平方加入答案

杨表计数

定义$h$是某个格子的正下边，正右边（包括自己）一共有几个格子。有钩子公式： $$f_{\lambda} = \frac{n!}{\prod h_{\lambda}(i,j)}$$

LIS长度限制的排列计数

其实就是限制一下形态之后的杨表计数 $k=2$：$\frac{1}{n+1}\binom{2n}{n}$ $k=3$：$\frac{1}{(n+1)^2(n+2)}\sum_{j=0}^n \binom{2j}{j}\binom{n+1}{k+1}\binom{n+2}{k+1}$ 后面的貌似比较难搞。不过可以证明，这玩意是可以递推的。

剩下的东西摸了，来两个题：

[BJWC2018]最长上升子序列

考虑暴力枚举$n$的划分，之后用钩子定理搞一下有多少杨表记为$f$，则把$f^2 \lambda_1$计入答案。当然这个题还有另一种做法：考虑对每个位置的LIS差分，则变成了01序列，DP套DP搞一下即可

[CTSC2017]最长上升子序列

最长上升序列不超过$k$，等价于可以划分为不超过$k$个下降序列，即等价于杨表的前$k$列一共有多少元素。注意到序列给定，于是只需扫描线，动态维护杨表。就有了一个平方算法。注意到改变杨表的插入方式是等价的，并且对于一个元素，它两位坐标中的min是根号的，于是维护两种矩阵就可以了。至于如何维护第二个矩阵？反转比较方式即可。

三格骨牌

一道网上找到的模拟赛题 https://www.cnblogs.com/coldchair/p/11116902.html https://memset0.cn/contest20190711 有点丧心病狂，不写了。大概是个钩子定理的题

[雅礼集训 2017 Day11]PATH

考虑二维的情况：首先易知这玩意是个卡特兰数。卡特兰数对应了$2 \times n$的杨表。类比一下，这道题就是给定了划分$\lambda$，求有多少种杨表。考虑钩子公式：要求$\prod h(i,j)$。考虑枚举每个$i$，则可能的值在$[1,\lambda_i+n-i]$之间。首先全乘上，再除掉不合法的。可以注意到，一行的值不一样，所以是个阶乘考虑什么情况下会不合法：令$r_i =\lambda_i+n-i$，则$r_i - r_j(i < j)$不合法。拆开之后发现FFT一下就行了