OI-wiki 杨氏矩阵杨表完全指南定义、RSK 插入算法与勾长公式【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读杨氏矩阵Young tableau简称杨表是组合数学、表示论与舒伯特演算中的核心组合对象也是算法竞赛中处理最长上升/下降子序列问题的一把利器。本文以 OI-wiki 的杨表文档为主体结合仓库中的整数分拆与序理论资料系统讲解杨图与杨表的严格定义、RSK 插入算法的完整流程、勾长公式的计算方法并通过 CTSC2017、BJWC2018、CF1268B 三道真题展示其在信息学竞赛中的典型应用。读完本文你将能够识别杨表类问题、手算勾长公式、理解「杨表前 k 列长度之和等于最长 k-LIS 长度」这一关键定理并掌握其 $O(n\sqrt{n}\log n)$ 的维护思路。引入什么是杨氏矩阵杨氏矩阵Young tableau又名杨表是一种常用于表示论Representation theory和舒伯特演算Schubert calculus中的组合对象。杨表是一种特殊的矩阵它便于对称群和一般线性群的群表示和性质研究。杨表由剑桥大学数学家阿尔弗雷德·杨Alfred Young于 1900 年首次提出于 1903 年被德国数学家弗罗贝尼乌斯Ferdinand Georg Frobenius应用于对称群的研究。注释表示论Representation theory是数学的一个分支它通过将元素表示为向量空间的线性变换来研究抽象代数结构。舒伯特演算Schubert calculus是代数几何的一个分支于 19 世纪由赫尔曼·舒伯特为了解决射影几何的计数问题而引入。从组合视角看杨表与整数分拆存在一一对应的关系形状即分拆因此杨表理论天然地与分拆数、Ferrers 图、偏序格等概念交织在一起。OI-wiki 在分拆一节中对分拆数与 Ferrers 图有专门介绍是阅读本文的前置知识。定义从杨图到杨表杨图Young diagram杨图Young diagram使用点表示时又称 Ferrers 图在分拆数一节中有相关介绍是一个有限的框或单元格集合左对齐排列行长按非递增顺序排列。如果把杨图每行的方格数列出我们得到了一个非负整数 $n$总方格数的整数分拆integer partition$\lambda$。因此我们可以将杨图的形状看作 $\lambda$因为它携带与其整数拆分相同的信息。杨图之间的包含关系定义了整数分拆上的一个偏序关系此关系拥有格的结构被称为杨格Youngs lattice。如果把杨图各列的方格数列出则会得到整数分拆 $\lambda$ 的「共轭分拆」或「转置分拆」它所对应到的杨图可由原本的杨图沿主对角线作镜射对称而得——这与分拆数一节中 Ferrers 图沿对角线翻转得到共轭的操作完全一致。杨图每个方格的位置由分别代表行数与列数的两个座标点决定。列的顺序由左向右行的顺序则按方格数的由多向少的方向。此处需要注意根据习惯不同存在着两种不同的杨图画法英式画法方格数较少的行排在方格数较多的行的下方主要由英语国家使用法式画法各行由大到小一层一层往上叠通常被法语国家使用。以下表格中分别为整数分拆 $(5,4,1)$ 对应的杨图不同画法英式画法法式画法杨表Young tableau定义杨表Young tableau是通过用取自某个字母表的符号填充杨氏图的框来获得的这通常需要是一个全序集和。填入的元素写作 $x_1, x_2, x_3, \ldots$。但为了方便起见都直接填入正整数。杨表最初应用于对称群的表示理论时允许在杨图的 $n$ 个方格中任意填入 $1$ 到 $n$ 中相异的正整数。但现在的研究大多使用「标准」的杨表即上述条件中各行与各列中方格的数字皆为严格递增的。由 $n$ 个方格的相异杨表数个数形成对和数involution number/telephone number注释对和数是在数学中是一个整数序列用来计算 $n$ 条电话线中每条线路最多可以连接到另一条线路时可以相互连接的方法个数。它还可以用来描述完全图 $n$ 个顶点上的匹配数$n$ 个对合元素的排列数Hermite 多项式系数的绝对值之和含有 $n$ 个格子的标准杨表的个数以及不可约对称群的度数之和。$$1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, \ldots$$OEIS 中的数列 A000085在其他应用中杨图也可以被填入相同的数字。若填法的同列数字严格递增且同行数字单调递增则该杨表被称为是半标准的Semistandard Young Tableaux有时称为列严格。杨表中各数字出现的次数记录下来得到的序列被视为杨表的权重。因此标准杨表的权重必然是 $(1,1,\ldots,1)$因为在标准杨表中$1$ 到 $n$ 的每个正整数恰好各出现一次。标准杨表的插入算法RSK 插入排列的性质可以由杨表直观地表现出来。RSK 插入算法就提供了一个将杨表和排列联系起来的途径它由 Robinson、Schensted 和 Knuth 提出。令 $S$ 是一个杨表定义 $S \leftarrow x$ 表示将 $x$ 从第一行插入杨表中具体如下在当前行中找到最小的比 $x$ 大的数$y$。如果找到了用 $x$ 去替换 $y$移到下一行令 $x \leftarrow y$ 重复操作 1。如果找不到就把 $x$ 放在该行末尾并退出。记 $x$ 在第 $s$ 行第 $t$ 列$(s, t)$ 必定是一个边角corner。一个格子 $(s, t)$ 是边角当且仅当 $(s 1, t)$ 和 $(s, t 1)$ 都不存在格子。例如将 $3$ 插入杨表 $(2, 5, 9)(6, 7)(8)$ 的步骤为具体过程为第一行中找到最小的大于 $3$ 的数 $5$用 $3$ 替换 $5$ 并将 $5$ 推入第二行第二行中找到最小的大于 $5$ 的数 $6$用 $5$ 替换 $6$ 并将 $6$ 推入第三行第三行中找不到大于 $6$ 的数将 $6$ 放在行末插入完成。注意每一步中被顶出的元素会继续向下传播这正是 RSK 插入算法保证杨表行、列严格递增性质不被破坏的关键。算法复杂度对单个元素执行一次插入最坏情况下需要沿着对角线遍历 $O(n)$ 个格子对长度为 $n$ 的排列逐个插入构建杨表朴素实现的总复杂度为 $O(n^2)$或 $O(n^2\log n)$视查找操作的数据结构而定。这正是后面例题中需要引入根号分治优化的原因。变体Variations非完全严格标准的杨表有许多变体。例如行严格杨表要求同行数字严格递增且同列数字单调递增即列严格杨表的共轭。此外在平面分拆plane partitions理论中习惯上会将上述定义中的递增改为递减。其他变体例如带状杨表会先将一些方块打包成群然后要求各群的方块必须填入相同数字。斜杨表Skew tableaux给定两个杨图 $\lambda (\lambda_1, \lambda_2, \ldots)$、$\mu (\mu_1, \mu_2, \ldots)$满足 $\lambda$ 包含 $\mu$即 $\mu_i \leq \lambda_i$ 对所有 $i$。定义「斜杨图」$\lambda/\mu$ 为 $\lambda$ 中所有方格减去$\mu$ 中的所有方格即 $\lambda$ 差集 $\mu$。在斜杨图的各方格中填入元素就形成了斜杨表Skew tableaux。例如下图为整数分拆 $(5,4,1)$ 对应的一个标准斜杨表同理若满足同一列中的数字严格递增且同一行中的数字单调递增则该斜杨表被称作半标准斜杨表若半标准斜杨表满足各方格不重复地填入数字 $1$ 到 $n$方格总数则该斜杨表被称作标准斜杨表。注意由不同的 $\lambda$ 和 $\mu$ 可得到相同的 $\lambda/\mu$。虽然大部分斜杨表的性质都只依赖于取完差集的方格但是仍然部分运算依赖于 $\lambda$ 和 $\mu$ 的选取。因此$\lambda/\mu$ 必须被视为包含两个元素信息$\lambda$ 和 $\mu$。当 $\mu$ 是空分拆$0$ 的唯一一种分拆时斜杨表 $\lambda/\mu$ 就变成杨表 $\lambda$。应用勾长公式杨表常用于在组合学、表示理论和代数几何中用各种不同计算杨表个数的方法得到舒尔函数的定义及相关的恒等式。在信息学竞赛中常有考察杨表勾长公式的题目。勾长hook length给定一个共有 $n$ 个方格的杨表 $\pi_{\lambda}$把 $1$ 到 $n$ 的 $n$ 个数字填入杨表中使得每行从左到右、每列从下到上都是递增的。用 $\dim_{\pi_{\lambda}}$ 表示可以这样填的方法个数。对于杨表中的一个方格 $v$定义其勾长$\mathrm{hook}(v)$ 等于同行右边的方格数加上同列上面的方格数再加 $1$即方格本身。直观理解勾长衡量的是「从这个格子出发向右走到行尾、再向上走到列顶」所覆盖的 L 形区域中格子的总数包含自身。勾长公式Hook length formula如果用 $\dim_{\lambda}$ 表示这样的方法个数勾长公式就是方法个数等于 $n!$ 除以所有方格的勾长的乘积$$ \dim \pi_{\lambda}{\frac {n!}{\prod_{{x\in Y(\lambda)}}{\mathrm {hook}}(x)}}. $$所以对于整数分拆 $10 5 4 1$ 的杨表如上图所示图中标注了每个格子的勾长有$$ \dim \pi_{\lambda }{\frac {10!}{7\cdot 5\cdot 4\cdot 3\cdot 1\cdot 5\cdot 3\cdot 2\cdot 1\cdot 1}}288. $$种方法。手算要点勾长的计算只需要关注形状与格子中填入的具体数字无关。给定杨图后从右下角向左上角逐格计算——右下角格子的勾长恒为 $1$同行左边的格子勾长等于其右边格子勾长加 $1$同行右侧每格贡献 $1$同列下方的格子同理。图中杨表第一行勾长依次为 $7,5,4,3,1$第二行为 $5,3,2,1$第三行为 $1$代入公式即可验证 $288$ 这一结果。例题杨表与子序列问题对于杨表 $P$定义对于一个从 $1$ 到 $n$ 的排列 $X x_1, \ldots, x_n$$P_X$ 中第一行的长度即为排列 $X$ 的**最长上升子序列LIS**长度。注意$P$ 的第一行并不一定是 LIS 本身所以不能直接利用杨表性质解决「LIS 划分」之类的问题。对于一个排列 $X$ 和它产生的杨表 $P_X$若 $X^R$ 是 $X$ 的翻转那么 $X^R$ 产生的杨表 $P_{X^R}$ 即为 $P_X$交换行列得到。例如对于排列 $X 1, 5, 7, 2, 8, 6, 3, 4$ 和 $X^R 4, 3, 6, 8, 2, 7, 5, 1$我们可得到如下杨表 $P_X$杨表 $P_X$ 中的第一列长度即为排列 $X$ 的**最长下降子序列LDS**长度。定义长度不超过 $k$ 的 LIS/LDS 长度为 $k$-LIS 和 $k$-LDS此类问题我们同样可以用杨表来解决。对于 $1$-LIS显而易见最长的 $1$-LIS 子序列就是该序列的 LDS这也正是杨表的第一列同样可得杨表前 $k$ 列的长度就是最长的 $k$-LIS 子序列的长度。证明如下对于一个排列 $X$ 和它的 $m$ 行杨表 $P$令排列 $X^$ 为 $(P_{m,1}\ldots,P_{m,\lambda_m},P_{m-1,1}\ldots,P_{1,1}\ldots P_{1,\lambda_1})$即将杨表从下往上每行依次写在后面。那么 $X$ 一定可以通过交换操作转化成 $X^$。所以最长 $k$-LIS 子序列长度可以表示成 $F(k)\sum_{i1}^{m} \min(k,\lambda_i)$即前 $k$ 列的长度和。CTSC2017 最长上升子序列有一个长为 $n$ 的数列 $b$。对于序列 $B_m (b_1, b_2, \ldots, b_m)$设 $C$ 是 $B_m$ 的子序列且 $C$ 的最长上升子序列的长度不超过 $k$询问 $C$ 的长度最大值。解题思路多个询问考虑使用扫描线的方法。这样我们就需要维护每个前缀的杨表。如果使用以上结论可以发现问题变成了如何快速维护杨表前 $k$ 列的长度之和。如果直接维护复杂度是 $O(n^2 \log n)$ 的不能接受。考虑维护前 $\sqrt{n}$ 列和前 $\sqrt{n}$ 行。可以发现杨表一定不会完全覆盖这个 $W \times H$ 的矩形。如果 $K \leq W$那么可以直接得答案如果 $K W$那么大于 $W$ 的部分一定在 $H$ 行内。所以可以考虑如何同时维护前 $\sqrt{n}$ 列和前 $\sqrt{n}$ 行。将这个排列翻转一下就可以得到杨表的翻转所以只需要再同时维护 $-A_i$ 即可复杂度为 $O(n \sqrt{n} \log n)$。要点解读该做法之所以成立依赖于上面两条性质——翻转排列对应杨表行列互换性质 2因此同时维护 $A_i$ 与 $-A_i$ 两套杨表就能分别获得前 $\sqrt{n}$ 列与前 $\sqrt{n}$ 行的信息而由 $F(k)\sum \min(k,\lambda_i)$任意 $k$ 的答案要么落在这两部分的覆盖范围内要么由矩形外界的行/列结构直接给出从而将 $O(n^2\log n)$ 的朴素维护优化到 $O(n\sqrt{n}\log n)$。BJWC2018 最长上升子序列现在有一个长度为 $n$ 的随机排列求它的最长上升子序列长度的期望。本题可利用杨表第一行长度即 LIS 长度的性质结合对和数标准杨表计数进行推导。注意到标准杨表的计数正是对和数序列 $1, 1, 2, 4, 10, 26, \ldots$A000085而勾长公式 $\dim\pi_\lambda n! / \prod \mathrm{hook}(x)$ 给出了固定形状下标准填法的个数这些工具共同服务于随机排列 LIS 期望的计算。CF1268B 杨氏多米诺骨牌给定一个具有 $n$ 列长度 $a_1, a_2, \ldots, a_n$$a_1 \geq a_2 \geq \ldots \geq a_n \geq 1$的直方图。$a[3,2,2,2,1]$ 的杨图。找到可以在此直方图中绘制的最大数量的非重叠多米诺骨牌$1 \times 2$ 或 $2 \times 1$ 矩形。本题将杨图与经典的多米诺骨牌覆盖问题结合需要根据行与列方向的覆盖能力进行贪心或组合计数分析考察对杨图形状结构的理解与转化能力。总结核心概念关键结论典型应用杨图 / Ferrers 图形状即整数分拆包含关系构成杨格分拆数、共轭分拆标准杨表 / 半标准杨表行、列严格递增权重记录数字出现次数对和数A000085RSK 插入算法逐行找最小大于 $x$ 的数并顶替下推由排列构造杨表 $P_X$勾长公式$\dim\pi_\lambda n! / \prod \mathrm{hook}(x)$计数固定形状的标准填法杨表与 LIS/LDS第一行长度 LIS第一列长度 LDS前 $k$ 列长度和 $k$-LISCTSC2017、BJWC2018杨表在信息学竞赛中是一类「形状优美、结论深刻」的组合工具从 RSK 插入构造杨表到勾长公式计数再到「前 $k$ 列长度和 最长 $k$-LIS」这一关键定理构成了从定义到应用的完整链条。掌握上述内容后遇到最长上升子序列变种、杨图覆盖计数类问题即可快速识别并套用杨表框架。参考资料与拓展阅读Young Tableau - from Wolfram MathWorldYoung tableau - WikipediaHook length formula - Wikipedia袁方舟《浅谈杨氏矩阵在信息学竞赛中的应用》IOI2019中国国家候选队论文集202-229仓库内延伸阅读本主题在 OI-wiki 中与以下内容相互关联建议一并阅读——整数分拆与 Ferrers 图杨图的组合基础含分拆数递推与生成函数、序理论偏序集与格杨格的数学背景、最长上升子序列相关的基础算法杨表方法与传统 LIS 求解的对比视角。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
