自动搬运

查看原文

来自洛谷，原作者为

	Elegia irony

搬运于2025-08-24 22:00:40，当前版本为作者最后更新于2019-06-16 22:37:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一个基于杨表的暴力：

由杨表的构造过程可知，一个序列构建的杨表其第一行长度就是 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)$，这是一个效率相当优秀的亚指数算法。