题解 P4769 【[NOI2018]冒泡排序】

wu3412790 · 2019-03-19 18:51:42 · 题解

不知道大家是怎么做的，退役已久的老博士硬推了3小时。 首先分析一个排列P什么时候达到最少交换次数，按照下界的证明，每一次交换都应该使得\delta(P):=\sum_{i=1}^n |i-p_i|减少2，否则就并不能达到下界。

这样一来，我们可以观察到，如果p_i\leq i，那么这个数从始至终向右移动。类似地，如果p_i\geq i，这个数只能向左移动。所以如果p_i\leq i，那么p_i之前的数应该都比它小，否则会迫使p_i向左移动。同样，如果p_i\geq i，那么p_i之后的数都应该比他大。

这可以总结为，不存在三个指标i<j<k满足p_i>p_j>p_k，否则考虑p_j若p_j\geq j则它后面的数p_k比它大，若p_j\leq j则它前面的数p_i比它小，都将导致矛盾。反之如果排列中不存在三个下降的数，那么任意一次交换，必然都使得\delta(P)减少2，这是因为，如果我们交换了p_i和p_{i+1}，那么必有p_i>p_{i+1},这时由于不存在三个下降的数，应有p_i前的数都比它小，p_{i+1}后的数都比它大。所以i<p_i且，p_{i+1}<i+1，这表明这次交换使得\delta(P)减少了2。从而每一次交换都会使\delta(P)减少2，故交换次数达到了下界。

这样一来，我们面对的将是一个纯粹的组合问题，问字典序大于某个排列的排列中，有多少排列不包含长度为3的下降子序列，下文中将称这个性质为"漂亮的“。字典序的处理比较常规，只需要枚举从哪一位开始第一次大于给定串就可以，这样我们就需要处理如下子问题: 固定前缀的排列中，有多少个是“漂亮的”？

首先应判断前缀中是否有长度\geq 3的下降子序列，如果有，方案数为0，还需判断一下，剩下数中的最小者是否能和前缀中的两个数组成下降子序列，这些都可以用简单的前缀数组解决，属于基本功。

接下来，如果上述情况未发生，注意到前缀对我们的影响将只剩下前缀中的最大数，因为我们已经判断前缀中取两数或三数，无法组成下降子序列。所以问题进一步简化为，在m个数的排列中，如果第一个数是x，有多少这样的排列不包含长度为3的下降子序列？这个问题递归性明显，我们尝试建立递推式。以下记上述子问题的方案数为f(x,m)。

当x=m时，\{1,2,...,m-1\}都在m后面，所以他们必然是有序的，这样只有1方案，故f(m,m)=1。

当x=1,2时，后面的m-1个数不可能和x形成长度为3的下降子序列，故后面m-1的排列方案为\sum_{i=1}^{n-1} f(i,n-1)种，即长度为n-1的不包含长度为3的下降子序列的排列总数。

当3\leq x\leq n-1时，考虑x后第一个大于x的数，设它的位置为i\in \{2,...,x+1\}，大小是j\in \{x+1,...,m\}。注意到\{1,2,...,x-1\}在x之后，故他们在排列中必然有序，这表明第2到第i-1个数必然是1到i-2，这也说明了为什么i的取值范围是2到x+1。这样一来，前i个数对后面的影响，可以简化为一个j，这样就把方案数转化到子问题f(j-i+1,m-i+1)上。所以我们得到递推式:

，直接按照这个公式递推，复杂度较高，期望得分60分左右。 我们注意到f的相邻项之间存在大量重复，可将递推式简化为，

按照这个公式递推，可以得到80分。

想要得到满分，我们还需要进一步求出f的通项。观察上式，我们容易联想到组合数的递推关系，

于是我们试图将递推式往这个方向变形。令g(x,m)=f(m-x,m)，则我们可以得到g(x,m)=g(x-1,m)+g(x,m-1), 其中边界条件为g(0,i)=1以及g(j,i)=0,j\geq i。至此，递推式已经完全拥有的组合数的组合解释，考虑一个n\times m的方格，要从点(0,1)走到点(x,m)，每次只能向右或向下行走，且不能碰到对角线(即横坐标永远小于纵坐标，对应上面的边界条件

g(a,b)=C(a,a+b-1)-C(a-1,a+b-1)