Processing math: 18%
编程题
                ### 问题描述

固执的 Alice 总喜欢通过交换数组中相邻元素的方式来对数组进行非降序的排序,但神奇的是,她总能找到最小的交换次数使得数组变得有序。而敏锐的 Bob 觉得,通过这样的方式进行排序可能耗费的次数过多,因此他准备给 Alice 出排序题检测这一个结论。

现有一个长度为 n 的数组 nums。Bob 先将其随机打乱,使得 nums 的每个排列的出现概率都相同;接下来 Alice 用最小的相邻元素交换次数,将数组排列至非降序。设 Alice 进行的总交换次数为 X 次,请你求出 X 的期望是多少?

可以证明,X 的期望一定是有理数,同时可以表示为 \frac{p}{q}(p\geq0, q>0, \gcd(p,q)=1, q \mod 998244353 \neq 0) 的形式,其中 \gcd(p,q) 表示 p,q 的最大公约数。请你输出 p·q^{-1} \mod 998244353,其中 q^{-1} 表示 q 在模 998244353 意义下的逆元,满足 q·q^{-1} \mod 9982443531 \leq q^{-1} < 998244353

输入格式

第一行包含一个正整数 nn 表示数组的长度。

第二行包含 n 个正整数 nums_1, nums_2,..., nums_n,用空格进行分隔,表示数组 nums 中的每一个元素。

输出格式

输出一行,表示所求的期望。

样例输入 1

3
1 2 3

样例输出 1

499122178

说明 1

在样例中,数组被 Bob 打乱后的新数组可能为 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1],每个排列发生的概率相等,对应的 Alice 进行的最小的交换次数分别为 0,1,1,2,2,3,因此期望为 \frac{0+1+1+2+2+3}{6}=\frac{9}{2},因此输出的是 9·2^{-1}=499122178

样例输入 2

3
1 1 2

样例输出 2

1

说明 2

在样例中,数组被 Bob 打乱后的新数组可能为 [1,1,2],[1,2,1],[2,1,1],每个排列发生的概率相等,对应的 Alice 进行的最小的交换次数分别为 0,1,2,因此期望为 \frac{0+1+2}{3}=1,因此输出的是 1·1^{-1}=1

评测数据规模

对于 20% 的评测数据,1\leq n \leq 3\times 10^3

对于 100% 的评测数据,1\leq n \leq 3\times 10^5

对于所有的测评数据,均满足 1 \leq nums_i \leq 10^{18}

查看答案
赣ICP备20007335号-2