#P18290. Fast Bogosort
Fast Bogosort
Fast Bogosort
普通 Bogosort 反复将整个数组均匀随机打乱,再检查是否有序。下面考虑一种更快的算法,对 到 的一个排列进行排序:
- 如果当前排列已经递增有序,结束算法。
- 否则,把排列划分成尽可能多个连续段。每段 中包含的数恰好是 ,各段互不重叠且覆盖整个排列。
- 对每个长度大于 的段 ,调用一次
shuffle(l,r),将该段中的所有数均匀随机打乱。长度为 的段不调用此函数。 - 返回第 1 步,再次检查并重新划分。
给定初始排列,求算法结束前调用 shuffle(l,r) 的总次数的期望值。同一轮对不同段分别调用时,每次调用都需要计数。
输入格式
第一行包含一个整数 ()。
第二行包含 个整数 ,保证它们构成 到 的一个排列。
输入只有一组数据。
输出格式
期望值可以表示为最简分数 ,题目保证 。输出唯一整数 ,满足
$$0\le R<998244353,\qquad RQ\equiv P\pmod{998244353}.$$样例 1
5
2 1 5 3 4
332748123
样例 2
10
4 2 3 1 6 5 9 7 10 8
453747445