Luogu4769 [NOI2018] 冒泡排序

题意：对于排列，记数值 原来的位置为 ，则相邻交换排序的交换次数有显然的下界 。

对于一个排列，若对其冒泡排序所需的交换次数达到上述下界，则称为好的。

求长度为 ，且字典序严格大于给定的排列 的好排列总数，答案对 取模。

多组数据，，，。

---

牛逼题。

Part1

考虑好排列的充要条件。

我们知道冒泡排序所需的交换次数达到下确界（每一步交换都是必须的），于是我们可以构造任意的交换方案。

每次交换我们都应当使 减少 （也至多减少 ），这样才可能符合条件。

若 ，则数值 只能向右移动（不能走弯路），若 ，则数值 只能向左移动。（充要）

因此，若 ，则 左侧的数都应该比 小。若 ，则 右侧的数都应该比 大。（充要）

进一步观察发现，这等价于要求不存在长度为 的下降子序列（三连降）。

• 必要性：若存在三连降，考虑中间的数 ，无论 还是 ，由于两侧都有不对的数，都不符合条件。

• 充分性：若 ，且我们要交换 ，此时 已经构成长度为 的下降子序列，于是 左侧不可能有 的数。

  类似地， 时也能保证正确性。

  显然交换不会中途产生三连降。

Part2

先不考虑字典序的限制。

用 来求解长为 的好排列的个数。

设 表示填写了前 个数，其中最大值为 的方案数。

下一步，若填更大的值，则必然合法。若填 的值，则必须填最小值，否则会产生三连降。

于是有转移 ：

利用差分，能发现 。

尝试编一个组合意义：路径。

• 当位于 时，可以前往 或 。但不能使得 。

先不考虑「不能使得 」的限制，从 到达 的方案数显然为 。

「使得 」等价于「达到直线 」。我们将不合法方案第一次触碰 之后的路径根据 翻转。

于是，不合法方案与「从 到 的路径」一一对应。

综上我们能得到 ：

Part3

接下来我们考虑字典序的限制。

枚举第一次不卡下界的位置，可以转化为：钦定一个前缀 ，且下一个数 的所有排列中，好排列的个数。

首先判一下填写这个数是否已经未被了上述 转移的限制。

记 ， 是不在 中的最小的数。

注意到总有 ，于是我们在这一位总是不能选择填 。

于是只能填比 大的数。

相当于将 置为 ，然后 求出 ，即为答案。

转化为下列问题 ：将 置为 ，然后 求出 。

考虑 的贡献系数，相当于从 走到 且不使 的方案数。

利用类似的技巧不难算得 ：

我们要求的是 ，不难发现其等于 。

复杂度 。