P2528 [SHOI2001] New Task on Sorting Workload

Suppose we define the parameter of the $i$-th item as $A_i$. Sorting means arranging $A_1, \cdots ,A_n$ in ascending order. If $i < j$ and $A_i > A_j$, then $(i, j)$ is an “inversion pair.” The SORT company specializes in providing sorting services. Their pricing is based on the number of inversion pairs among the items to be sorted, called the “inversion count.” Grant is a sorter at this company. He wants to know, among all sequences of $n$ items with distinct parameters, how many have inversion count $t$, and to also provide one lexicographically smallest such sequence. “Smallest” means: for two sequences $(A_1,A_2,\cdots ,A_n)$ and $(B_1,B_2,\cdots ,B_n)$, if there exists $1 \le i \le n$ such that $(A_1,A_2,\cdots ,A_{i-1})=(B_1,B_2,\cdots ,B_{i-1})$ and $A_i < B_i$.

Two integers $n$ and $t$ ($1 \le n \le 20$, $0 \le t \le \dfrac{n\cdot (n-1)}{2}$).

- The first line contains the number of sequences of $n$ distinct items whose inversion count is $t$. - The second line is the requested sequence of item parameters. Assume the $n$ items are labeled $1$ to $n$.

Translated by ChatGPT 5