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]$$$, $$$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 = 1 \times 2 + 2 \times 3 + 3 \times 1 = 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$$$. $$$n \leq 300;\,k \leq \frac{n(n-1)}{2}$$$.
2. Some trials
First, I considered fixing $$$p_i = j$$$, and tried 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 gave me false hope, but I did not know how to push it forward (maybe this approach works and we can make it 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$$$ sits 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 zzafanti's blog (in Chinese).
3. zzafanti'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 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 considered. 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$$$, zzafanti considers the dual of (1):
$$$\sum\limits_{i=1}^n i \sum\limits_{j=1}^{p^{-1}(i)} [p_j > 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$$$, and $$$mn := max(0, j - i + 1)$$$, Then, similar to Leetcode 629,
$$$f_{i, j} = \sum\limits_{p = mn} ^ j f_{i - 1, p}$$$ (Because $$$i$$$ can contributes to at most $$$i - 1$$$ inversion).
Obviously, the calculation of $$$f$$$ could be accelerated via prefix array (i.e., $$$pf$$$ in the following code).
We denote $$$g_{i,j}$$$ as the contribution of Eq.(1), when $$$i$$$ is inserted and there is $$$j$$$ inversion. If $$$i$$$ contributes $$$p$$$ inversion, $$$i$$$ sites on the $$$i - p$$$ place, therefore:
$$$g_{i, j} = \sum\limits_{p = 0} ^ {i - 1}(g_{i-1, j - p} + f_{i - 1, j - p}i(i - p)) = \sum\limits_{p = 0} ^ {i - 1}(g_{i-1, j - p} + i(j - p)f_{i - 1, j - p} + i(i - j)f_{i - 1, j - p})$$$
By changing $$$j - p$$$ into another variable:
$$$g_{i, j} = \sum\limits_{p = mn} ^ {j}(g_{i-1, p} + \sum\limits_{p = 0} ^ {i - 1}ipf_{i - 1, p} + i(i - j)f_{i - 1, p})$$$.
Therefore, we need to create two prefix arrays $$$pg$$$ and $$$pfg$$$ to deal with $$$\sum\limits_{p = mn} ^ {j}g_{i-1, p}$$$ and $$$\sum\limits_{p = mn} ^ {j}p \times f_{i-1, p}$$$, respectively.
Finally, let's consider $$$h_{i,j}$$$, which is the contribution of Eq. (2), when $$$n-i+1$$$ is inserted and there is $$$j$$$ inversion. Why $$$n-i+1$$$? Because we are inserting reversely, and the $$$i$$$-th element inserted is $$$n-i+1$$$. If $$$n-i+1$$$ contributes $$$p$$$ inversion, $$$\sum\limits_{j=1}^{p^{-1}(i)} [p_j > i] = p$$$ by definition. Therefore,
$$$h_{i, j} = \sum\limits_{p = 0}^{i - 1}(h_{i-1,j-p} + f_{i-1, j-p}(n-i+1)p) = \sum\limits_{p = 0}^{i - 1}(h_{i-1,j-p} + (n-i+1)(j-(j-p))f_{i-1, j-p})$$$.
By change $$$j-p$$$ into a new variable $$$p$$$, and discard some invalid indices (their corresponding values are $$$0$$$):
$$$h_{i, j} = \sum\limits_{p = mn}^{j}(h_{i-1, p} + (n-i+1)(j-p)f_{i-1, p})$$$.
We need another prefix array $$$ph$$$ to deal with $$$\sum\limits_{p = mn} ^ {j}h_{i-1, p}$$$ in our code. Please kindly note that the we already deal with the range sum $$$\sum\limits_{p = mn} ^ {j}p \times f_{i-1, p}$$$ when calculating $$$g$$$ (a coincidence), therefore no additional prefix array is further needed to handle this. We use $$$7$$$ arrays in total ($$$f$$$, $$$g$$$, $$$h$$$, $$$pf$$$, $$$pg$$$, $$$ph$$$, and $$$pfg$$$). The memory limit of this problem is only $$$128MB$$$, therefore it might be too expensive to use $$$7 \times n \times k \times sizeof(int) \sim 7*300*(300*299//2)*4/(1024*1024) \sim 360MB$$$, so we use a "Rolling-DP" (i.e., dp array with only the current state and the previous state) instead. The complexity is $$$O(nk)$$$.
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.
Comments (0)
