P7623 [AHOI2021初中组] 收衣服

AHOI2021 初中组 T3 **你可以选择跳过背景部分。** 沉迷于虐待跳蚤游戏的小雪没有发觉时间过了多久，一抬头发现竟然天色大变！天空一片昏黄，一股怪味扑鼻而来。没想到在如此发达的 2077 年，城市中还能碰到沙尘暴，这超现实的场景让小雪怀疑是跳蚤国王显灵。 “别愣着了，快去收衣服呀！”小可可突然想到。

看着这么多蒙灰的衣服，他们俩欲哭无泪；而且，有的衣服是没法一起洗的，为了分门别类，小可可给了每件衣服一个 $1 \sim n$ 的两两不同的标号，其中 $n$ 是衣服的件数，把衣服排成 $1,2,\ldots,n$ 的顺序再洗会比较方便。 小可可还想到，我们可以把一段连续的晾衣架拿出来，在手上翻转顺序，再放回去。作为 OI 选手的你，马上抽象出了小可可排序衣服的算法：我们设初始时从左往右第 $i$ 件衣服的标号为 $p_i$，按 $1,2,\ldots,n-1$ 的顺序枚举 $i$，设 $p_i,p_{i+1},\ldots,p_n$ 中标号最小的是 $p_j$，那么将 $p_i,p_{i+1},\ldots,p_{j-1},p_j$ 左右翻转变成 $p_j,p_{j-1},\ldots,p_{i+1},p_i$。 小雪很快发现，小可可的算法看似厉害，实际上很傻——在天色的影响下，大家都分不出衣服的标号了。于是他们只能回到房间进行理性愉悦：我们假设左右翻转区间 $[i,j]$ 的操作代价是 $w_{i,j}$，一次排序的代价是每次翻转的操作代价之和。现在小可可想知道，当 $p$ 取遍 $n!$ 种排列时，所有情况的排序代价之和。 只用输出答案对 $998244353$（$=7 \times 17 \times 2^{23} + 1$，一个质数）取模后的值。

第一行一个整数 $n$。 下面 $n-1$ 行，第 $i(1 \le i \le n)$ 行 $n - i + 1$ 个空格隔开的整数，第 $j$ 个表示 $w_{i,j}$。

一行一个整数，表示答案对 $998244353$ 取模的结果。

【样例 1 解释】 我们举一个例子，当 $p=[3,2,5,1,4]$ 时，算法的执行步骤如下： - 执行到 $i=1$，$p_1,p_2,p_3,p_4,p_5$ 即 $3,2,5,1,4$ 中的最小值为 $p_4=1$，我们翻转区间 $[1,4]$，$p$ 变为 $[1,5,2,3,4]$，代价为 $w_{1,4}=4$； - 执行到 $i=2$，$p_2,p_3,p_4,p_5$ 即 $5,2,3,4$ 中的最小值为 $p_3=2$，我们翻转区间 $[2,3]$，$p$ 变为 $[1,2,5,3,4]$，代价为 $w_{2,3}=2$； - 执行到 $i=3$，$p_3,p_4,p_5$ 即 $5,3,4$ 中的最小值为 $p_4=3$，我们翻转区间 $[3,4]$，$p$ 变为 $[1,2,3,5,4]$，代价为 $w_{3,4}=2$； - 执行到 $i=4$，$p_4,p_5$ 即 $5,4$ 中的最小值为 $p_5=4$，我们翻转区间 $[4,5]$，$p$ 变为 $[1,2,3,4,5]$，代价为 $w_{4,5}=2$。 可以看到，算法执行到第 $i$ 步结束时，序列的 $[1,i]$ 位置上恰好是 $[1,i]$ 号衣服，算法结束后 $p$ 被排好了序。这次排序总共付出了 $4+2+2+2=10$ 的代价。 **注意：算法一定会执行 $n-1$ 步，即使中间就排好了序也不会提前退出。** 【数据范围与提示】 **提示：本题输入规模较大，请避免使用过慢的输入方式。** - 对于 $25\%$ 的数据，保证 $1 \le n \le 9$； - 对于 $50\%$ 的数据，保证 $1 \le n \le 16$； - 对于 $70\%$ 的数据，保证 $1 \le n \le 50$； - 对于另外 $15\%$ 的数据，保证 $w_{i,j}=1$； - 对于 $100\%$ 的数据，保证 $1 \le n \le 500$，$0 \le w_{i,j} < 998244353$。