题意

求有多少个长度为 $n$ 的排列，使得 $S$ 为其长度为 $k$ 的字典序最大的子序列和其长度为 $k$ 的字典序最小的子序列的最长公共子序列之一。

题解

下文用 $T$ 代替 $S_0$，用 $R$ 代替 $S_1$。

性质一：考虑 $T$ 的形态，令 $i=\min\{i \mid i = k \lor T_i < T_{i+1}\}$，则 $T_1, T_2, \cdots, T_i$ 为 $p$ 字典序最大子序列长度为 $i$ 的前缀，$T_{i+1}, \cdots, T_k$ 为 $p$ 的长度为 $k - i$ 的后缀。

下称 $T_1, \cdots, T_i$ 为 $T$ 的头部，$T_{i+1}, \cdots, T_k$ 为 $T$ 的尾部。可以用类似的方式定义 $R$ 的头部与尾部。

容易发现 $S$ 唯一。考虑 $S$ 的形态。不妨令 $T$ 的尾部长度 $< R$ 的尾部长度。则 $T$ 的尾部一定是 $S$ 的一段后缀。删除这段后缀后，令 $R$ 尾部的剩下部分为 $p_l, \cdots, p_r$。则此时 $S$ 的一段后缀为有序集合 $\{p_i \mid i \in [l, r] \land p_i \in T \}$。删除这段后缀后，剩下的部分为两个头部的最长公共子序列。由于两个头部都是单调，因此 $S$ 剩下部分的长度至多为 $1$。

接下来可以考虑分类讨论开始 dp 计数了。

1. $S_1$ 为 $T, R$ 头部的一部分。

   对于 $S_1$ 前面的部分，我们要计数的问题是：有多少个长度为 $i$ 的排列，其字典序最大子序列的长度为 $j_1$，字典序最小子序列的长度为 $j_2$，且它们的最后一位一定是 $k$。发现 $\le k$ 的部分与 $\ge k$ 的部分是独立的，只需要分别 $dp$ 再组合数拼起来即可。现在的问题转换为：长度为 $i$ 的排列，其字典序最大子序列长度为 $j$，其最后一位和字典序最大子序列的最后一位为 $k$。这个容易用 $\Theta(n^3)$ 的时间复杂度 dp。

   对于 $S_1$ 后面的部分，不妨令 $S_2 < S_1$。则 $S_2$ 一定为 $R$ 的尾部。讨论 $T$ 的尾部是否比 $R$ 更长。

   1. $T$ 的尾部比 $R$ 的更长。

      则 $S_1$ 与 $S_2$ 之间必须存在数，且这些数都必须大于 $S_1$。对于 $S_2, \cdots, S_m$，其一定为原排列的一个后缀。这部分容易计数。

   2. T 的尾部比 R 的更短。

      令 $i = \min\{i \mid i = m \lor S_i < S_{i+1}\}$，则 $S_{i+1}, \cdots, S_m$ 为原排列的一个后缀。此时只需要对 $S_1$ 与 $S_i$ 之间的部分计数。此时问题转化成，有多少个长度为 $n'$ 的排列，其字典序最大子序列的长度为 $i$ 的前缀为 $S_1, \cdots, S_i$。这一部分也容易用 $\Theta(n^2)$ 或 $\Theta(n^3)$ 的时间复杂度 dp。

2. $S_1$ 为 $T, R$ 尾部的一部分。

   不妨令 $T$ 的尾部长度小于 $R$ 的尾部长度。则 $S$ 为 $T$ 的尾部。枚举 $R$ 的尾部长度与 $T$ 的尾部长度之差 $i$，再枚举 $T$ 的头部的最后一位 $p'$ 是多少。分开对 $p_1, \cdots, p'$ 和 $p', \cdots, S_1$ 计数。这两部分都可以用类似于 1 中对 $S_1$ 之前部分计数的方法计数。注意这个东西可以预处理，没有必要每枚举一次都重新计数一遍。

3. $S_1$ 为 $T$ 头部、$R$ 尾部的一部分或 $R$ 头部、$T$ 尾部的一部分。

   不妨令 $S_1$ 为 $T$ 头部、$R$ 尾部的一部分。

   $S_1$ 后面的部分与 1.2 相同。

   下面尝试对 $S_1$ 前面的部分计数。

   令 $k_2$ 为 $R$ 头部的最后一位，$k_1$ 为 $T$ 中 $S_1$ 前面的数。

   1. $S_1$ 为 $R$ 尾部的第一位。

      则 $S_1$ 的前一个数一定为 $k_1$。枚举 $k_2$，将 $\le k_2$ 的部分与 $> k_2$ 的部分使用类似于 1 中 $S_1$ 前面部分的方法分开 dp 计数。注意这个东西可以预处理，没有必要每枚举一次 $k_2$ 就重新 dp 一次。

   2. $S_1$ 不为 $R$ 尾部的第一位，且 $k_2 < S_1$。

      枚举 $k_2$，再枚举 $R$ 尾部在 $S_1$ 之前的长度，以 $k_2$ 或 $S_1$ 为界分开 dp，用上述方法仍然容易处理。

   3. $S_1$ 不为 $R$ 尾部的第一位，且 $k_2 > S_1$。

      这就要求 $k_2$ 必须在 $k_1$ 前面。注意到 $k_1$ 之后一定紧挨着 $R$ 尾部的第一位。枚举 $k_2$，再枚举 $R$ 尾部的第一位与 $S_1$ 之间有多少数，一样可以用类似的方法 dp。

总时间复杂度 $\Theta(n^3)$。

Bonus: $n \le 5000$。

瓶颈在于以下问题：有多少个长度为 $i$ 的排列，其字典序最大子序列的长度为 $j$。

设 $dp_{i,j}$ 为我们所希望求出的答案。每次尝试向已有排列中加入一个更小的数。如果这个数被放在了整个排列的最右边，则字典序最大子序列的长度会增加 $1$，否则不变。按照这个思路对 dp 式子进行转移，时间复杂度 $\Theta(n^2)$。

由于 $\Theta(n^2)$ 算法不仅要求对 dp 进行优化，还要求选手在分类讨论的过程中进行相当精细的实现，因此最终只开了 $n \le 400$ 来允许实现相对较差的算法通过。