杨氏矩阵学习笔记

参考资料

IOI2019中国国家候选队论文集

袁方舟《浅谈杨氏矩阵在信息学竞赛中的应用》

标准杨表大概就是行单调增，列单调增并且行数单调不增，列数单调不增的一个矩阵

半标准杨表大概就是行或列有一个单调不降

插入x(以行为例）

从第一行开始

每次在当前行行找第一个最小的比x大的数

找不到就插到行末并退出

否则替换那个数并把那个数插入下一行

性质很多

某个有用的性质

前k行长度和是序列k-lis长度的最大值

「CTSC2017」最长上升子序列

code

钩子公式

对于一个规定了形状的标准杨表

对于n个元素它的个数有

(n!*prod_{(i,j)} frac{1}{hook(i,j)})

这里(hook(i,j)=(i,j))下方和右方的格子数量

对于规定形状的半标准杨表

对于值域为(r)它的个数有

(prod_{(i,j)} frac{r + j - i}{hook(i,j)})

HihoCoder-1480 矩阵填数

code

[Codechef]BB-Billboards

题解