菜王的 blog

首先可以发现一个显然的结论，就是对于每一种排序操作，只有最后一次该操作是对最终序列有影响的，于是一个长度为 $m$ 的操作序列 $x$，我们把 $x$ 中所有非最后一次出现的元素删去得到长度最多为 $k$ 的操作序列序列 $y$，这两个操作序列是等价的。

我们考虑对合法的 $y$ 计数，然后考虑乘上一个系数表示每一个 $y$，能拓展出多少种长度为 $m$ 的 $x$。设这个 $y$ 的长度为 $l$，显然乘的系数就是第二类斯特林数 $\begin{Bmatrix}m\\l\end{Bmatrix}$（考虑把 $m$ 个位置划分为无序的 $l$ 组，按照每一组最靠后的位置顺序来给该组元素安排操作），可以用容斥 $O(k^2 \log m)$ 预处理。

现在只需要计数 $y$，考虑对于合法的 $y$ 有什么限制，显然最终只要满足每一个 $i$ 都满足 $b_i$ 都在 $b_{i + 1}$ 的前面即可。

对于每一个 $i$，都有一些位 $p$ 满足 $b_{i, p} < b_{i + 1, p}$，我们称这些位的集合为 $S_i$；还有一些位 $q$ 满足 $b_{i, q} > b_{i + 1, q}$，我们称这些位的集合为 $T_i$。则限制变成以下两种：

1. 对于每一个 $i$，$S_i$ 出现在 $y$ 序列内的最后位置一定后于 $T_i$ 出现在 $y$ 序列内的，否则 $b_i$ 会被排到 $b_{i + 1}$ 之后。

2. 对于所有原本 $b_i$ 在 $b_{i + 1}$ 后面的 $i$，$y$ 序列里必须出现至少一个 $S_i$ 内的元素。

这两种限制都可以简单处理，对于第一种限制，预处理 $bd_j$ 为选了集合 $j$ 的元素，接下来不能放在最前面的元素集合；对于第二种限制，预处理 $ce_j$ 为选了集合 $j$ 的元素，是否满足强制要求。

最后直接 DP 即可：设 $f_j$ 为包含元素为集合 $j$ 的 $y$ 序列方案数，转移则考虑枚举最前面新放了什么。

最终答案为：

$\sum_S ce_S \begin{Bmatrix}m\\|S|\end{Bmatrix} f_S$

时间复杂度为 $O(nk + k^2 \log m + k2^k)$，可以轻松通过。