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)$$$. 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$$$.
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.
3. zzfantani's contribution splitting idea