杨氏矩阵(杨表) 学习笔记

其实学这个并不能帮我改变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一下就行了

发表评论

电子邮件地址不会被公开。必填项已用 * 标注