Problem Link: https://www.luogu.com.cn/problem/P10254
1. Problem Statement
Given a permutation $$$p$$$ of length $$$n$$$, define $$$Inv(p)$$$ to be the inversion of $$$p$$$ and $$$W(p) := \sum\limits_{i=1}^n ip_i$$$. For example, if $$$p = [1, 2, 3]$$$, the $$$W(p) = 1 \times 1 + 2 \times 2 + 3 \times 3 = 14$$$. Given integers $$$n$$$ and $$$k$$$, compute $$$\sum\limits_{p \in S_n,\,Inv(p) = k} W(p)$$$ modulo $$$998244353$$$. For example, if $$$n = 3, k = 2$$$, then there are two permutations whose inversion is $$$2$$$: $$$[2, 3, 1]$$$ ($$$W = 1 \times 2 + 2 \times 3 + 3 \times 1 = 11$$$) and $$$[3, 1, 2]$$$ ($$$W = 3 \times 1 + 1 \times 2 + 2 \times 3 = 11$$$). Therefore, the answer is the sum of $$$W$$$ of these two permutations, i.e., $$$11 + 11 = 22$$$. Also, the answer for $$$n=7,\,k=5$$$ is $$$22066$$$.
2. Some trials
First, I considered fix $$$p_i = j$$$, and try to figure out:
Q1: How many permutations are there such that $$$p_i = j$$$ and the inversion is $$$k$$$?
If Q1 were solved efficiently, the original problem would be easy. The answer would be $$$\sum\limits_{i, j}ij\text{Answer_to_Q1}(i, j)$$$. If we remove the clause "$$$p_i = j$$$" from $$$Q_1$$$, $$$Q_1$$$ becomes a common Leetcode-hard problem (Leetcode 629). This observation gives me false hope, but I do not know how to push it forward (maybe this approach will work and we can make it as a CF problem!).
After struggling for several hours, I discussed with Tobo. He offered some brilliant ideas. First, we can insert from $$$1$$$ to $$$n$$$. For each integer $$$i$$$ contributing $$$p$$$ inversion, it is located at the $$$(i - p)$$$ — th place. For example, we first insert $$$1$$$. Then we insert $$$i = 2$$$ to the permutation $$$[1]$$$. If the number $$$2$$$ contributes one inversion, the permutation is $$$[2, 1]$$$, and $$$2$$$ is located at the $$$2-1 = 1$$$-th place. If the number $$$2$$$ contributes no inversion, the permutation is $$$[1, 2]$$$, and $$$2$$$ is located at the $$$2-0 = 2$$$-th place. No other possibilities.
Q2: For elements after $$$i$$$, their contributions might change after $$$i$$$ is inserted into the permutation. How to deal with the change?
For example, if we insert $$$2$$$ after $$$1$$$, the contribution of $$$1$$$ is not changed. However, if we insert $$$2$$$ before $$$1$$$, the contribution of $$$1$$$ changes from $$$1$$$ to $$$2$$$. Before the insertion, $$$1$$$ sits on the first place, contributing $$$1$$$. However, after $$$2$$$ is inserted in front of $$$1$$$, $$$1$$$ sites on the second place and its contribution becomes $$$2$$$! I considered the suffix sum of the elements after $$$i$$$, because when $$$i$$$ is inserted, the contribution of elements after $$$i$$$ actually increases the same as their sum ("suffix sum"), but I find the "suffix sum" difficult to deal with. I failed to get an idea until I read zzfantani's blog (in Chinese).
3. zzfantani's contribution splitting idea
What if we ignore the elements located after $$$i$$$? In fact, we are calculating
$$$\sum\limits_{i=1}^n i \sum\limits_{j=1}^{p^{-1}(i)} [p_j \leq p_i]$$$ (1),
i.e., given an element $$$i$$$, for elements sits before $$$i$$$ (including $$$i$$$ itself), only the elements $$$\leq i$$$ are taken into account, the elements $$$>i$$$ are not taken into account. In the above example, if we insert $$$[1]$$$, the contribution of $$$1$$$ is $$$1$$$, if we insert $$$2$$$ before $$$1$$$, the contribution of $$$2$$$ is $$$2$$$, and the contribution of $$$1$$$ is still $$$1$$$. The contribution that $$$2$$$ makes to $$$1$$$, which is $$$1$$$, is omitted from the above calculation. Let's verify Eq. (1): For $$$i = 1$$$, $$$p^{-1}(1) = 2$$$ (because $$$1$$$ sits at the second place in $$$[1, 2]$$$), $$$\sum\limits_{j=1}^{2} [p_j \leq 1] = [p_1 \leq 1] + [p_2 \leq 1] = 0 + 1 = 1$$$, so the contribution of $$$1$$$ is counted as $$$1$$$. Similarly, the contribution of $$$2$$$ is counted as $$$2$$$.
So, instead of consider the annoying "suffix sum" in chapter $$$3$$$, zzfantani considers the dual of (1):
$$$\sum\limits_{i=1}^n i \sum\limits_{j=1}^{p^{-1}(i)} [p_j > p_i]$$$ (2),
which could be calculated via inserting reversely, i.e., from $$$n$$$ to $$$1$$$.
4. Implementation
Let $$$f_{i, j}$$$ be the number of size-$$$i$$$ permutation with inversion $$$j$$$. Let $$$mn := max(0, j - i + 1)$$$, Then, similar to Leetcode 629:
$$$f_{i, j} = \sum\limits_{p = mn} ^ j f_{i - 1, p}$$$.
5. Please comment on the estimated difficulty of this problem
I think it is a $$$2700$$$ level problem. What is your opinion? StarSilk marked it as a $$$2600$$$-level problem.
