P4769 [NOI2018] 冒泡排序 洛谷黑题题解附源码

[NOI2018] 冒泡排序

题目背景

请注意，题目中存在 $n=0$ 的数据。

题目描述

最近，小 S 对冒泡排序产生了浓厚的兴趣。为了问题简单，小 S 只研究对 $1$ 到 $n$ 的排列的冒泡排序。

下面是对冒泡排序的算法描述。

输入：一个长度为 n 的排列 p[1...n]
输出：p 排序后的结果。
for i = 1 to n do
	for j = 1 to n - 1 do
		if(p[j] > p[j + 1])
			交换 p[j] 与 p[j + 1] 的值

冒泡排序的交换次数被定义为交换过程的执行次数。可以证明交换次数的一个下界是 $\frac{1}{2}{\sum }_{i=1}^n|i-p_i|$，其中 $p_i$ 是排列 $p$ 中第 $i$ 个位置的数字。如果你对证明感兴趣，可以看提示。

小 S 开始专注于研究长度为 $n$ 的排列中，满足交换次数 $=\frac{1}{2}{\sum }_{i=1}^n|i-p_i|$ 的排列（在后文中，为了方便，我们把所有这样的排列叫「好」的排列）。他进一步想，这样的排列到底多不多？它们分布的密不密集？

小 S 想要对于一个给定的长度为 $n$ 的排列 $q$，计算字典序严格大于 $q$ 的“好”的排列个数。但是他不会做，于是求助于你，希望你帮他解决这个问题，考虑到答案可能会很大，因此只需输出答案对 $998244353$ 取模的结果。

输入格式

输入第一行包含一个正整数 $T$，表示数据组数。

对于每组数据，第一行有一个正整数 $n$，保证 $n\le 6\times 10^5$。

接下来一行会输入 $n$ 个正整数，对应于题目描述中的 $q_i$，保证输入的是一个 $1$ 到 $n$ 的排列。

输出格式

输出共 $T$ 行，每行一个整数。

对于每组数据，输出一个整数，表示字典序严格大于 $q$ 的「好」的排列个数对 $998244353$ 取模的结果。

样例 #1

样例输入 #1

1
3
1 3 2

样例输出 #1

3

样例 #2

样例输入 #2

1
4
1 4 2 3

样例输出 #2

9

提示

更多样例

更多样例请在附加文件中下载。

样例 3

见附加文件中的 inverse3.in 与 inverse3.ans。

样例 1 解释

字典序比 $132$ 大的排列中，除了 $321$ 以外都是「好」的排列，故答案为 $3$。

数据范围

下面是对本题每个测试点的输入规模的说明。

对于所有数据，均满足 $T=5$（样例可能不满足）。

记 $n_{\max }$ 表示每组数据中 $n$ 的最大值，$\sum n$ 表示所有数据的 $n$ 的和。

提示

下面是对交换次数下界是 $\frac{1}{2}{\sum }_{i=1}^n|i-p_i|$ 的证明。

排序本质上就是数字的移动，因此排序的交换次数应当可以用数字移动的总距离来描述。对于第 $i$ 个位置，假设在初始排列中，这个位置上的数字是 pi，那么我们需要将这个数字移动到第 $p_i$ 个位置上，移动的距离是 $|i-p_i|$。从而移动的总距离就是 ${\sum }_{i=1}^n|i-p_i|$，而冒泡排序每次会交换两个相邻的数字，每次交换可以使移动的总距离至多减少 $2$。因此 $\frac{1}{2}{\sum }_{i=1}^n|i-p_i|$ 是冒泡排序的交换次数的下界。

并不是所有的排列都达到了下界，比如在 $n=3$ 的时候，考虑排列 $321$，这个排列进行冒泡排序以后的交换次数是 $3$，但是 $\frac{1}{2}{\sum }_{i=1}^n|i-p_i|$ 只有 $2$。

#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;
}