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

让我们来尝试理性理解一下这道题 其实这道题的难点就是两个神仙的转化,理解这两个转化之后做这道题就不难了 ______________ ### 前置芝士:一颗冷静的头脑和一张草稿纸 计数题的代码不一定长但是思维难度一定不小，建议不懂的地方画图理解 ### 前置芝士:树状数组 ~~那个，做noi题真的不会树状数组吗？~~ ___________________ ## 本题题解 首先我们先来证明一个结论，题目中实际上是要求我们求出符合下列条件的排列个数 **1.这个排列的字典序严格大于输入的排列** **2.这个排列不含有长度超过3的下降子序列** 那么条件1十分好说，就是题目要求 问题来了条件2呢？我们需要证明两件事情: 第一就是如果这个排列含有长度超过3的下降子序列那么这个排列一定非法 第二就是如果这个排列不含有长度超过3的下降子序列那么这个排列一定合法 #### 先来尝试着证明第一点: 根据题目中给出证明我们可以知道，一个排列是合法的当且仅当我们在交换两个位置$(i,i+1)$的时候满足$a(i)>i,a(i+1)<i+1$，换句话说我们不会做出把这个数字向与最后位置相反的方向移动的行为 假设这里有3个元素从左到右值分别为$a,b,c$并且$a>b>c$ 那么在最后排好序的排列当中这三个元素的位置必须是$c,b,a$ 那么我们知道冒泡排序只能交换相邻的两个元素，那么必然存在一个时刻这个三个元素长这样$b,a,c$或者是$a,c,b$ 问题来了我们迟早要把三个元素变成$c,b,a$的，这就意味着b这个元素向两个不同的方向移动了，无论b的初始位置在哪里也无论b的目标位置在哪里b元素总是会浪费几步，因此这个排列就非法了 ### 接着证明第二点: 可以观察出一个事实就是如果这个排列不含有长度超过3的下降子序列那么这个排列一定可以被拆分成两个或者一个上升的子序列，构造方法如下: 对于每一个位置i，**如果这个数字是$(1,i)$的前缀最大值**，就将这个数字丢到第一个子序列当中,否则将这个数字丢到第二个子序列当中 显然第一个子序列肯定是单调的，现在我们需要证明为什么第二个子序列单调 采用反证法，如果第二个子序列不单调那么存在一对位置$(i,j)$满足i在j的前面但是i却比j大。 那么我们知道$i$肯定是小于$(1,i)$的前缀最大值的，因此$(1,i)$的前缀最大值,$i$,$j$构成了一个长度为3的下降子序列，与假设不符，所以第二个子序列也是单调的 接下来我们证明为什么我们的排列不含有长度超过3的下降子序列这个排列一定合法 首先我们知道冒泡排序只交换相邻的逆序元素，那么我们可以轻松的得到一个事实是这个排列在冒泡排序的任意时刻都不含有长度超过3的下降子序列 接下来我们证明两件事情，如果$i$属于第一个子序列那么$i \leq a(i)$ 这其实十分的显然因为$a(i)$是前缀最大值 另一件事情不怎么平凡，如果$i$属于第二个子序列那么$a(i) < i$ 证明其实也比较简单考虑$(1,i)$的权值的分布，比如说可能长这样  其中红色点表示这个值属于第一个子序列而蓝色点表示这个点属于第二个子序列，白色点表示这个权值不在$(1,i)$这个权值当中出现 然而打叉的那种权值分布是不可能出现的，因为蓝色点的位置是单调的红色点的位置是单调的，一共只有n种权值，如果蓝色点之间有白色点，那么后面将没有权值可以填上白色的空隙， 所以我们可以知道:如果i是第二个子序列的数字，那么$a(i)<i$ 因为既然出现了第二个子序列,那么$(1,i)$当中一定有红色点在最大的蓝色点前面 那么接下来的事情就十分简单了，我们冒泡排序的时候交换的元素$(i,i+1)$属于两个不同的子序列并且$i$属于第一个而$i+1$属于第二个子序列，根据刚才证明的两个结论我们可以推出交换的每一步都是合法的 好了千辛万苦我们终于证明了这个结论是对的 接下来我们把精力集中在第一个限制上，也就是字典序严格大于$p$这个条件上，显然我们需要枚举目标排列和p的lcp长度 假如我们钦定了lcp长度恰好为$i$那么我们发现$a(i+1)>p(i+1)$并且$p$的前i位是合法的，并且我们还需要满足一件事情是$(i+1,n)$当中所有比$(1,i)$中最大值小的数字必须有序，否则不行 那么我们不妨设计一个$dp(n,k)$表示长度为$n$以$k$开头的合法排列数量 我们会有一个神奇的转移方程 $$dp(n,k)=\sum_{i=\max(1,k-1)}^{n-1}dp(n-1,i)$$ 哇这个转移方程真的肥肠神仙啊 让我们来尝试理解它 #### case1:排列以1开头 如果这个排列以1开头那么1不可能出现在下降子序列当中，所以后面随便什么开头都行 #### case2:排列以k开头 此时如果我们发现下一位比k小的话,$(k,\text{下一位},1)$会构成一个长度为3的下降子序列此时我们gg了 如果更加不巧，我们下一位填了1,那么其实等价于这样一个要求:对于剩下的元素如果这些元素比k小，那么这些元素之间必须有序 似乎这个限制也在枚举字典序的要求当中出现了啊，让我们康康有没有什么办法可以处理它 然后我们仔细观察一下发现还真的有…… 那就是符合上面要求的排列个数恰好等于$dp(n-1,k-1)$ 证明是这样的，我们要求$(1,k-1)$这些元素有序的要求相当于不存在一对$(i,j),i<j$使得$j$排在$i$的前面 那么我们令$(1,k-1)$当中值为i的元素挪到值为i+1的元素上，k-1挪到1的位置上，我们发现如果刚才非法的$(i,j)$对中不含1那么做这样的变换之后$(k-1,i-1,j-1)$构成了一个长度为3的下降子序列 如果刚才的非法的$(i,j)$对中含1,这显然是不可能的因为原序列当中1排在序列的开头 所以我们转移的方程就真了 好了那么我们处理字典序限制时候也可以如法炮制 事实上我们的答案就是这些数字加起来 对于输入的排列当中的每一个位置$i$假设在$(i,n)$当中有$k$个数字比$(1,i)$的前缀最大值小,那么答案加等于 $$\sum_{t=k+1}^{n-i+1}dp(n-i+1,t)$$ 证明方式也是类似的，如果$P(i)$就是前缀最大值那么为了满足字典序限制，我们需要满足这一位排列的开头在离散化之后比$P(i)$大 如果$P(i)$不是前缀最大值那么根据刚才的结论我们会发现开头必须必前缀最大值大否则(前缀最大值,当前位,后缀最小值)构成一个长度为3的下降子序列 然后我们仔细想想会发现这一位是不能填后缀最小值的，因为后缀最小值是小于等于$P(i)$的,填了我们就不满足字典序限制了 ### 求出dp数组的后缀和 好了现在我们来解决最后一个问题，$O(1)$的求出这个式子 $$\sum_{t=k+1}^{n-i+1}dp(n-i+1,t)$$ 哇，好棒哎，我们现在只能$O(N^2)$的刷出dp数组的每一个值您现在让我$O(1)$求出后缀和？ 没关系啊我们使用最常见的套路求什么设什么为了方便起见我们令$dp(n,0)=0$这样可以规避掉诡异的下界问题 $$s(n,m)=\sum_{i=m}^{n}dp(n,i)$$ $$dp(n,i)=\sum_{k=i-1}^{n-1}dp(n-1,k)$$ $$s(n,m)=\sum_{i=m}^{n}\sum_{k=i-1}^{n-1}dp(n-1,k)$$ 接下来该会会我们的老朋友交换求和号了 $$s(n,m)=\sum_{k=m-1}^{n-1}dp(n-1,k)\sum_{i=m}^{k+1}1$$ 让我们稍微倒腾一下求和上下界 $$s(n,m)=\sum_{k=m-1}^{n-1}dp(n-1,k)+\sum_{k=m}^{n-1}dp(n-1,k)\sum_{i=m+1}^{k+1}1$$ $$s(n,m)=s(n-1,m-1)+\sum_{i=m+1}^{n}\sum_{k=i-1}^{n-1}dp(n-1,k)$$ $$s(n,m)=s(n-1,m-1)+s(n-1,m+1)$$ ~~不要觉得上面的推倒很简单，请自己交换几次求和号康康自己能不能不把求和上下界搞对~~ 哇，我们搞出了一个关于后缀和的递推式！ 边界条件$s(0,0)=1$ 那么我们发现其实s数组是有实际意义的 也就是从$(0,0)$到$(n,m)$每次可以向上走一步或者向右再向下走一步，中间不能经过x轴之下的方案数 那么我们发现单独向上走一步实在是不优美…… 不如这样，我们每次向上走一步的时候接着向右走一步，这样$s(n,m)$就是从$(0,0)$走到$(2n-m,m)$的方案数 那么我们需要从$2n-m$步当中选出n-m步来走，这一步的方案数就是 $${2n-m\choose n-m}$$ 对于一个不合法的方案也就是触碰了y=-1的方案，我们将第一次触碰y=-1之前的操作全部取反，向上走改成向下走，我们向下走的总步数变为n-m-1,这部分的方案数为 $${2n-m \choose n-m-1}$$ 这样我们得到了 $$s(n,m)={2n-m \choose n-m}-{2n-m \choose n-m-1}$$ 然后就可以$O(1)$计算辣~ 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std;const int N=6*1e5+10;typedef long long ll;const ll mod=998244353; ll fac[N<<1];ll ifac[N<<1];int n;int T;int a[N];int mi[N]; inline ll c(int n,int m){return (m>=0)?(fac[n]*ifac[m]%mod*ifac[n-m]%mod):0;} inline ll s(ll n,ll m){if(m>n)return 0;return (c((n<<1)-m,n-m)+mod-c((n<<1)-m,n-m-1))%mod;} struct treearray { int ta[N]; inline void c(int x,int t){for(;x<=n;x+=x&(-x))ta[x]+=t;} inline int q(int x){int r=0;for(;x;x-=x&(-x))r+=ta[x];return r;} inline void clr(){for(int i=1;i<=n;i++)ta[i]=0;} }ta; inline void solve()//直接按照推出的式子模拟即可 { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=n;i>=1;i--)ta.c(a[i],1); mi[n]=a[n];for(int i=n-1;i>=1;i--)mi[i]=min(mi[i+1],a[i]); int mx=0;int cmx=0;ll ans=0; for(int i=1;i<=n;i++)//注意判断前缀是否是合法的 { if(cmx>mi[i])break;(ans+=s(n-i+1,ta.q(max(mx,a[i]))+1))%=mod; if(a[i]<mx)cmx=max(cmx,a[i]);mx=max(mx,a[i]);ta.c(a[i],-1); }printf("%lld\n",ans); } inline void clr(){ta.clr();} int main() { fac[0]=1;for(int i=1;i<=(N<<1)-10;i++)fac[i]=fac[i-1]*i%mod; ifac[0]=1;ifac[1]=1;for(int i=2;i<=(N<<1)-10;i++)ifac[i]=(mod-mod/i)*ifac[mod%i]%mod; for(int i=1;i<=(N<<1)-10;i++)(ifac[i]*=ifac[i-1])%=mod; scanf("%d",&T);for(int z=1;z<=T;z++)solve(),clr();return 0;//拜拜程序~ } ```