题解：P4769 [NOI2018] 冒泡排序

题意：定义一个排列是好的，当且仅当可以通过 \(\frac 1 2\sum_{i=1}^n|i-p_i|\) 次对相邻两个数的交换使得整个排列变成 \(1,2,\cdots n\)。给出一个排列 \(q\)，求有多少个排列 \(p\) 满足他是好的且字典序大于 \(q\)。

做法：

首先我们先思考没有字典序大于 \(q\) 这个事情怎么做。

我们尝试去给一个排列是好的一个更好描述的充要条件，我们注意到，每个数一定不能走回头路。对于一个数 \(x\)，如果有一个更大的数在他的前面，那么他必须向左走，否则向右的话这个数会被那个更大的数往左交换一次；如果有一个更小的数在他的后面，那他必须向右走。所以就要求这个排列里一定不能有长度 \(>2\) 的下降子序列，也就等同于该排列可以划分为不多于两个上升子序列。

那么就很容易想到一个 dp，\(dp_{i,j}\) 代表前 \(i\) 个数，并且目前的最大值为 \(j\)，后面有多少种方案，注意这里有个隐藏限制就是 \(i\le j\)。

考虑如何转移，有两种方式，一种是选一个更大的数，一种是选小于 \(j\) 的，但是注意，如果选择第二种，那么就一定得选当前最小的数，否则之后填的时候最小的数会形成一个长度至少为三的下降子序列。

所以 \(dp_{i,j} = \sum\limits_{k=j}^n dp_{i+1,k}\)。

我们发现这个东西非常像在网格图上移动，所以我们考虑也放到网格图上算路径数量，类似 Catalan 的计数方法，可以得到 \(dp_{i,j} = \binom{2n-i-j-1}{n-i-1}-\binom{2n-i-j-1}{n-j-1}\)。

然后就是考虑有排列的限制怎么做，我们枚举一个前缀相等，第 \(p\) 位不相等，我们记 \(mx = \max\limits_{i=1}^{p-1}q_i,mn\) 为目前还没用过的最小的数，那么讨论：

1. \(mn = q_p\)，那么就意味着我们这里只能填 \(>mx\) 的，不可以填比 \(mx\) 更小的数，答案为 \(\sum\limits_{i=mx+1}^ndp_{p,i}\)，注意到这个东西等于 \(dp_{p-1,mx+1}\) 可以预处理 \(O(1)\)。

2. \(mn<q_p<mx\)，此时还是可以填 \(>mx\) 的，但是因为这里填的不是 \(mn\) 但是又比 \(mx\) 小，所以 \(p+1,p+2,...n\) 这些位置因为有 \([1,p]\) 的前缀，再加上必须填 \(mn\)，就不合法了，之后的就可以直接跳过计算。

3. \(q_p \ge mx\)，那么这里只要填大于 \(q_p\) 的都可以。

按上述过程计算即可