[JXOI2018]排序问题

题目背景

九条可怜是一个热爱思考的女孩子。

题目描述

九条可怜最近正在研究各种排序的性质,她发现了一种很有趣的排序方法: Gobo sort ! Gobo sort 的算法描述大致如下: - 假设我们要对一个大小为 $n$ 的数列 $a$ 排序。 - 等概率随机生成一个大小为 $n$ 的排列 $p$ 。 - 构造一个大小为 $n$ 的数列 $b$ 满足 $b_i=a_{p_i}$ ,检查 $b$ 是否有序,如果 $b$ 已经有序了就结束算法,并返回 $b$ ,不然返回步骤 2。 显然这个算法的期望时间复杂度是 $O(n\times n!)$ 的,但是九条可怜惊奇的发现,利用量子的神奇性质,在量子系统中,可以把这个算法的时间复杂度优化到线性。 九条可怜对这个排序算法进行了进一步研究,她发现如果一个序列满足一些性质,那么 Gobo sort 会很快计算出正确的结果。为了量化这个速度,她定义 Gobo sort 的执行轮数是步骤 2 的执行次数。 于是她就想到了这么一个问题: 现在有一个长度为 $n$ 的序列 $x$ ,九条可怜会在这个序列后面加入 $m$ 个元素,每个元素是 $[l,r]$ 内的正整数。 她希望新的长度为 $n+m$ 的序列执行 Gobo sort 的期望执行轮数尽量的多。她希望得到这个最多的期望轮数。 九条可怜很聪明,她很快就算出了答案,她希望和你核对一下,由于这个期望轮数实在是太大了,于是她只要求你输出对 $998244353$ 取模的结果。

输入输出格式

输入格式


第一行输入一个整数 $T$,表示数据组数。 接下来 $2 \times T$ 行描述了 $T$ 组数据。 每组数据分成两行,第 1 行有四个正整数 $n,m,l,r$ ,表示数列的长度和加入数字的个数和加入数字的范围。 第 2 行有 $n$ 个正整数,第 $i$ 个表示 $x_i$ 。

输出格式


输出 $T$ 个整数,表示答案。

输入输出样例

输入样例 #1

2
3 3 1 2
1 3 4
3 3 5 7
1 3 4

输出样例 #1

180
720

说明

###样例解释 对于第一组数据,我们可以添加 $\{1,2,2\}$ 到序列的最末尾,使得这个序列变成 `1 3 4 1 2 2` ,那么进行一轮的成功概率是 $\frac{1}{180}$ ,因此期望需要 $180$ 轮。 对于第二组数据,我们可以添加 $\{5,6,7\}$ 到序列的最末尾,使得这个序列变成 `1 3 4 5 6 7` ,那么进行一轮的成功概率是 $\frac{1}{720}$ ,因此期望需要 $720$ 轮。 ### 数据范围 对于 30% 的数据, $T\leq 10 , n,m,l,r\leq 8$。 对于 50% 的数据, $T\leq 300,n,m,l,r,a_i\leq 300$ 。 对于 60% 的数据, $\sum{r-l+1}\leq 10^7$ 。 对于 70% 的数据, $\sum{n} \leq 2\times 10^5$ 。 对于 90% 的数据, $m\leq 2\times 10^5$。 对于 100% 的数据, $T\leq 10^5,n\leq 2\times 10^5,m\leq 10^7,1\leq l\leq r\leq 10^9$ , $1\leq a_i\leq 10^9,\sum{n}\leq 2\times 10^6$ 。