#1837. 「NOI2018」冒泡排序

「NOI2018」冒泡排序

题目描述

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

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

输入:一个长度为 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] 的值

冒泡排序的交换次数被定义为交换过程的执行次数。可以证明交换次数的一个下界是 12i=1nipi\frac 1 2 \sum_{i=1}^n \lvert i - p_i \rvert,其中 pip_i 是排列 pp 中第 ii 个位置的数字。如果你对证明感兴趣,可以看提示。

小 S 开始专注于研究长度为 nn 的排列中,满足交换次数 =12i=1nipi= \frac 1 2 \sum_{i=1}^n \lvert i - p_i \rvert 的排列(在后文中,为了方便,我们把所有这样的排列叫「好」的排列)。他进一步想,这样的排列到底多不多?它们分布的密不密集?

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

输入格式

从文件 inverse.in 读入数据。

输入第一行包含一个正整数 TT,表示数据组数。

对于每组数据,第一行有一个正整数 nn,保证 n6×105n \leq 6 \times 10^5

接下来一行会输入 nn 个正整数,对应于题目描述中的 qiq_i,保证输入的是一个 11nn 的排列。

输出格式

输出到文件 inverse.out 中。

输出共 TT 行,每行一个整数。

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

样例 1

1
3
1 3 2
3

字典序比 1 3 21 \ 3 \ 2 大的排列中,除了 3 2 13 \ 2 \ 1 以外都是「好」的排列,故答案为 33

1
4
1 4 2 3
9

见附加文件中的 inverse3.ininverse3.ans.

数据范围与提示

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

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

nmaxn_\mathrm{max} 表示每组数据中 nn 的最大值,n\sum n 表示所有数据的 nn 的和。

测试点 nmax=n_\mathrm{max} = n\sum n \leq 特殊性质
1 88 5 nmax5 \ n_\mathrm{max}
2 99
3 1010
4 1212
5 1313
6 1414
7 1616
8
9 1717
10 1818
11
12 122122 700700 iqi=i\forall i \enspace q_i = i
13 144144
14 166166
15 200200
16 233233
17 777777 40004000 iqi=i\forall i \enspace q_i = i
18 888888
19 933933
20 10001000
21 266666266666 20000002000000 iqi=i\forall i \enspace q_i = i
22 333333333333
23 444444444444
24 555555555555
25 600000600000

「提示」

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

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

并不是所有的排列都达到了下界,比如在 n=3n = 3 的时候,考虑排列 3 2 13 \ 2 \ 1,这个排列进行冒泡排序以后的交换次数是 33,但是 12i=1nipi\frac 1 2 \sum_{i=1}^n \lvert i - p_i \rvert 只有 22