#P17493. [ICPC 2026 Wuhan I] Sort
[ICPC 2026 Wuhan I] Sort
题目描述
给定一个长度为 的排列 。
每次操作会等概率随机选择一个整数 (),并将排列 中的前缀区间 和后缀区间 分别进行升序排序。特别地,当 时,后缀区间为空,即相当于对整个排列进行排序。
你需要求出,使得最终排列完全升序有序(即满足 )所需要的期望操作次数。
答案对 取模。
输入格式
本题包含多组测试数据。
第一行包含一个整数 (),表示测试数据组数。
对于每组测试数据:
- 第一行包含一个整数 (),表示排列的长度。
- 第二行包含 个整数 (),表示给定的排列 。保证给出的序列是一个 的排列。
保证所有测试数据中 的总和不超过 。
输出格式
对于每组测试数据输出一行,包含一个整数,表示期望操作次数对 取模后的结果。
3
3
3 1 2
2
2 1
5
3 2 5 1 4
748683267
2
670695427