P7623 [AHOI2021初中组] 收衣服题目背景AHOI2021 初中组 T3你可以选择跳过背景部分。沉迷于虐待跳蚤游戏的小雪没有发觉时间过了多久一抬头发现竟然天色大变天空一片昏黄一股怪味扑鼻而来。没想到在如此发达的 2077 年城市中还能碰到沙尘暴这超现实的场景让小雪怀疑是跳蚤国王显灵。“别愣着了快去收衣服呀”小可可突然想到。题目描述看着这么多蒙灰的衣服他们俩欲哭无泪而且有的衣服是没法一起洗的为了分门别类小可可给了每件衣服一个1∼n1 \sim n1∼n的两两不同的标号其中nnn是衣服的件数把衣服排成1,2,…,n1,2,\ldots,n1,2,…,n的顺序再洗会比较方便。小可可还想到我们可以把一段连续的晾衣架拿出来在手上翻转顺序再放回去。作为 OI 选手的你马上抽象出了小可可排序衣服的算法我们设初始时从左往右第iii件衣服的标号为pip_ipi​按1,2,…,n−11,2,\ldots,n-11,2,…,n−1的顺序枚举iii设pi,pi1,…,pnp_i,p_{i1},\ldots,p_npi​,pi1​,…,pn​中标号最小的是pjp_jpj​那么将pi,pi1,…,pj−1,pjp_i,p_{i1},\ldots,p_{j-1},p_jpi​,pi1​,…,pj−1​,pj​左右翻转变成pj,pj−1,…,pi1,pip_j,p_{j-1},\ldots,p_{i1},p_ipj​,pj−1​,…,pi1​,pi​。小雪很快发现小可可的算法看似厉害实际上很傻——在天色的影响下大家都分不出衣服的标号了。于是他们只能回到房间进行理性愉悦我们假设左右翻转区间[i,j][i,j][i,j]的操作代价是wi,jw_{i,j}wi,j​一次排序的代价是每次翻转的操作代价之和。现在小可可想知道当ppp取遍n!n!n!种排列时所有情况的排序代价之和。只用输出答案对9982443539982443539982443537×17×22317 \times 17 \times 2^{23} 17×17×2231一个质数取模后的值。输入格式第一行一个整数nnn。下面n−1n-1n−1行第i(1≤i≤n)i(1 \le i \le n)i(1≤i≤n)行n−i1n - i 1n−i1个空格隔开的整数第jjj个表示wi,jw_{i,j}wi,j​。输出格式一行一个整数表示答案对998244353998244353998244353取模的结果。输入输出样例 #1输入 #15 1 2 3 4 5 1 2 3 4 1 2 3 1 2输出 #11080输入输出样例 #2输入 #2见附加文件的 sort2.in。输出 #2见附加文件的 sort2.ans。说明/提示【样例 1 解释】我们举一个例子当p[3,2,5,1,4]p[3,2,5,1,4]p[3,2,5,1,4]时算法的执行步骤如下执行到i1i1i1p1,p2,p3,p4,p5p_1,p_2,p_3,p_4,p_5p1​,p2​,p3​,p4​,p5​即3,2,5,1,43,2,5,1,43,2,5,1,4中的最小值为p41p_41p4​1我们翻转区间[1,4][1,4][1,4]ppp变为[1,5,2,3,4][1,5,2,3,4][1,5,2,3,4]代价为w1,44w_{1,4}4w1,4​4执行到i2i2i2p2,p3,p4,p5p_2,p_3,p_4,p_5p2​,p3​,p4​,p5​即5,2,3,45,2,3,45,2,3,4中的最小值为p32p_32p3​2我们翻转区间[2,3][2,3][2,3]ppp变为[1,2,5,3,4][1,2,5,3,4][1,2,5,3,4]代价为w2,32w_{2,3}2w2,3​2执行到i3i3i3p3,p4,p5p_3,p_4,p_5p3​,p4​,p5​即5,3,45,3,45,3,4中的最小值为p43p_43p4​3我们翻转区间[3,4][3,4][3,4]ppp变为[1,2,3,5,4][1,2,3,5,4][1,2,3,5,4]代价为w3,42w_{3,4}2w3,4​2执行到i4i4i4p4,p5p_4,p_5p4​,p5​即5,45,45,4中的最小值为p54p_54p5​4我们翻转区间[4,5][4,5][4,5]ppp变为[1,2,3,4,5][1,2,3,4,5][1,2,3,4,5]代价为w4,52w_{4,5}2w4,5​2。可以看到算法执行到第iii步结束时序列的[1,i][1,i][1,i]位置上恰好是[1,i][1,i][1,i]号衣服算法结束后ppp被排好了序。这次排序总共付出了422210422210422210的代价。注意算法一定会执行n−1n-1n−1步即使中间就排好了序也不会提前退出。【数据范围与提示】提示本题输入规模较大请避免使用过慢的输入方式。对于25%25\%25%的数据保证1≤n≤91 \le n \le 91≤n≤9对于50%50\%50%的数据保证1≤n≤161 \le n \le 161≤n≤16对于70%70\%70%的数据保证1≤n≤501 \le n \le 501≤n≤50对于另外15%15\%15%的数据保证wi,j1w_{i,j}1wi,j​1对于100%100\%100%的数据保证1≤n≤5001 \le n \le 5001≤n≤5000≤wi,j9982443530 \le w_{i,j} 9982443530≤wi,j​998244353。C实现#includebits/stdc.husingnamespacestd;constintN505,P998244353;intn,w[N][N],fact[N],dp[N];intmain(){scanf(%d,n);for(inti1;in;i){for(intji;jn;j){scanf(%d,w[i]j);}}fact[0]1;for(inti1;in;i){fact[i]1ll*fact[i-1]*i%P;}for(intin-1;i;--i){for(intji;jn;j){dp[i](dp[i]dp[i1]1ll*w[i][j]*fact[n-i])%P;}}printf(%d\n,dp[1]);}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容