题解 P4769 【[NOI2018]冒泡排序】

· · 题解

感谢给我讲了这个题的神仙跳瓜 \textrm{jumpmelon}。

首先看给的提示，我们可以发现在这样的排序方式下，对于每一个数都只向目标位置方向走，不换向。那么对于一个数 x，如果有一个比它大的数在它前面，那么它必须向左走；如果有一个比它小的数在它后面，那么它必须向右走。这样的排列是不合法的，即要求不存在长度超过 2 的下降子序列。

根据 \textrm{Dilworth} 定理，最长下降子序列的长度不超过 2，即整个排列最多被划分成 2 个上升子序列。

先不考虑字典序严格大于 q 的限制。

我们记 f_{i, j} 为前 i 个的最大值为 j 后面 n - i 个位置的方案数。我们考虑第 i 个数填什么。注意 i \leqslant j

如果填比 j 大的数，那么一定可以接在 j 的后面；如果要填比 j 小的数，那么必须填当前还没有填的中最小的，否则上升子序列将不止 2 个，所以

\begin{aligned} f_{i, j} &= \begin{cases} f_{i + 1, k} \ \ \ \ \ (k > j) \\ f_{i + 1, j} \ \ \ \ \ \end{cases} \\ &= \sum_{k = j}^n f_{i + 1, k} \end{aligned}

但是直接这样递推是 O(n^2) 的。我们把它以图像的形式表示，f_{i, j} 即表示从点 (i, j) 开始，每次向右走一步，向上走 x(x \leqslant 0) 步，不与直线 y = x - 1 （因为 i \leqslant j） 相交，走到点 (n, n) 的方案数。

如图，即从点 A(i, j) 走到 B(n, n) 的不与直线 y = x - 1 相交的方案数。

首先，如果不考虑与直线不相交，即为走 n - i 次，每次选择向上走 x (x \geqslant 0) 步，一共走了 n - j 步的方案数。模仿插板法，因为 x 可以取 0，我们把总个数加上划分数 n - i，变成 n - i + n - j 个物品划分成 n - i 块的方案数，即 \dbinom{2n - i - j - 1}{n-i-1}。

再模仿 \textrm{Catalan} 数的推法，看第一个与直线 y = x - 1 相交的位置。找点 (i, j) 关于直线 y = x - 1 的对称点 (j + 1, i - 1), 由于方案一一对应，所以，从点 (i, j) 出发，经过直线的方案数即为从点 (j + 1, i - 1) 出发到点 (n, n) 的方案数。

得到

\begin{aligned} f_{i, j} &= calc(i, j) - calc(j + 1, i - 1) \\ &= \dbinom{2n - i - j - 1}{n - i - 1} - \dbinom{2n - i - j - 1}{n - j - 2} \\ \end{aligned}

这样就得到 f 的 O(1) 求解啦！（然而 O(n^2) 有足足 80 分，真香)

可以发现 f_{0, 0} 即为 \textrm{Catalan} 数，可以得到 12 分。

回到有限制字典序严格大于 q 的原题上来。考虑一位一位枚举，假设当前枚举到第 i 项，我们计数证前 i - 1 项与 q 相同，第 i 项大于 q_i 的排列个数。

记 mx = \max_{j = 1}^{i - 1} q_j，mn 为当前还没有用过的最小的数，v = q_i。第 i 位只能填 mn 或大于 mx 的数。分类讨论

问题又来了，怎么求 f 的前缀和呢？考虑 f 的递推式 f_{i, j} = \sum_{k = j}^n f_{i + 1, k}，这正是一个前缀和的形式。所以

\sum_{k = lim}^n f_{i, k} = f_{i - 1, lim}

不用像其他题解上说的要用树状数组，复杂度 O(Tn)（还好写)

完结撒花~

代码

注意数组要开 2n，写起来很简单，但是最开始由于没彻底搞懂想了半天

#include <bits/stdc++.h>
using namespace std;

namespace TYC
{
    typedef long long ll;
    const int N = 1.2e6, p = 998244353;

    int fac[N + 5], inv[N + 5], vis[N + 5];

    inline int read()
    {
        int v = 0, fl = 0, ch = getchar();
        while (!isdigit(ch))
            fl |= (ch == '-'), ch = getchar();
        while (isdigit(ch))
            v = v * 10 + ch - '0', ch = getchar();
        return fl ? -v : v;
    }

    inline int qpow(int v, int tim)
    {
        int ans = 1;
        for (; tim; tim >>= 1, v = (ll)v * v % p)
            if (tim & 1)
                ans = (ll)ans * v % p;
        return ans;
    }

    void init()
    {
        fac[0] = 1;
        for (int i = 1; i <= N; i++)
            fac[i] = (ll)fac[i - 1] * i % p;
        inv[N] = qpow(fac[N], p - 2);
        for (int i = N; i; i--)
            inv[i - 1] = (ll)inv[i] * i % p;
    }

    inline int C(const int n, const int m)
    {
        return (n < 0 || m < 0 || n < m) ? 0 : int((ll)fac[n] * inv[m] % p * inv[n - m] % p);
    }

    int n;
    inline int F(const int i, const int j)
    {
        return i <= j && j <= n ? (C(2 * n - i - j - 1, n - i - 1) - C(2 * n - i - j - 1, n - j - 2) + p) % p : 0;
    }

    void work()
    {
        init();
        int T = read();
        while (T--)
        {
            n = read();
            memset(vis, 0, sizeof(int[n + 1]));
            int ans = 0, mx = 0, mn = 1, flag = 0, v;
            for (int i = 1; i <= n; i++)
            {
                v = read();
                if (flag)
                    continue;
                ans = (ans + (F(i - 1, max(mx, v) + 1) + p) % p) % p;
                if (mx > v && v > mn)
                    flag = 1;
                mx = max(mx, v);
                vis[v] = 1;
                while (vis[mn]) mn++;
            }
            printf("%d\n", ans);
        }
    }
}

int main()
{
    TYC::work();
    return 0;
}

P.S.
upd 2023.8.5 我已经退役很多年了，一次碰巧上洛谷看到有同学提醒组合数写反了，现特为纠正，希望同学们都能看明白。