冒泡排序[NOI2018]

发表于 分类于

链接

loj

题解

显然我们需要分析一下达到交换次数下界的排列的充要条件。

如果有三个数 $a_i,a_j,a_k (i < j < k)$ 满足 $a_i>a_j>a_k$，那么这个排列一定不合法。因为 $a_j$ 至少要向右和向左都交换一次，那么这两次交换对这个 $a_j$ 是毫无意义的。

那么剩下的情况只有最长下降子序列长度不超过 $2$ 的情况。可以发现，这样的情况一定合法。

如果不考虑字典序的限制，只统计有多少个排列满足最长下降子序列长度不超过 $2$。

尝试DP，设 $f_{i,j}$ 表示考虑到第 $i$ 位，前缀最大值为 $j$ 的方案数。看看 $f_{i,j}$ 能转移到哪里去。显然 $f_{i+1,k}(k>j)$ 是一定可以的，且系数是 $1$。那么能否转移到 $f_{i+1,j}$ 呢？可以发现，如果你第 $i+1$ 位填的不是前 $i$ 位最小的没有出现过的正整数 $t$ 的话，后面一定会填上这个 $t$，此时 $j,a_{i+1},t$ 就会形成一个长度为 $3$ 的下降子序列了。因此 $f_{i,j}$ 给 $f_{i+1,j}$ 的贡献的系数为 $1$，且必须满足 $i+1\leq j$（不然就没数可填了）。

考虑这个 $f_{i,j}$ 的组合意义，显然是从 $(0,0)$ 开始走，每次可以往右边且纵坐标不比当前点小的格点走，不经过 $y=x-1$，走到 $(n,n)$ 的方案数。

用折线法容斥一下，把不经过直线的限制去掉。剩下的是一个组合数。

现在考虑字典序的限制。假设我们从第 $i$ 位开始打破字典序的限制，那么就相当于前面的情况，只不过不是从 $(0,0)$ 开始走罢了。

预处理组合数，枚举从哪一位开始打破限制就好了。注意及时break。

时间复杂度 $O(n)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=998244353;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
	y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
	return ans;
}
const int N=1200010;
ll fac[N],inv[N];
void init(int n)
{
	fac[0]=1; fo(i,1,n) fac[i]=fac[i-1]*i%mod;
	inv[n]=Pow(fac[n],mod-2); fd(i,n,1) inv[i-1]=inv[i]*i%mod;
}
inline ll C(int n,int m)
{
	if(n<0||m<0||n<m) return 0;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int n,p[N],mx,pos;
inline ll calc(int x,int y)
{
	return (C(2*n-x-y,n-y)-C(2*n-x-y,n-y-1)+mod)%mod;
}
bool vis[N];
ll ans;
int main()
{
	init(1200000);
	CASET
	{
		n=read();
		fo(i,1,n) p[i]=read(),vis[i]=0;
		mx=0; pos=1; ans=0;
		fo(i,1,n)
		{
			for(;vis[pos];pos++);
			ans=Add(ans,calc(i-1,max(mx,p[i])+1));
			if(mx>p[i]&&p[i]>pos) break;
			mx=max(mx,p[i]); vis[p[i]]=1;
		}
		printf("%lld\n",ans);
	}
	return 0;
}