#2543. 「JXOI2018」排序问题

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

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

九条可怜最近正在研究各种排序的性质,她发现了一种很有趣的排序方法: Gobo sort !

Gobo sort 的算法描述大致如下:

  1. 假设我们要对一个大小为 n 的数列 a 排序。
  2. 等概率随机生成一个大小为 n 的排列 p
  3. 构造一个大小为 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 个整数,表示答案。

样例

样例输入

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

样例输出

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
对于 100\% 的数据, 1\leq a_i\leq 10^9,\sum{n}\leq 2\times 10^6