UOJ Logo Universal Online Judge

UOJ

#394. 【NOI2018】冒泡排序

附件下载 统计

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

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

input:一个长度为 n 的排列 p[1...n]
output: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$ 的排列。

需要注意的是,在官方测试数据中,存在 $n = 0$ 的测试点,因此并不满足“$n$ 为正整数”的限制。即,题目中的限制为 $\mathbf{0} \le n \le 6 \times 10^5$。

输出格式

输出到标准输出。

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

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

样例一

input

1
3
1 3 2

output

3

解释

字典序比 $1~~3~~2$ 大的排列中,除了 $3~~2~~1$ 以外都是“好”的排列,故答案为 3。

样例二

input

1
4
1 4 2 3

output

9

样例三

下载目录下的 ex_3.inex_3.ans

子任务

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

对于所有数据,均满足 $T = 5$ (样例可能不满足).

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

测试点$n_{max}=$$\sum n\leq$特殊性质
1$8$$5n_{max}$$\text{无}$
2$9$
3$10$
4$12$
5$13$
6$14$
7$16$
8
9$17$
10$18$
11
12$122$$700$$\forall i ~~q_i=i$
13$144$$\text{无}$
14$166$
15$200$
16$233$
17$777$$4000$$\forall i ~~q_i=i$
18$888$$\text{无}$
19$933$
20$1000$
21$266666$$2000000$$\forall i ~~q_i=i$
22$333333$$\text{无}$
23$444444$
24$555555$
25$600000$

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

提示

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

排序本质上就是数字的移动,因此排序的交换次数应当可以用数字移动的总距离来描述。对于第 $i$ 个位置,假设在初始排列中,这个位置上的数字是 $p_i$,那么我们需要将这个数字移动到第 $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$ 的时候,考虑排列 $3 ~~ 2~~1$, 这个排列进行冒泡排序以后的交换次数是 3,但是 $\frac{1}{2}\sum_{i=1}^{n}{|i-p_i|}$ 只有 2。

下载

样例数据下载