AGC054C Roughly Sorted

题意：给定参数 。

对于一个长为 的排列 ，若满足下列条件，称之为好的。

• ，使得 且 的 的个数 。

对于排列 ，要用最少次数的相邻交换将 调整为好的。

现在我们知道了调整后的结果 ，问原来的 有多少种可能？答案对 取模。

。

---

这是一个经典的反映射计数问题，先考虑正映射。

记 为 前面 的数的个数。那么， 至少要参与 次向前的交换。

• 存在如下策略使得交换次数达到下界 。

  策略：不断找出 且 的 ，将 交换。

  正确性证明： 只需证当存在 时，也存在 使得 。

  考虑所有的后缀最小值，当存在 时，一定存在一个后缀最小值 满足 。

  找出一个 使得 是后缀最小值，但 不是（如果找不出，则说明 已排序），则必然满足 。

• 结论： 该策略得到的排列是唯一的。

  证明： 观察上面的策略，不难发现后缀最小值只会变为原来的超集（以数值而言），而不会减少。

  因此，后缀最小值向前移动时，不会互相越过。每个后缀最小值的移动都是独立的。

  所以，如果移动步数确定的话，最终得到的结果也是确定的。

接下来解决原问题。

对给出的 求出 ，若 则说明 有可能参与过向前的交换，若 ，则说明 不参与向前的交换。

对于每个可能移动的 ，其原来的位置可能是 的任何一个。

记 ，从大到小考虑 ，原来的位置有 种方案，答案为：

复杂度 。