Update 2024.11.6
- 突然发现一个错误，应该是：只需要保证在加入 的时候， 已经有值了即可。
经过和 @gza 和 @ORzyzRO 的讨论应该会了这道题。谢谢你们。
前置知识：杨表基础知识，还有 Robinson–Schensted 对应（即两个形状相同的标准杨表与一个排列一一对应）
对于官方“状态数较少”的解释（来自 @masterhuang）：在本题限制下杨表的形态数为 走到 的方案数。
在原题中，给定了最长递增子序列 (LIS = A) 和最长递减子序列 (LDS = B) 的长度，并且 的长度为 ，因此 的标准杨表形状是唯一确定的，就是一个 A * B 的杨表扣掉右下方的格子。
的限制即最后一个填的会使其恰好变成一个 A * B 的矩形，等价于要求 的杨表 满足（这个可以考虑 的插入过程）：
- 。
注意：只对于最终得到的杨表 1，即 RSK 插入得到的杨表有这个限制，但对于另一个的限制只有形状相同！！！
我们考虑对于一个符合的杨表，直接按从小到大的数来确定它，具体而言：我们假设当前得到的是只考虑 的杨表，形状为 （即每行分别有几列），加入 ，枚举加入在哪一行的末尾，得到一个新的杨表。
请注意：我们不是按照插入的顺序构造杨表，而是直接拓展原本的杨表！！！
只要一直加在轮廓线上就可以满足杨表的性质，同时我们要保证 的限制（上文已经转化成对杨表的值的等价限制），那么只需要保证在加入 的时候， 已经有值了即可。
官方题解
给定整数 、 和 。
有多少种排列 满足以下所有条件？请将结果对 取模。
- 的最长递增子序列的长度为 。
- 的最长递减子序列的长度为 。
- 存在一个整数 ，将 添加到 的末尾不会改变 的最长递增子序列和最长递减子序列的长度。
本题是考察 Robinson–Schensted 对应的练习题。
关于 Robinson–Schensted 对应的解释，国际读者可参考 英文维基百科。
在原题中，给定了最长递增子序列 (LIS) 和最长递减子序列 (LDS) 的长度，并且 的长度为 ，因此 的标准杨表形状是唯一确定的。
具体来说，该形状为一个矩形，有 行和 列，右下角的方格被移除。设 表示从上到下第 行、从左到右第 列的方格， 表示写在方格 上的数字。当前方格包含 ，且满足 和 。
考虑第三个条件。由于 LIS 和 LDS 长度不变，将 添加到 末尾会生成一个形状为 的杨表。设 表示生成后的杨表中方格 上的数字，需要满足：
- ，
- 。
为了满足这些条件，原来的 必须满足：
- 。
综上所述，我们只需统计满足以下条件的 的数量：
- 包含从 到 的所有整数，
- ，
- ，
- 。
在没有第四个条件的情况下，可以使用钩长公式轻松求解结果，但第四个条件会使得问题更复杂。
在本题中，给定的约束足够小，可以使用动态规划 (DP) 进行求解，其中 的值依次为 填充。最多存在 个状态，因此通过适当的实现可以快速运行。
题目要求找到满足 LIS 和 LDS 长度要求的排列数量。由于 Robinson–Schensted 对应提供了一种将排列映射到杨表形状的方法，我们可以确定每种满足 LIS 和 LDS 长度的排列对应的杨表形状，并对该形状上的数字填充问题进行求解。通过动态规划和钩长公式，我们能够快速计算出满足条件的排列数量。
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/bcyy/27116.html