nocriz的博客

苔花如米小,也学牡丹开。

[NOI2018]冒泡排序

一句话题意:给你一个长度为n的排列,求有多少长度为n的排列使得\sum_{i=1}^n\frac{|i-p[i]|}{2} =冒泡排序交换数。

n \le 600000, \sum n \le 2000000

首先,可以证明给出的条件就是要求排列中没有一个长度为3的下降子序列。如何证明?

打表是一种方法,但是我还想了一种证明方法:

首先,我们知道由于每一次冒泡排序交换都会减少一个逆序对,总的交换数目就是逆序对数目。那么,我们就需要和式的值等于逆序对个数。我们还可以把

考虑排列中的第i位的数字p[i],不妨设p[i]>i。我们把排列中大于p[i]的数字用1表示,其他数字用0表示,那么排列是这样的:

0 0 0 0 0 i 0 0 1 1 0 0 1 0

emmmmm大概就是说一共会有n-p[i]个1,p[i]-1个0。而且很显然,包含这个i的逆序对,仅仅是以i为左端点的就有右面的0那么多,就是p[i]-i那么多。如果i左边有1,右面的零就会更多,左边的1也可以和i形成逆序对,那么就会超出限制。这样我们就知道对于这个i所有左边的元素都小于它。再同理讨论p[i]<i和p[i]=i的情况,我们发现由于没有元素可以当下降子序列的中间的元素,显然是没有长度为3的下降子序列的。

下一步是将一个合法的子序列转化成一个括号序列。如何转化?

写出一个dp, [公式] 表示放了前 [公式] 个数,剩余的数中有 [公式] 个数比之前最大的数要大。显然就有两种转移,一种是放一个比之前最大的数要大的数,这个是有 [公式] 种放法。一种是放一个更小的数,因为这个更小的数后面的数都得比他大才行,所以必须是最小的数。有一个case是不能走第二种转移的,也就是 [公式] 的case。

如果我们考虑 [公式] 的话,相当于是二维平面上每次给 [公式] 加任意数,或者是给 [公式] 减1,并且不能越过 [公式] 的一个随机游走,没有限制的时候显然对应了长度为 [公式] 的括号序列,就是卡特兰数。

(上面两段段来自武弘勋的知乎回答

用语言不好描述,写一点python代码,证明留给读者(鸽)。

seq = ""
mx = 0
for i in range(1,n+1):
    if p[i]>mx:
        seq+="("*(p[i]-mx)
        mx = p[i]
    seq+=")"

然后可以证明这是一个一一对应的关系。

对于一个有着字典序限制的情况,可以遍历,枚举哪里超过了字典序,相当于固定了一个序列的前缀求方案数。这一步是一个经典问题,可以使用两个组合数相减来求值。

dbq,12点30分了,我不能写了,我好爬啊,希望我能做更多更好的题。

#include <bits/stdc++.h>


using namespace std;
typedef long long ll;
#define set0(x) memset(x,0,sizeof(x))
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()

ll chkmax(ll &a,ll b){return a = a>b?a:b;}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> VI;
template<typename T> void read(T &x){
	x = 0;char ch = getchar();ll f = 1;
	while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
	while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
	read(first);
	read(args...);
}
int mod = 998244353;
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int sq(int x){return 1ll*x*x%mod;}
int mpow(int a,int b){return b == 0 ? 1 : ( b&1 ? mul(a,sq(mpow(a,b/2))) : sq(mpow(a,b/2)));}
const int N = 1200000;
int fac[N+10],invfac[N+10];
int C(int n,int m){
	if(n<0 || m<0 || m>n)return 0;
	return mul(fac[n],mul(invfac[m],invfac[n-m]));
}
int C1(int n,int m){
	return sub(C(n,m+(n-m)/2),C(n,m+2+(n-m-2)/2));
}
int T,n;

void solve(){
	read(n);
	vector<int> a(n+1),vis(n+2,0);
	for(int i=1;i<=n;i++)read(a[i]);
	int mx = 0,mi = 0,cx = 0,cy = 0,ans = 0;
	for(int i=1;i<=n;i++){
		while(vis[mi+1])mi+=1;
		vis[a[i]] = 1;
		if(a[i]<mx && a[i]>mi+1){
			ans = add(ans,C1(2*n-(cx+1),cy+1));
			break;
		}
		if(a[i] == mi+1 && a[i]<mx){
			ans = add(ans,C1(2*n-(cx+1),cy+1));
			cx+=1;
			cy-=1;
		}else{
			int d = a[i]-mx;
			ans = add(ans,C1(2*n-(cx+d+1),cy+d+1));
			cx+=d+1;
			cy+=d-1;
		}
		mx = max(mx,a[i]);
	}
	cout<<ans<<endl;
}

int main(){
	fac[0] = 1;
	for(int i=1;i<=N;i++)fac[i] = mul(fac[i-1],i);
	invfac[N] = mpow(fac[N],mod-2);
	for(int i=N-1;i>=0;i--) invfac[i] = mul(invfac[i+1],i+1);
	read(T);
	while(T--){
		solve();
	}
	return 0;
}

评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注