【学习笔记】「NOI2018」冒泡排序

从题解的角度来说，这是一道简单题。不过考场上在没有任何人提示的情况下要想出正确的结论其实并不容易。

我自己做这道题的时候，因为没有想清楚题目给出的下界能取到的充要条件是什么，所以到了很晚才猜到结论，以至于难以为继。

结论：当且仅当一个排列不含有长度为$3$的下降子序列，冒泡排序的交换次数取到下界。这也非常好理解，因为如果一个位置存在前面一个数比它大，后面一个数比它小，那么至少会向左/向右移动一次，因此取不到下界。

证明需要运用$\text{Dilworth}$定理，我们可以把原序列划分成两个上升子序列 ，其中一个子序列的数只会往左移，另一个子序列的数只会往右移，然后就证完了。

先不考虑字典序的限制。我们将限制转化一下，变成不存在一个位置$i$，使得存在前面的一个数比它大，后面的一个数比它小。这直接导出了下面的$dp$：设$d{p}_{i,j}$表示前$i$个位置，最大值为$j$的方案数。如果$[1:i-1]$的最大值为$j$，那么$p_i$只能是$[1:j]$中没填的最小的那一个，方案数$d{p}_{i-1,j}$。否则，若$[1:i-1]$最大值为$k(k<j)$，那么$p_i$填$j$总是合法的。那么，$d{p}_{i,j}={\sum }_{k\le j}d{p}_{i-1,k}(i\le j)$ 。我们发现这就是从$(1,1)$走到$(n,n)$且不穿过对角线$x=y$的方案数，也就是$\left(\genfrac{}{}{0ex}{}{2n}{n}\right)-\left(\genfrac{}{}{0ex}{}{2n}{n-1}\right)$。

回到原题，我们枚举$\text{lcp}$，然后就变成了求从$(i,j)$走到$(n,n)$的方案数，同样可以组合数计算。然后就做完了。

复杂度$O(n)$。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int mod=998244353;
const int N=2e6+5;
int T,n,p[N],vs[N];
ll fac[N],inv[N],bit[N],res;
void add(ll &x,ll y){x=(x+y)%mod; 
}
ll fpow(ll x,ll y=mod-2){ll z(1);for(;y;y>>=1){if(y&1)z=z*x%mod;x=x*x%mod;}return z;
}
void init(int n){fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;inv[n]=fpow(fac[n]);for(int i=n;i>=1;i--)inv[i-1]=inv[i]*i%mod;
}
ll binom(ll x,ll y){return fac[x]*inv[y]%mod*inv[x-y]%mod;
} 
ll G(int a,int b,int c,int d){if(c>=a&&d>=b)return binom(c+d-a-b,c-a);return 0;
}
ll F(int a,int b,int c,int d){if(c>=a&&d>=b&&b>=a){return G(a,b,c,d)-G(b+1,a-1,c,d);}return 0;
}
int main(){    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);init(2e6);cin>>T;while(T--){cin>>n;for(int i=1;i<=n;i++)cin>>p[i],vs[i]=0;res=0;int tp=0,j=1;for(int i=0;i<n;i++){add(res,F(i,max(tp,p[i+1])+1,n,n));while(j<=n&&vs[j])j++;if(j<tp&&j>p[i+1]){add(res,F(i+1,tp,n,n));}if(p[i+1]<tp&&p[i+1]!=j){break;}tp=max(tp,p[i+1]);vs[p[i+1]]=1;}cout<<(res+mod)%mod<<"\n";}
}