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

~~一道绝好的打表找规律题。~~ 题目可以转化为：要求排列中不存在长度>=3的下降子序列。 因为如果出现的话，那么这个下降子序列中间的元素需要先与左边比它大的元素交换再与右边比它小的元素交换，需要折返一下，显然就不合法了。 这又等价于可以将序列划分为2个上升子序列。 首先我们先不看那个字典序的性质，~~相信大家打一下表就能~~发现答案是卡特兰数。 然后我们再想想它的本质是什么： 假设前i个位置中，最大的数是j，那么我们会发现，>j的数目前是可以随便填的，然而<j的数只能限制从小到大按顺序填入（因为这些元素一定被归入同一个上升子序列）。 于是我们就可以设f(i,j)表示还剩余i个数没填，其中后j个是大于当前最大值的“非限制元素”的答案。 转移就是枚举下一个位置填一个限制元素或某一个非限制元素。 如果填限制元素，非限制元素的数量不变；否则假设填入第k个非限制元素，非限制元素的数量就会减少k个（这是因为最大值发生了变化，使得前面k-1个非限制元素变成了限制元素）。 f(i,j) = sigma k=0~j f(i-1,j-k) 边界是f(0,0) = 1 这其实就是个前缀和： f(i,j) = f(i,j-1) + f(i-1,j) ~~擅长打表~~熟悉组合数的人会很快发现，这东西就是两个组合数相减： f(i,j) = c(i+j-1,j) - c(i+j-1,j-2) 它的正确性容易验证： f(i,j-1) + f(i-1,j) = c(i+j-2,j-1) + c(i+j-2,j) - c(i+j-2,j-3) - c(i+j-2,j-2) = c(i+j-1,j) - c(i+j-1,j-2) = f(i,j) 特别地，f(i,0) = 1,f(i,1) = i 这也解释了为什么没有限制时答案是卡特兰数：只需注意到此时的所求是f(n,n) f(n,n) = c(2×n-1,n) - c(2×n-1,n-2) = C(n) 我们再考虑限制，假设当前做到第i位，给定的排列中这一位是ai，后面有bi个数比它大，前面有ci个数比它小（这两个数组可以用树状数组方便地计算出来）并且现在的“非限制元素”还有nw个。 我们先计算填入的数字pi>ai的情况，然后再令pi=ai继续计算下一位。 首先nw可以与bi取个min，因为填完这一位后非限制元素一定不超过bi个。 然后此时如果nw=0（最大的数被填进去了）,则意味着我们后面将别无选择地只能按顺序填入，而这个排列的字典序是严格不大于给定排列的，因此就可以退出了。 否则，我们相当于要求sigma j=0~nw-1 f(n-i,j),根据前缀和它等于f(n-i+1,nw-1),可以O（1）计算。 然后，我们考虑填入pi=ai是否合法： 如果刚刚bi更新了nw，说明ai本身就是一个“非限制元素”，当然合法； 否则，如果ai是当前未填入的元素中最小的（对应ci==ai-1）,相当于填了一个最小的“限制元素”，也是合法的； 否则，就是乱序填入“限制元素”，不合法，就可以退出了。 总复杂度O(n log n),瓶颈其实在于树状数组求bi和ci的部分。 代码如下： ```cpp #include<bits/stdc++.h> using namespace std; int t,n,a[600010]; #define li long long #define gc getchar() #define pc putchar int read(){ int x = 0,c = gc; while(!isdigit(c)) c = gc; while(isdigit(c)){ x = (x << 1) + (x << 3) + (c ^ '0'); c = gc; } return x; } void print(int x){ if(x >= 10) print(x / 10); pc(x % 10 + '0'); } int tt[1200010]; void xg(int q){ for(int i = q;i <= n;i += i & (-i)) ++tt[i]; } int cx(int q){ int as = 0; for(int i = q;i;i -= i & (-i)) as += tt[i]; return as; } int b[600010],c[600010]; li jc[1200010],nj[1200010]; const int mo = 998244353; li ksm(li q,li w){ li as = 1; while(w){ if(w & 1) as = as * q % mo; q = q * q % mo; w >>= 1; } return as; } int mx1 = 1200005; inline li zh(li q,li w){ return jc[q] * nj[w] % mo * nj[q - w] % mo; } inline li wk(li q,li w){ if(w == 0) return 1; if(w == 1) return q; return (zh(q + w - 1,w) - zh(q + w - 1,w - 2) + mo) % mo; } int main(){ int i,j; jc[0] = 1; for(i = 1;i <= mx1;++i) jc[i] = jc[i - 1] * i % mo; nj[mx1] = ksm(jc[mx1],mo - 2); for(i = mx1 - 1;i >= 0;--i) nj[i] = nj[i + 1] * (i + 1) % mo; t = read(); while(t--){ n = read(); for(i = 1;i <= n;++i) a[i] = read(),tt[i] = 0; for(i = n;i;--i){ b[i] = n - i - cx(a[i]); xg(a[i]); c[i] = i - 1 - (n - a[i] - b[i]); } li as = 0;int nw = n; for(i = 1;i <= n;++i){ bool fg = b[i] < nw; nw = min(nw,b[i]); if(nw <= 0) break; (as += wk(n - i + 1,nw - 1)) %= mo; if(!fg && c[i] != a[i] - 1) break; } print(as);pc('\n'); } return 0; } ```