Insertion Sort ICPC 2018 Shenyang R

WZH2026-09-132026-09-13

[ICPC 2018 Shenyang R] Insertion Sort

题目描述（简化版）：

经过原题面转化。

给定 $n,k,P$ ，求所有长度 $n$ 的排列中，将前 $k$ 个排好序之后最长上升子序列至少为 $n-1$ 的方案数。对 $P$ 取模。

首先考虑前 $k$ 个的分布。

前 $k$ 个数恰为 $1\sim k$ 。

此时只需后面 $k+1\sim n$ 的最长上升子序列至少 $n-k-1$ 即可。

易知方案数为 $k!\times ((n-k-1)^2+1)$ 。

前 $k$ 个数恰为 $1\sim k+1$ 中 $k$ 个（不包括 Case #1 ）。

此时只需后面 $k+2\sim n$ 有序。

所以此时我们需要将前 $k$ 个位置的数乱序，并枚举 $1\sim k$ 中谁不在前 $k$ 个位置中。这个枚举的数可以放在 $k+1\sim n$ 中任意位置。所以方案数为 $k!\times k(n-k)$ 。

前 $k$ 个数恰为 $1\sim k$ 剔除一个并加入 $k+2\sim n$ 中任意一个。

此时前面随意排序，后面必须有序。

于是方案数为 $k!(n-k-1)$ 。

然后就没了。