P7623 [AHOI2021 Junior] Collecting Clothes

AHOI2021 Junior T3. **You may choose to skip the background section.** Xiaoxue, who was obsessed with the “flea-torturing” game, did not notice how much time had passed. When she looked up, she found that the sky had changed dramatically. The sky was murky yellow, and a strange smell hit her face. She did not expect that in the highly developed year 2077, a sandstorm could still happen in the city. This surreal scene made Xiaoxue suspect that the Flea King had shown his power. “Stop staring, hurry up and collect the clothes!” Xiaokeke suddenly remembered.

Looking at so many clothes covered with dust, the two of them felt helpless. Also, some clothes cannot be washed together. To sort them into categories, Xiaokeke gave each piece of clothing a distinct label from $1 \sim n$, where $n$ is the number of clothes. It would be more convenient to wash them after arranging the clothes in the order $1,2,\ldots,n$. Xiaokeke also thought that we can take out a continuous segment of the clothes rack, reverse its order by hand, and then put it back. As an OI contestant, you immediately abstracted Xiaokeke’s algorithm for sorting clothes: let the label of the $i$-th piece of clothing from left to right initially be $p_i$. Enumerate $i$ in the order $1,2,\ldots,n-1$. Let the smallest label among $p_i,p_{i+1},\ldots,p_n$ be $p_j$. Then reverse $p_i,p_{i+1},\ldots,p_{j-1},p_j$ from left to right, turning it into $p_j,p_{j-1},\ldots,p_{i+1},p_i$. Xiaoxue soon discovered that although Xiaokeke’s algorithm looks impressive, it is actually quite silly—in the dim light, nobody can tell the labels on the clothes. So they could only return to the room for rational enjoyment: assume the cost of reversing the interval $[i,j]$ is $w_{i,j}$. The cost of one sorting process is the sum of the operation costs of all reversals. Now Xiaokeke wants to know, when $p$ ranges over all $n!$ permutations, the total sorting cost over all cases. You only need to output the answer modulo $998244353$ ($=7 \times 17 \times 2^{23} + 1$, a prime).

The first line contains an integer $n$. The next $n-1$ lines: in line $i$ $(1 \le i \le n)$, there are $n - i + 1$ space-separated integers, where the $j$-th one denotes $w_{i,j}$.

One line containing an integer, which is the answer modulo $998244353$.

[Sample 1 Explanation] Let us give an example. When $p=[3,2,5,1,4]$, the steps of the algorithm are as follows: - When executing $i=1$, the minimum among $p_1,p_2,p_3,p_4,p_5$, i.e. $3,2,5,1,4$, is $p_4=1$. We reverse interval $[1,4]$, and $p$ becomes $[1,5,2,3,4]$, with cost $w_{1,4}=4$. - When executing $i=2$, the minimum among $p_2,p_3,p_4,p_5$, i.e. $5,2,3,4$, is $p_3=2$. We reverse interval $[2,3]$, and $p$ becomes $[1,2,5,3,4]$, with cost $w_{2,3}=2$. - When executing $i=3$, the minimum among $p_3,p_4,p_5$, i.e. $5,3,4$, is $p_4=3$. We reverse interval $[3,4]$, and $p$ becomes $[1,2,3,5,4]$, with cost $w_{3,4}=2$. - When executing $i=4$, the minimum among $p_4,p_5$, i.e. $5,4$, is $p_5=4$. We reverse interval $[4,5]$, and $p$ becomes $[1,2,3,4,5]$, with cost $w_{4,5}=2$. As you can see, after the $i$-th step ends, the positions $[1,i]$ of the sequence are exactly the clothes labeled $[1,i]$. After the algorithm finishes, $p$ is sorted. The total cost of this sorting is $4+2+2+2=10$. **Note: The algorithm will always execute $n-1$ steps, and it will not terminate early even if it becomes sorted in the middle.** [Constraints and Hints] **Hint: The input size of this problem is large, so please avoid overly slow input methods.** - For $25\%$ of the testdata, $1 \le n \le 9$. - For $50\%$ of the testdata, $1 \le n \le 16$. - For $70\%$ of the testdata, $1 \le n \le 50$. - For another $15\%$ of the testdata, $w_{i,j}=1$. - For $100\%$ of the testdata, $1 \le n \le 500$, $0 \le w_{i,j} < 998244353$. Translated by ChatGPT 5