Comet OJ

C0411 [NOI2018Day1-B]冒泡排序

内存限制：512 MB 时间限制：1000 ms

题目描述

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

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

输入：一个长度为 n 的排列 p[1...n]
输出：p 排序后的结果。
for i = 1 to n do
	for j = 1 to n - i 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$，计算字典序$p$严格大于的“好”的排列个数。但是他不会做，于是求助于你，希望你帮他解决这个问题，考虑到答案可能会很大，因此只需输出答案对998244353取模的结果。

输入格式

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

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

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

输出

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

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

样例

样例输入 1

1
3
1 3 2

样例输出 1

3

样例输入 2

1
4
1 4 2 3

样例输出 2

9

提示

【样例1解释】

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

【子任务】

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

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

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

屏幕快照 2019-06-03 下午1.24.18.png

【提示】

下面是对交换次数下界是$\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。