题解 P4484 【[BJWC2018]最长上升子序列】

· · 题解

一个基于杨表的暴力：

由杨表的构造过程可知，一个序列构建的杨表其第一行长度就是 LIS 长度。因此我们想知道：对于每个 1\le k \le n，对于一个长为 n 的排列，有多少种排列使得杨表的第一行长度为 k。

Robinson-Schensted correspondence 定理指出，对于任何两个相同形状的杨表（填数的顺序可能不同），可以与排列建立一一对应。

因此我们要求的就是

\frac 1{n!}\sum_{\lambda \vdash n} f_\lambda ^2 \lambda_1

其中 \lambda \vdash n 是一个 n 的整数拆分，f_\lambda 是 \lambda 这个整数划分的填法数量。通过 Hook 公式可以在 \Theta(n) 时间内计算。

因此如果枚举所有的整数划分，则可以在 \Theta(np(n)) 的时间内解决本题。

注意 p(n) \sim \frac1{4n\sqrt 3}\exp \left(\pi \sqrt\frac{2n}3\right)，这是一个效率相当优秀的亚指数算法。