打卡信奥刷题（3139）用C++实现信奥题 P7623 [AHOI2021初中组] 收衣服-编程阁

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,pi+1,…,pnp_i,p_{i+1},\ldots,p_npi,pi+1,…,pn中标号最小的是pjp_jpj，那么将pi,pi+1,…,pj−1,pjp_i,p_{i+1},\ldots,p_{j-1},p_jpi,pi+1,…,pj−1,pj左右翻转变成pj,pj−1,…,pi+1,pip_j,p_{j-1},\ldots,p_{i+1},p_ipj,pj−1,…,pi+1,pi。

小雪很快发现，小可可的算法看似厉害，实际上很傻——在天色的影响下，大家都分不出衣服的标号了。于是他们只能回到房间进行理性愉悦：我们假设左右翻转区间[i,j][i,j][i,j]的操作代价是wi,jw_{i,j}wi,j，一次排序的代价是每次翻转的操作代价之和。现在小可可想知道，当ppp取遍n!n!n!种排列时，所有情况的排序代价之和。

只用输出答案对998244353998244353998244353（=7×17×223+1=7 \times 17 \times 2^{23} + 1=7×17×223+1，一个质数）取模后的值。

输入格式

第一行一个整数nnn。

下面n−1n-1n−1行，第i(1≤i≤n)i(1 \le i \le n)i(1≤i≤n)行n−i+1n - i + 1n−i+1个空格隔开的整数，第jjj个表示wi,jw_{i,j}wi,j。

输出格式

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

输入输出样例 #1

输入 #1

5 1 2 3 4 5 1 2 3 4 1 2 3 1 2

输出 #1

输入输出样例 #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]时，算法的执行步骤如下：

执行到i=1i=1i=1，p1,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中的最小值为p4=1p_4=1p4=1，我们翻转区间[1,4][1,4][1,4]，ppp变为[1,5,2,3,4][1,5,2,3,4][1,5,2,3,4]，代价为w1,4=4w_{1,4}=4w1,4=4；
执行到i=2i=2i=2，p2,p3,p4,p5p_2,p_3,p_4,p_5p2,p3,p4,p5即5,2,3,45,2,3,45,2,3,4中的最小值为p3=2p_3=2p3=2，我们翻转区间[2,3][2,3][2,3]，ppp变为[1,2,5,3,4][1,2,5,3,4][1,2,5,3,4]，代价为w2,3=2w_{2,3}=2w2,3=2；
执行到i=3i=3i=3，p3,p4,p5p_3,p_4,p_5p3,p4,p5即5,3,45,3,45,3,4中的最小值为p4=3p_4=3p4=3，我们翻转区间[3,4][3,4][3,4]，ppp变为[1,2,3,5,4][1,2,3,5,4][1,2,3,5,4]，代价为w3,4=2w_{3,4}=2w3,4=2；
执行到i=4i=4i=4，p4,p5p_4,p_5p4,p5即5,45,45,4中的最小值为p5=4p_5=4p5=4，我们翻转区间[4,5][4,5][4,5]，ppp变为[1,2,3,4,5][1,2,3,4,5][1,2,3,4,5]，代价为w4,5=2w_{4,5}=2w4,5=2。

可以看到，算法执行到第iii步结束时，序列的[1,i][1,i][1,i]位置上恰好是[1,i][1,i][1,i]号衣服，算法结束后ppp被排好了序。这次排序总共付出了4+2+2+2=104+2+2+2=104+2+2+2=10的代价。

注意：算法一定会执行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,j=1w_{i,j}=1wi,j=1；
对于100%100\%100%的数据，保证1≤n≤5001 \le n \le 5001≤n≤500，0≤wi,j<9982443530 \le w_{i,j} < 9982443530≤wi,j<998244353。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=505,P=998244353;intn,w[N][N],fact[N],dp[N];intmain(){scanf("%d",&n);for(inti=1;i<n;++i){for(intj=i;j<=n;++j){scanf("%d",w[i]+j);}}fact[0]=1;for(inti=1;i<=n;++i){fact[i]=1ll*fact[i-1]*i%P;}for(inti=n-1;i;--i){for(intj=i;j<=n;++j){dp[i]=(dp[i]+dp[i+1]+1ll*w[i][j]*fact[n-i])%P;}}printf("%d\n",dp[1]);}