[NOI 2018]冒泡排序

题意：求所有字典序大于给定序列且满足条件的排列个数之和。

思路：

考虑dp即可，打表出卡特兰数优化，直接dp可以44...

#include <bits/stdc++.h>
using namespace std ;
#define int long long
const int mod = 998244353ull;
inline int pow(int x,int y) {
	int ret = 1;
	while(y) {
		if(y & 1) ret = ret * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return ret;
}
const 	int maxn = 6e6+10;
int fac[maxn<<1];
int ifac[maxn<<1];
inline int C (int x,int y) {
	return fac[x] * ifac[y] % mod * ifac[x - y] % mod;
}

inline int calc(int x,int y) {
	if(x < y) {
		return 0;
	}
	
	int d = (x << 1) - y;
	int res = C(d,x);
	if(x != y) {
		res = (res - C(d,x + 1))%mod;
	}
	return res;
}

inline void init() {
	fac[0] = 1;
	for(int i = 1;i <= maxn; ++i) {
		fac[i] = fac[i - 1] * i % mod;
	}
	ifac[maxn] = pow(fac[maxn],mod - 2);
	for(int i = maxn;i >= 1; --i) {
		ifac[i - 1] = ifac[i] * i % mod;
	}
}
int p[maxn];
int T,n;
bool vis[maxn];
signed main () {
	ios::sync_with_stdio(false);
	init();
	cin >> T;
	while(T--) {
		cin >> n;
		for(int i = 1;i <= n; ++i) {
			cin >> p[i];
		}
		memset(vis,0,sizeof(vis));
		int mx = 0;
		int mn = 1;
		int res = 0;
		int cnt = 0;
		for(int i = 1;i < n; ++i,cnt --) {
			if(p[i] > mx) {
				cnt += p[i] - mx;
			}
			mx = max(mx,p[i]);
			vis[p[i]] = 1;
			while(vis[mn] == 1) {
				mn++;
			}
			res += calc(n - i + 1,cnt + 1);
			res %= mod;
			if(mx > p[i] && p[i] > mn) break;
		}
		cout<<(res + mod) % mod <<endl;
	}
	return 0;
}