题目描述

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

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

输入:一个长度为n 的排列p[1…n]

输出:p 排序后的结果。

冒泡排序的交换次数被定义为交换过程的执行次数。可以证明交换次数的一个下界是 $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 取模的结果。

输入和输出

输入格式

从文件inverse.in 中读入数据。

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

对于每组数据,第一行有一个正整数n, 保证 $n leq 6 imes 10^5$
接下来一行会输入n 个正整数,对应于题目描述中的$q_i$,保证输入的是一个1 到 n 的排列。

输出格式

输出到文件inverse.out 中。

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

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

样例

输入

输出

数据范围和提示

测试点

nmax=n_{max}=

nsum nleq

特殊性质 测试点

nmax=n_{max}=

nsum nleq

特殊性质
1

88

5nmax5n_{max}

13

144144

700700

2

99

5nmax5n_{max}

14

166166

700700

3

1010

5nmax5n_{max}

15

200200

700700

4

1212

5nmax5n_{max}

16

233233

700700

5

1313

5nmax5n_{max}

17

777777

40004000

i  pi=iforall i ~~p_i=i

6

1414

5nmax5n_{max}

18

888888

40004000

7

1616

5nmax5n_{max}

19

933933

40004000

8

1616

5nmax5n_{max}

20

10001000

40004000

9

1717

5nmax5n_{max}

21

266666266666

20000002000000

i  pi=iforall i ~~p_i=i

10

1818

5nmax5n_{max}

22

333333333333

20000002000000

11

1818

5nmax5n_{max}

23

444444444444

20000002000000

12

122122

700700

i  pi=iforall i ~~p_i=i

24

555555555555

20000002000000

. . . . 25

600000600000

20000002000000

思路

题目的限制可以转化为不存在长度>=3的下降子序列,这又可以转化为可以将序列划分为2个上升子序列。

首先我们用树状数组预处理出 $a_i$ ,后面的比它大的数的个数 $b_i$ ,以及前面的比它小的数 $c_i$。因为要保证字典序,我们就从前往后依次固定前 $i$ 个数,然后讨论后面的数字的顺序。

令前 $i$ 个位置中,最大的数是 $j$。 我们发现,大于$j$的数的顺序不影响答案,然而小于 $j$ 的数必须从小到大按顺序填入(因为这些元素一定要被归入同一个上升子序列)。

所以,我们可以得到这个式子:$f(i,j) = sum_{k=0}^j f(i-1,j-k)$。

通过一些化式子的技巧,可以发现它恰好等于 $ binom{n+m-1}{m}- binom{n+m-1}{m-2}$。

然后就可以开始暴算啦!

代码