33OJ
登录 注册

#P17493. [ICPC 2026 Wuhan I] Sort

    ID: 20221 远端评测题 4000ms 512MiB 尝试: 0 已通过: 0 显示难度省选/NOI− 上传者: 标签>ICPC2026省赛/邀请赛湖北

[ICPC 2026 Wuhan I] Sort

题目描述

给定一个长度为 nn 的排列 pp。

每次操作会等概率随机选择一个整数 ii(1≤i≤n1 \le i \le n),并将排列 pp 中的前缀区间 [1,i][1,i] 和后缀区间 [i+1,n][i+1,n] 分别进行升序排序。特别地,当 i=ni=n 时,后缀区间为空,即相当于对整个排列进行排序。

你需要求出,使得最终排列完全升序有序(即满足 pj=jp_j=j)所需要的期望操作次数。

答案对 998244353998244353 取模。

输入格式

本题包含多组测试数据。

第一行包含一个整数 TT(1≤T≤1001 \le T \le 100),表示测试数据组数。

对于每组测试数据:

  • 第一行包含一个整数 nn(1≤n≤5001 \le n \le 500),表示排列的长度。
  • 第二行包含 nn 个整数 p1,p2,⋯ ,pnp_1,p_2,\cdots,p_n(1≤pj≤n1 \le p_j \le n),表示给定的排列 pp。保证给出的序列是一个 1∼n1\sim n 的排列。

保证所有测试数据中 nn 的总和不超过 20002000。

输出格式

对于每组测试数据输出一行,包含一个整数,表示期望操作次数对 998244353998244353 取模后的结果。

3
3
3 1 2
2
2 1
5
3 2 5 1 4
748683267
2
670695427