[NOI2018]冒泡排序

一句话题意：给你一个长度为n的排列，求有多少长度为n的排列使得冒泡排序交换数。

首先，可以证明给出的条件就是要求排列中没有一个长度为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;
}