杨氏矩阵

简要定义:

一个 $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}$ 子序列的长度

    例子:「CTSC2017」最长上升子序列

    • 暴力做法即离线下来,然后每次执行” 插入算法”,维护前 $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)$ ,足以通过。
分类: 文章

Qiuly

QAQ

0 条评论

发表评论

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

*

code