主页
题目
状态
排名
OI排名
统计
题解
请登录
常用链接
AOJ考试平台
老赵的Gitee代码
编译原理模拟考试平台
Java技术手册
FCC网站
菜鸟网
在线工具箱
字节豆包GPT
代码可视化
力扣网
牛客网
洛谷
杭电OJ
CodeForce
隐藏编译器
Problem C: 收衣服(sort)
上一题
正确率: $33.33\%$
下一题
Time Limit
$1$ 秒/Second(s)
Memory Limit
$128$ 兆字节/Megabyte(s)
提交总数
$3$
正确数量
$1$
"
裁判形式
标准裁判/Standard Judge
我的状态
尚未尝试
难度
分类标签
×
为本题添加算法分类(请不要超过5个)
当前分类(单击移除):
单击选择分类:
Description
<div> <span style="font-size:16px;">看着这么多蒙灰的衣服,他们俩欲哭无泪;而且,有的衣服是没法一起洗的,为了分门别</span><span style="font-size:16px;">类,小可可给了每件衣服一个 1 ∼ n 的两两不同的标号,其中 n 是衣服的件数,把衣服排成</span><span style="font-size:16px;">1, 2, . . . , n 的顺序再洗会比较方便。</span> </div> <div> <span style="font-size:16px;">小可可还想到,我们可以把一段连续的晾衣架拿出来,在手上翻转顺序,再放回去。作为 OI</span><span style="font-size:16px;">选手的你,马上抽象出了小可可排序衣服的算法:我们设初始时从左往右第 i 件衣服的标号为 pi,</span><span style="font-size:16px;">按 1, 2, . . . , n−1 的顺序枚举 i,设 pi , pi+1, . . . , pn 中标号最小的是 pj,那么将 pi , pi+1, . . . , pj−1, pj</span><span style="font-size:16px;">左右翻转变成 pj , pj−1, . . . , pi+1, pi。</span><span style="font-size:16px;">小雪很快发现,小可可的算法看似厉害,实际上很傻——在天色的影响下,大家都分不出衣</span><span style="font-size:16px;">服的标号了。于是他们只能回到房间进行理性愉悦:我们假设左右翻转区间 [i, j] 的操作代价是</span> </div> <div> <span style="font-size:16px;">wi,j,一次排序的代价是每次翻转的操作代价之和。现在小可可想知道,</span><span style="font-size:16px;">当p</span><span style="font-size:16px;">取</span><span style="font-size:16px;">遍n!</span><span style="font-size:16px;">种</span><span style="font-size:16px;">排</span><span style="font-size:16px;">列</span><span style="font-size:16px;">时,</span><span style="font-size:16px;">所</span><span style="font-size:16px;">有</span><span style="font-size:16px;">情</span><span style="font-size:16px;">况</span><span style="font-size:16px;">的</span><span style="font-size:16px;">排</span><span style="font-size:16px;">序</span><span style="font-size:16px;">代</span><span style="font-size:16px;">价</span><span style="font-size:16px;">之</span><span style="font-size:16px;">和。</span> </div> <div> <span style="font-size:16px;">只用输出答案对 998244353(= 7 × 17 × 2 <sup>23</sup></span><span style="font-size:16px;">+ 1,一个质数)取模后的值。</span> </div>
Input
<div> <span style="font-size:16px;">第一行一个整数 n。</span> </div> <div> <span style="font-size:16px;">下面 n − 1 行,第 i(1 ≤ i ≤ n) 行 n − i + 1</span><span style="font-size:16px;">个空格隔开的整数,第 j 个表示 wi,j。</span> </div>
Output
<div> <span style="font-size:16px;">一行一个整数表示答案对 998244353 取模的结果。</span> </div>
Sample Input
复制
5 1 2 3 4 5 1 2 3 4 1 2 3 1 2
Sample Output
复制
1080
提示
<div> <span style="font-size:16px;">【样例解释】</span> </div> <div> <span style="font-size:16px;">我们举一个例子,当 p = [3, 2, 5, 1, 4] 时,算法的执行步骤如下:</span> </div> <div> <span style="font-size:16px;">•</span> </div> <div> <span style="font-size:16px;">执行到 i = 1,p1, p2, p3, p4, p5 即 3, 2, 5, 1, 4 中的最小值为 p4 = 1,我们翻转区间 [1, 4],p</span> </div> <div> <span style="font-size:16px;">变为 [1, 5, 2, 3, 4],代价为 w1,4 = 4;</span> </div> <div> <span style="font-size:16px;">•</span> </div> <div> <span style="font-size:16px;">执行到 i = 2,p2, p3, p4, p5 即 5, 2, 3, 4 中的最小值为 p3 = 2,我们翻转区间 [2, 3],p 变为</span> </div> <div> <span style="font-size:16px;">[1, 2, 5, 3, 4],代价为 w2,3</span> </div> <div> <span style="font-size:16px;">= 2;</span> </div> <div> <span style="font-size:16px;">•</span> </div> <div> <span style="font-size:16px;">执行到 i = 3,p3, p4, p5</span> </div> <div> <span style="font-size:16px;">即 5, 3, 4 中的最小值为 p4 = 3,我们翻转区间 [3, 4],p 变为</span> </div> <div> <span style="font-size:16px;">[1, 2, 3, 5, 4],代价为 w3,4</span> </div> <div> <span style="font-size:16px;">= 2;</span> </div> <div> <span style="font-size:16px;">•</span> </div> <div> <span style="font-size:16px;">执行到 i = 4,p4, p5 即 5, 4 中的最小值为 p5 = 4,我们翻转区间 [4, 5],p 变为 [1, 2, 3, 4, 5],</span> </div> <div> <span style="font-size:16px;">代价为 w4,5 = 2。</span> </div> <div> <span style="font-size:16px;">可以看到,算法执行到第 i 步结束时,序列的 [1, i] 位置上恰好是 [1, i] 号衣服,算法结束后</span> </div> <div> <span style="font-size:16px;">p 被排好了序。这次排序总共付出了 4 + 2 + 2 + 2 = 10 的代价。</span> </div> <div> <span style="font-size:16px;">注意:算法一定会执行n − 1步,即使中间就排好了序也不会提前退出。</span> </div>
AOJ
Please Login