【题解】[NOI2018] 冒泡排序 组合数学/卡特兰数 Loj2719 — Qiuly

千年大坑。

合法排列有什么性质

首先考虑排列如何达到交换下界。

单独的考虑排列中的一个数，对于其目标位置，容易发现每一次关于这个数的交换一定是朝着目标位置的方向换的。对于排列 $2,1$ ，$2$ 要到后面 $1$ 要到前面，所以交换不会浪费次数。但是如果在前面加上 $3$ ，$3$ 要到后面去，$2$ 位置不变，$1$ 要到前面去。

$3$ 往后面去的时候 $2$ 会往前走，$1$ 往前面去的时候 $2$ 又被搬回来，这样就浪费了交换次数。考虑一般情况，即排列中有 $a_i,a_j,a_k$ 满足 $i<j<k,a_i>a_j>a_k$ ，最终情况下 $a_i$ 一定是要到 $a_k$ 的后面的，$a_k$ 也一定是要到 $a_i$ 的前面，两者方向不同，中间的 $a_j$ 就会浪费交换次数。

所以如果当排列中出现了长度为 $3$ 甚至以上的子序列，并且满足子序列递减，那么排列不合法。

容易发现长度为 $2$ 甚至以下的递减子序列和其他递增子序列都不会浪费交换次数。

简单情况如何统计

首先考虑 $p_i=i$ ，也就是忽略字典序顺序。

设 $dp(i,j)$ 表示选了 $i$ 个数，最大值为 $j$ 的方案数。转移显然要么选一个更大的，要么选小于 $j$ 的数中最小的。

令小于 $j$ 的数中最小的数为 $a$ ，如果选了一个小于 $j$ 的数 $b$ 但 $a<b$ ，因为 $a$ 无论如何都要加入，也就只能以后加入，这样就形成了由 ${j,b,a}$ 组成的递减子序列。

转移式即：

$$dp(i,j)=\sum_{k=i-1}^{j} dp(i-1,k)$$

时间复杂度 $O(n^2)$ 。

如何快速求出 $dp$ 数组

观察 $dp$ 数组的转移式，会发现 $dp(i,j)=dp(i-1,j)+dp(i,j-1)$ 。

考虑将 $dp$ 搬到二维平面上，用点 $(i,j)$ 表示 $dp(i,j)$ 。每一次转移就是往前走一步或者往上走一步。但是不能出现 $j>i$ 的情况，转而言之就是不能越过 $y=x$ 这条直线，也就是不能触碰 $y=x-1$ 这条直线。

这是一个经典的套路：首先令按照上述方式走，没有直线限制走到点 $(i,j)$ 的方案数为 $f(i,j)$ 。

那么 $dp(i,j)$ 就是 $f(i,j)$ 减去非法情况。考虑将第一次触碰直线 $y=x-1$ 的点后面的路径按照直线 $y=x-1$ 翻转，也就是终点变成了 $(j+1,i-1)$ ，这样就可以得到：

$$dp(i,j)=f(i,j)-f(j+1,i-1)$$

现在考虑 $f(i,j)$ 如何求。

可以往左走也可以往上走，显而易见的有：

$$f(i,j)={i+j \choose i}$$

时间复杂度 $O(1)$ ，预处理要 $O(n)$ 。

对于另外一种处理 $dp$ 数组的想法

按照原来的 $dp$ 转移式子，同样放到二维平面来考虑。

直线的限制是一样的，同样的设没有直线限制走到点 $(i,j)$ 的方案数为 $g(i,j)$ 。现在需要考虑 $g(i,j)$ 如何求。

现在一共是走了 $i$ 步，然后每一步的步长总和为 $j$，步长可以为 $0$ 。可以转化为一共 $i$ 个盒子，$j$ 个小球，可以空盒子的方案数。于是就可以得到：

$$g(i,j)={i+j-1 \choose i-1}$$

需要注意的是，由于在这种情况下只能” 横着走”，即每一步 $i$ 必须加 $1$ 。从 $(0,0)$ 到 $(j+1,i-1)$ 的” 竖着走” 的方案数。对应过来就是到 $(i-1,j+1)$ 的” 横着走” 的方案数。

（不会玩，暂时留坑

字典序问题如何处理

（不知道为啥卡这卡好久 …（于是开始钻研题解 ×

比较容易的一个方法就是枚举位置 $i$，前 $i-1$ 个数都和 $p$ 的对应位置相同，第 $i$ 个数大于 $p_i$ ，然后将方案数加起来。

令 $mx=\max_{j=1}^{i-1}p_j$，$mi$ 为当前最小的可以填的数，讨论第 $i$ 位的方案。

重新定义 $dp$ ：表示点 $(i,j)$ 到 $(n,n)$ 的方案数。

• 如果 $p_i=mi$
  • 填 $mi$ 显然不合法。
  • 填一个满足 $mi<x<mx$ 的数 $x$，因为如果将 $mi$ 留到后面就会形成 ${mx,x,mi}$，不合法。
  • 填一个满足 $x>mx$ 的数 $x$，方案数为 $dp(i,mx+1)$ 。
• 如果 $mi<p_i<mx$
  • 只能填满足 $x>mx$ 的数 $x$，方案数为 $dp(i,mx+1)$ 。
  • 当接下来处理 $i+1$ 时，由于第 $i$ 位填了 $p_i$ ，前面一定形成了 ${mx,p_i}$，而还有小于 $p_i$ 的元素没有填，接下来一定不存在合法方案了。
• 如果 $p_i\geq mx$
  • 填一个满足 $x>p_i$ 的数 $x$，方案数为 $dp(i,p_i+1)$ 。

时间复杂度 $O(n)$ 。

Code

const int N=2e6+5;
int n=2e6,p[N],vis[N],fac[N],inv[N];

inline int C(int n,int m) {
    if(n<m||n<0||m<0) return 0;
    return mul(fac[n],mul(inv[m],inv[n-m]));
}
inline int dp(int i,int j) {
    if(i>j||j>n) return 0;
    return dec(C((n<<1)-i-j,n-i),C((n<<1)-i-j,n-i+1));
}

int main() {
    fac[0]=1;
    for(int i=1;i<=n;++i) fac[i]=mul(fac[i-1],i);
    inv[n]=modpow(fac[n],mod-2);
    for(int i=n;i>=1;--i) inv[i-1]=mul(inv[i],i);

    int T=int(IN);while(T--) {
        IN(n);
        for(int i=1;i<=n;++i) IN(p[i]),vis[p[i]]=0;

        int mx=0,mi=1,ans=0;
        for(int i=1;i<=n;++i) {
            chkmax(mx,p[i]),pls(ans,dp(i-1,mx+1)),vis[p[i]]=true;
            while(vis[mi]) ++mi;
            if(mi<p[i]&&p[i]<mx) break;
        }
        printf("%d\n",ans);
    }
    return 0;
}