UOJ#394. 【NOI2018】冒泡排序

[我是原题](http://uoj.ac/problem/394)

题目等价于求最长下降子序列长度不超过$2$的排列个数，否则就不可能让冒泡排序在复杂度下限。

先想一个$dp$做法：设$f(i,j)$是放到了第$i$个位置，最大值为$j$的方案数。转移分两种：
1、填了一个更大的数$k$。这样的话显然是$f(i,j)\to f(i+1,k)$。
2、填了一个比$j$小的数$k$。看起来很不可做，实际上我们发现这个转移是唯一的——我们只能选择最小的那个填。否则最小的数一定出现在后面，那么一定出现了一个长度为3的下降子序列。那么有$f(i,j)\to f(i+1,j)$。
这就有了一个$O(n^2)$的优秀做法。

我们来思考这个$dp$的本质。
首先$dp$的合法状态是$i\le j$，也就是$i>j$的状态都无法到。
我们用格点表示坐标，黑色的是转移，每一个转移都只是累加，系数都是$1$。
![图片标题](https://leanote.com/api/file/getImage?fileId=5c1a21e6ab644128cd00042e)
考虑把每一条斜线都转化为向上走几步再向右的情况，实际$A$点表示的$dp$值等价于从$A$点走到$K$点的方案数。但是同时$i<j$的方案又是不合法的，也就是不能超过$y=x$这一条线。
不难发现，从终点出发来看，就是一个类似卡特兰数的东西，
从$(0,0)$走到$(a,b)$，只能走向右或向上，不经过直线$f(x)=x$的方案数，这个其实就是
$$\binom {a+b} a - \binom {a+b} {a-1}$$
这个的证明比较有趣，考虑每一个不合法方案，只要对每个方案找到第一个“向上出界”的步，将这一步以及前面的步全部取反(上对应右，右对应上)都是$(0,0)$到$(a+1,b-1)$的一条路径。所以用总的减不合法的。
现在我们解决了没有字典序限制的，考虑如何处理字典序限制。
发现直接枚举和要求字典序的前几位一样，就变成一个不带字典序的问题，比如上图，假设$B$点是限制点，那么我们计算一下$F,E,C,D$到$K$的方案的和就好了。
这个和一个可以用上指标求和化简，或者也可以通过观察发现，它们的和就是$H$到$K$的满足以上条件的路径的方案数。
于是$O(n)$枚举$O(1)$计算求和，总复杂度$O(n)$。

注意，边界可能不符合要求排列的性质，在枚举到不符合的时候$break$就好了。

```
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int maxn = 4e6 + 5;
const int mod = 998244353;
int step[maxn], inv[maxn], vis[maxn];
int n, up, ans, mx, t, mn;

void Add(int &x, const int &a) {
	x += a; if(x >= mod) x -= mod;
}

LL fpow(LL a, int b) {
	LL ans = 1;
	while(b) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod, b >>= 1;
	}
	return ans;
}

void pre(int n) {
	inv[0] = step[0] = 1;
	for(register int i = 1; i <= n; ++i)
		step[i] = 1ll * step[i - 1] * i % mod;
	inv[n] = fpow(step[n], mod - 2);
	for(register int i = n - 1; i >= 1; --i)
		inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}

int C(int n, int m) {
	return (1ll * step[n] * inv[n - m] % mod) * inv[m] % mod;
}

int way(int x, int y) {
	return (C(x + y, x) - C(x + y, x - 1) + mod) % mod;
}

int main() {
	scanf("%d", &t);
	pre(4000005);
	while(t--) {
		ans = 0, mx = 0, mn = 1;
		memset(vis, 0, sizeof(vis));
		scanf("%d", &n);
		register int i;
		for(i = 1; i <= n; ++i) {
			scanf("%d", &up), mx = max(mx, up);
			Add(ans, way(n - mx - 1, n - i + 1));
			if(up < mx && up != mn) 
				break;
			vis[up] = 1;
			while(vis[mn]) ++mn;
		}
		for(i = i + 1; i <= n; ++i) scanf("%d", &up);
		printf("%d\n", ans);
	}
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链