[NOI2018]冒泡排序

发表于

难度

思维难度 : 四星

代码难度：一星半

标签

计数 + 组合意义 + dpdp

题解

考虑什么样的排列是不好的排列。

显然，一个排列是不好的排列当且仅当存在一次交换，使一个数远离它的目标位置. 考虑三种情况.

  1. pi>ip_i > i 即目标位置在原位置右侧.
  2. pi<ip_i < i 即目标位置在原位置左侧.
  3. pi=ip_i = i​​ 即目标位置与原位置重合.

对于情况一，当这个数左侧有一个比它大的数时，才会使它远离原位置， 因为 pi>ip_i > i​ 所有右侧一定存在一个点满足 pj<pi∧j>ip_j < p_i \land j > i​

对于情况二，当这个数右侧有一个比它小的数时，才会使它远离原位置， 因为 pi<ip_i < i​​ 所有左侧一定存在一个点满足 pj>pi∧j<ip_j > p_i \land j < i​​

对于情况三，当这个数左侧有一个比它大的数时，才会使它远离原位置，那么相应的，右侧一定有一个比它小的数。

综上所述，一个排列是不好的排列，仅当在这个排列中存在一个长度等于 33​​​​ 的下降子序列. （必要性)

接下来考虑充要性. 即如果这个排列中存在一个长度等于 33 的下降子序列， 那么这个排列一定是不好的排列.

如果存在一个长度等于 33​​ 的下降子序列，考虑中间的点，它在和比它小的数交换时向右移，和比它大的数交换时向左移。那么对它而言，一定有一次会使它远离目标点。得证

所以一个排列是好排列当且仅当这个排列中不存在一个长度等于 33​ 的下降子序列.

那么怎么求不存在一个长度等于 33 的下降子序列的序列个数呢？

那么对于位置 ii​ ，有两种选择，要么放一个比放过的数的最大值大的数，要么放当前没有放的最小值。

考虑 dpdp , 设 f[i][j]f[i][j] 表示 dpdp 到第 ii 个位置， 放过的数的最大值为 jj .

那么 f[i][j]+=f[i−1][k](j≥k)f[i][j] += f[i - 1][k] (j \geq k) ， j=kj = k 表示放当前没有放的最小值, j>kj > k 表示放 jj .

考虑它的组合意义，实际上就是在一个网格图上，以当前位置为横坐标，放过的数的最大值为纵坐标，从 (0,0)(0, 0) 走到 (n,n)(n, n) ，可以向正右走，也可以向斜右上走 (角度不一定是 45045^0 )，问方案数。注意到放过的数的最大值不能小于当前位置，即 j≥ij \geq i , 所以路径不能越过对角线。

可以向正右走，也可以向斜右上走，可以拆解成先向上走大于等于 00 步，再向右走 11 步。

那么这就是最基本的格路计数问题，在没有字典序限制的情况下，答案就是卡特兰数。

考虑解决字典序的问题，这不难解决。像解决数位 dpdp​​​​​​​​​ 一样，枚举从哪一位开始超过字典序。设 aia_i​​ 表示 max⁡j=1iqj\max_{j=1}^i{q_j}​​ 那么方案数为 ∑j=ai+1n(n−i+n−jn−i)−(n−i+n−jn−j−1)\sum_{j=a_i+1}^{n}\tbinom{n - i + n - j}{n - i}-\tbinom{n-i+n-j}{n-j-1}​​​​​​​

两部分分开求

∑j=ai+1n(n−i+n−jn−i)=∑k=0n−ai−1(n−i+kn−i)用k代替n−j=(n−i+n−ain−i+1)上指标求和\begin{aligned} &\quad\sum_{j=a_i+1}^{n}\tbinom{n - i + n - j}{n - i}\\ &=\sum_{k=0}^{n-a_i-1}\tbinom{n - i + k}{n - i}\quad 用k代替n-j\\ &=\tbinom{n - i + n - a_i}{n - i + 1} \quad 上指标求和\\ \end{aligned}

\begin{aligned} &\quad\sum_{j=a_i+1}^{n}\tbinom{n-i+n-j}{n-j-1}\hfill\\ &=\sum_{j=a_i+1}^{n}\tbinom{n-i+n-j}{n-i+1}\hfill\\ &=\sum_{k=n-i}^{n-i+n-a_i-1}\tbinom{k}{n-i+1}\quad用k代替n-i+n-j\hfill\\ &=\sum_{k=0}^{n-i+n-a_i-1}\tbinom{k}{n-i+1}-\sum_{k=0}^{n-i-1}\tbinom{k}{n-i+1} \hfill\\ &=\tbinom{n-i+n-a_i}{n-i+2}-\tbinom{n-i}{n-i+2} \quad上指标求和\hfill\\ \end{aligned}

所以原式为 (n−i+n−ain−i+1)−(n−i+n−ain−i+2)+(n−in−i+2)\tbinom{n - i + n - a_i}{n - i + 1} - \tbinom{n-i+n-a_i}{n-i+2}+\tbinom{n-i}{n-i+2}

这样就只需要枚举从哪一位开始超过字典序，然后用上面的式子计算啦.

然后要注意如果之前已经有长度等于 33​ 的下降子序列的话要跳出循环。

Code

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define int long long

using namespace std;

const int N = 2e6, mod = 998244353;
int fac[N + 10], ifac[N + 10], inv[N + 10];
int q[N], vis[N];
int C(int n, int m) {
    if (m > n || m < 0) return 0;
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

int calc(int x, int y, int n, int m) {
    return (mod + C(n - x + m - y, n - x + 1) + C(n - x, m - x + 2) - C(m - x + n - y, m - x + 2)) % mod;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T, n;
    cin >> T;
    fac[0] = fac[1] = ifac[0] = ifac[1] = inv[1] = 1;
    for (int i = 2; i <= N; ++i) {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        ifac[i] = ifac[i - 1] * inv[i] % mod;
        fac[i] = fac[i - 1] * i % mod;
    }
    while (T--) {
        cin >> n;
        memset(vis, 0, sizeof(vis));
        int ans = 0;
        int Max = 0;
        int mn = 1;
        for (int i = 1; i <= n; ++i) {
            cin >> q[i];
            vis[q[i]] = 1;
            ans = (ans + calc(i, max(Max, q[i]), n, n)) % mod;
            if (Max < q[i]) Max = q[i];
            else {
                if (q[i] != mn) {
                    for (int j = i + 1; j <= n; ++j) {
                        cin >> q[j];
                    }
                    break;
                }
            }
            while (vis[mn]) ++mn;
        }
        cout << ans << endl;
    }
  return 0;
}

总结

一些题可以通过寻找组合意义来转化成格路计数