杨氏矩阵
简要定义：
一个 $N$ 的整数划分 $x_1+x_2+\cdots x_m = N$ ，满足 $x_1\geq x_2\geq\cdots\geq x_m>0$ 。考虑有 $m$ 行，第 $i$ 行有 $x_i$ 列的表格，称为杨图。将 $1$ 到 $N$ 这 $N$ 个正整数填进去并满足：每一列从上到下单调递增，每一行从左往右单调递增，称其为杨表。当有的数出现了多次时，称对应杨表为” 半标准杨表”。
钩子公式：
- 定义一个方格 $(x,y)$ 的勾长 $h(x,y)$ 为：同行右边列的个数 + 同列下面行的个数 + $1$ 。
-
对于一个共有 $N$ 个格子的杨图 $S$，将 $1$ 到 $N$ 填入进去满足要求的方案数为：
$$
\frac{n!}{\prod _{(x,y)\in S}h(x,y)}
$$
与排列的关系：
- 插入算法：插入 $x$ 至杨表 $S$ 。从第一行开始，找到第一个大于 $x$ 的数，用 $x$ 替换其，然后将这个数插入到下一行，递归这个过程。直到找不到” 第一个大于 $x$ 的数”，此时将 $x$ 接到该行末尾。
- 删除算法：删除杨表 $S$ 中的 $(s,t)$ 位置（位置上数为 $x$），要求 $(s,t)$ 一定作为行末尾。从其所属行开始，在上一行中找到最大的比 $x$ 小的 $y$ ，替换其并移动到上一行。直到第一行直接删除其。
性质：
- $1.$ 每一个排列可以被一对同形状的杨表表示，一对同形状的杨表对应唯一一个排列。令 $f_{\lambda}$ 表示形状为 $\lambda$ 的杨表个数，那么有：
$$
n!=\sum_{\lambda}f_{\lambda}^2
$$ -
$1′.$ 最长上升子序列长度为 $\alpha$ ，最长下降子序列长度为 $\beta$ 的排列对应的杨表有 $\alpha$ 列 $\beta$ 行。同样的，对于这样的排列的个数为：
$$
A=\sum_{\lambda, 行数为\alpha, 列数为\beta} f_{\lambda}^2
$$
例子：「BJWC2018」最长上升子序列- 直接考虑计数，最后乘上 $\frac{1}{n!}$ 即可。
- 因为只需要在意最长上升子序列的长度 $\alpha$ ，就只需要枚举杨表的形状，用” 钩子公式” 计算排列数即可。这样子的话复杂度为不同的 $\lambda$ 的个数，不难发现这个值为 $P(n)$ ，即 $n$ 的划分数。
- $n\leq 28$ ，足已通过。事实上这个复杂度还可以跑 $n$ 更大的情况。
- 感觉有一种直接对杨表状态 $\rm{DP}$ 的做法，那样子的话复杂度大概可以做到 $O(n^2)$ 或 $O(n^3)$ 之类的，有空想想。
- *$1”.$ 最长非严格上升子序列长度为 $\alpha$ ，最长下降子序列长度为 $\beta$ 的排列对应的杨表有 $\alpha$ 列 $\beta$ 行。同样的，对于这样的排列的个数为：
$$
A=\sum_{\lambda, 行数为\alpha, 列数为\beta} g_{\lambda/\mu}f_{\lambda}
$$
$g_{\lambda/\mu}$ 表示权重为 $\mu$ 的半标准杨表数。显然当 $\mu=(1,1,\cdots,1)$ 时 $g_{\lambda/\mu}=f_{\lambda}$ 。 -
$2.$ 对于排列 $x$ ，其 最长上升子序列 的长度为其对应 杨表 的 第一行 的 列数。（注意，这里只的是长度对应，并不是指 “ 对应 杨表 中 第一行 的元素 即 $x$ 的上升子序列”）。
-
$3.$ 对于排列 $x$ ，其对应的 杨表 可以通过 翻转列和行 得到 其翻转排列 $x^R$ 对应的 杨表。
-
$4.$ 对于排列 $x$ ，其 最长下降子序列 的长度为其对应 杨表 的 第一列 的 行数。（可以通过 $3.$ 证明）。
-
最长 $\mathrm{k\verb|-|LIS}$ 子序列：指” 最长上升子序列” 长度不超过 $k$ 的最长子序列，显然最长 $\mathrm{1\verb|-|LIS}$ 子序列就是 $\mathrm{LDS}$ ，即其长度为对应杨表第一列的行数。结论：对应杨表的前 $k$ 列的行数和 即为最长 $\mathrm{k\verb|-|LIS}$ 子序列的长度。
- 暴力做法即离线下来，然后每次执行” 插入算法”，维护前 $k$ 列行数之和。显然做法是 $O(n^2\log n)$ 的。
- 可以发现：对于第 $i,i>\sqrt{n}$ 列，其行数一定小于 $\sqrt{n}$ 。即杨表的有效格子，一定是前 $\sqrt{n}$ 行和前 $\sqrt{n}$ 列的并集的子集。这样子的话查询的时候只需要按照 $k$ 的大小分类讨论即可。
- 注意到因为性质 $3$，可以开两个杨表，分别储存原数组 $x$ 和翻转数组 $x^R$ ，然后相当于只需要维护前 $\sqrt{n}$ 行的信息了。
- 这样子的话插入只要过了 $\sqrt{n}$ 行就可以立马返回，因为每层还需要二分找位置，所以单次插入复杂度为 $O(\sqrt{n}\log n)$ ，足以通过。
0 条评论