题解 P4769 【[NOI2018]冒泡排序】
LPA20020220
2018-12-19 13:53:55
提供一个复杂度为$O(N)$的题解。
证明已经基本上告诉我们了， 如果可以达到下界， 那么最长下降子序列的长度不能超过$2$， 否则由于要交换最小最大的两个元素中间的那个元素会多交换， 无法达到最优。
那么设$dp[i][j]$表示已选$i$个数放入序列， 其中最大值为$j$的方案数， 如果下一个可选的数比$j$大， 显然是合法的。 但如果下一个数比$j$小，为了保证最长下降子序列的长度不超过$2$， 显然应该选当前未选的元素中最小的一个， 因此这个转移是唯一的。所以$dp[i][j]$可转移至$dp[i+1][j+k](j+k\le n,k\ge 0)$。
把$(i,j)$视为一个点， 那么发现实际上我们要求的就是$(0,0)$到$(n,n)$且**不跨过**$y=x$这条直线， 始终保持在其上方的， 只能向右或向右上走的方案数。 这实际上就是$Catalan(n)$。
那么如果加上字典序限制怎么办呢？类似数位$dp$，我们可以先算一部分最高位比限制大的方案数， 这样之后的数位是不会受到影响的， 然后假设这位恰好为当前位限制的大小继续推下一位。
例如下面这个例子：
假设我们现在在考虑$E$处的限制， 那么其上面的三个点都不受后面字典序的限制。我们只需要求出这三个点只向右或向右上走到$D$点， 且不跨过$y=x$这条直线的方案数。 显然这个值也就等于$M$点到$D$点的方案数。
这个方案数怎么算？ 就是[这道题](https://www.luogu.org/problemnew/show/P1641)......预处理逆元， 阶乘即可$O(1)$计算。
另外， 注意如果我们强制卡满限制， 填数也是需要满足上面我们$dp$的要求的， 如果某次填入的限制比当前最大的限制小， 且不是最小的一个未填的元素， 直接$break$即可， 因为这样根本不能满足要求， 一定会在这一位选取到一个更大的数。
代码如下：
```cpp
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <algorithm>
#define R register
#define IN inline
#define W while
#define gc getchar()
#define MX 1205000
#define MOD 998244353ll
#define ll long long
template <class T>
IN void in(T &x)
{
x = 0; R char c = gc;
for (; !isdigit(c); c = gc);
for (; isdigit(c); c = gc)
x = (x << 1) + (x << 3) + c - 48;
}
template <class T> IN T max(T a, T b) {return a > b ? a : b;}
int fac[MX], inv[MX], bd[MX];
bool used[MX];
IN void pre()
{
fac[0] = fac[1] = inv[0] = inv[1] = 1;
for (R int i = 2; i <= 1200000; ++i)
{
fac[i] = 1ll * fac[i - 1] * i % MOD;
inv[i] = 1ll * inv[MOD % i] * (MOD - MOD / i) % MOD;
}
for (R int i = 2; i <= 1200000; ++i) inv[i] = 1ll * inv[i] * inv[i - 1] % MOD;
}
IN int C(R int n, R int m)
{
if (n < m) return 0;
return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
int main(void)
{
int T, n, lim, mn, mx, ans; pre(), in(T);
W (T--)
{
in(n); mx = ans = 0, mn = 1;
std::memset(used, false, sizeof(bool) * (n + 1));
for (R int i = 1; i <= n; ++i) in(bd[i]);
for (R int i = 1; i <= n; ++i)
{
lim = max(mx + 1, bd[i] + 1); used[bd[i]] = true;
if (lim <= n)
(ans += ((C(2 * n - i - lim + 1, n - i + 1) - C(2 * n - i - lim + 1, n - i + 2) + MOD) % MOD)) %= MOD;
if (mx < bd[i]) mx = bd[i];
else if (bd[i] != mn) break;
W (used[mn]) ++mn;
}
printf("%d\n", ans);
}
}
```