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 (failed)

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, the original problem would be easy. The answer would be $$$\sum\limits_{i, j}ij\text{Answer_to_Q1}(i, j)$$$ seems not very difficult