我们先来考虑，好的排列满足什么性质。不难发现，如果这个排列的最长下降子序列长度大于 2，那么这个排列一定不是好的排列，设不满足的 3 个数为 \(c,b,a(c>b>a)\)，那么 \(c\) 要移到 \(b\) 的右面，一定会和 \(b\) 交换一次，然后 \(a\) 和 \(c\) 再交换一次，这时变成了 \(b,a,c\)，还需要额外交换一次。现在我们再来证明一下这个条件也是充分条件：
我们发现，如果要保证这个排列是好的排列，我们改变任何一个数的位置的时候，都需要让它往它应该在的位置移动，也就是说，如果 \(p_i<i\)，那么 \(p_i\) 一定只会向左移动，\(p_i>i\) 同理，当 \(p_i=i\) 时，这个位置不能移动，反之，如果不是好的排列，至少有一次交换使得某一个数距离它应该在的位置变远了。
考虑任何一次交换，设我们交换的数为 \(p_i\) 和 \(p_{i+1}\)，那么我们有 \(p_i>p_{i+1}\)，由不存在长度为 3 的下降子序列我们可知 \(p_1\dots p_{i-1}<p_i\)，\(p_{i+2}\dots p_n>p_{i+1}\)，这样就有 \(p_{i+1}<i+1\)，\(p_i>i\)，故这一次交换两个数都往应该走的方向走了，显然这样的交换不会增加最长下降子序列的长度。
这样我们就证明了不存在长度为 3 的最长下降子序列是好的排列的充要条件。
现在我们考虑计算方案数。我们先忽略字典序的限制，即让 \(p_i=i\)，设 \(f(i,j)\) 为填了前 \(i\) 个位置，填过的最大的数为 \(j\) 的方案数，我们先给出递推式： \[ f(i,j)=\sum\limits_{k=i-1}^jf(i-1,k) \] 这个的意思是，如果我们现在填的数比之前都大，显然不会造成影响，所以可以任意填一个比当前最大值大的数；如果我们现在填的数比之前小，那么一定只能填没有填过的最小的数，因为如果填了一个不是最小的数，迟早要把最小的数填上，这样就构成了一个长度为 3 的下降子序列。不难证明按照这样填也一定不会出现长度为 3 的下降子序列（考虑反证，第三个数一定是最小的数转移的，如果在之前已经存在了长度为 2 的下降子序列，那说明填第二个数的时候填的不是当前最小值）。
然后我们可以改写一下 dp 的转移方程。 \[ f(i,j)=f(i,j-1)+f(i-1,j) \] 且 \(f(i,j)=0,j<i\)。
我们发现，这等价于在平面直角坐标系中，只能向右或向上走，从 \((0,0)\) 走到 \((i,j)\)，且一直在直线 \(y=x\) 上方的方案数。我们要求的是 \(f(n,n)\)，这个的方案数便是卡特兰数 \(C_n\)。
现在我们要把字典序的限制加上，经典的处理方法是枚举实际排列和要求排列的 LCP。我们假定在第 \(i\) 位实际排列和要求排列不同，那么我们这一位一定比之前大。设从第 \(i+1\) 位开始不同，前 \(i\) 位中最大值为 \(mx\)，那么方案数就是 \((i-1,mx+1)\) 到 \((n,n)\) 一直在 \(y=x\) 下方的方案数。这实际上是卡特兰数的一个扩展，可以发现所有跨过 \(y=x\) 的路径都经过了 \(y=x-1\)，所以对这些路径关于 \(y=x-1\) 对称，这样就等价于 \((i-1,mx+1)\) 到 \((n+1,n-1)\) 的方案数，这样的总方案数为 \(\dbinom{2n-i-mx}{n-i+1}-\dbinom{2n-i-mx}{n-i+2}\)。
需要注意的是如果给定的排列某一位比前缀最大值小，而且这一位并不是剩余的最小值，这样后面全部不合法，需要直接 break 掉。
代码：
1 |
|