题目描述
给定整数 \(A\)、\(B\) 和 \(M\)。
有多少种排列 \(P = (P_1, \dots, P_{AB-1})\) 满足以下所有条件？请将结果对 \(M\) 取模。
- \(P\) 的最长递增子序列的长度为 \(A\)。
- \(P\) 的最长递减子序列的长度为 \(B\)。
- 存在一个整数 \(n\)，将 \(n + 0.5\) 添加到 \(P\) 的末尾不会改变 \(P\) 的最长递增子序列和最长递减子序列的长度。
题解
本题是考察 Robinson–Schensted 对应的练习题。
关于 Robinson–Schensted 对应的解释，国际读者可参考 英文维基百科。
在原题中，给定了最长递增子序列 (LIS) 和最长递减子序列 (LDS) 的长度，并且 \(P\) 的长度为 \((AB-1)\)，因此 \(P\) 的标准杨表形状是唯一确定的。
具体来说，该形状为一个矩形，有 \(B\) 行和 \(A\) 列，右下角的方格被移除。设 \((i,j)\) 表示从上到下第 \(i\) 行、从左到右第 \(j\) 列的方格，\(t_{i,j}\) 表示写在方格 \((i,j)\) 上的数字。当前方格包含 \((1,1),\ldots,(1,A),(2,1),\ldots,(2,A),\ldots,(B,1),\ldots,(B,A-1)\)，且满足 \(t_{i,j} < t_{i+1,j}\) 和 \(t_{i,j} < t_{i,j+1}\)。
考虑第三个条件。由于 LIS 和 LDS 长度不变，将 \((n+0.5)\) 添加到 \(P\) 末尾会生成一个形状为 \(B\times A\) 的杨表。设 \(t'_{i,j}\) 表示生成后的杨表中方格 \((i,j)\) 上的数字，需要满足：
- \(t'_{1,A} = n + 0.5\)，
- \(t'_{i+1,A} = t_{i,A} \ (1 \leq i \leq B-1)\)。
为了满足这些条件，原来的 \(t\) 必须满足：
- \(t_{i,A} > t_{i+1,A-1} \ (1 \leq i \leq B-1)\)。
综上所述，我们只需统计满足以下条件的 \(t\) 的数量：
- \(t\) 包含从 \(0\) 到 \((AB-1)\) 的所有整数，
- \(t_{i,j} < t_{i+1,j}\)，
- \(t_{i,j} < t_{i,j+1}\)，
- \(t_{i+1,A-1} < t_{i,A}\)。
在没有第四个条件的情况下，可以使用钩长公式轻松求解结果，但第四个条件会使得问题更复杂。
在本题中，给定的约束足够小，可以使用动态规划 (DP) 进行求解，其中 \(t\) 的值依次为 \(1, 2, \ldots, AB-1\) 填充。最多存在 500000 个状态，因此通过适当的实现可以快速运行。
思路解释
题目要求找到满足 LIS 和 LDS 长度要求的排列数量。由于 Robinson–Schensted 对应提供了一种将排列映射到杨表形状的方法，我们可以确定每种满足 LIS 和 LDS 长度的排列对应的杨表形状，并对该形状上的数字填充问题进行求解。通过动态规划和钩长公式，我们能够快速计算出满足条件的排列数量。
标签：4.0,题解,LDS,方格,ABC378G,LIS,序列,长度,ldots From： https://www.cnblogs.com/SkyMaths/p/18522544