E - Reverse and Inversion Editorial by evima
We will explain two solutions:
\(\mathrm{O}(N\log M)\) solution from the characteristics of the operation: https://atcoder.jp/contests/arc154/editorial/5599
\(\mathrm{O}(N\log M)\) solution from optimization of DP: Here
\(f(P)\) equals \(\sum_{i=1}^{N} (\)the number of indices \(j\) such that \(j<i,P_j > P_i)\times i -\sum_{i=1}^{N} (\)the number of indices \(j\) such that \(i<j,P_i > P_j)\times i\).
Below, let \(g(i):= (\)the number of indices \(j\) such that \(j<i,P_j > P_i)-(\)the number of indices \(j\) such that \(i<j,P_i > P_j)\). Additionally, let \(\mathrm{inv}(i) := (\)the index \(j\) such that \(P_j = i)\).
Then, we have \(g(i) = i - P_i\).
Proof
For $P=(1,2,\dots,N)$, we have $P_x=x$, so $g(x)=x-x(=0)$. Now, let us choose an element to the left of $x$ and move it to the right of $x$. Then, $g(\mathrm{inv}(x))$ decreases by $1$, regardless of whether that element is larger or smaller than $x$. Similarly, when an element to the right of $x$ is moved to the left of $x$, $g(\mathrm{inv}(x))$ increases by $1$. Thus, $g(i)=i-P_i$.Thus, we have \(f(P) = \sum_{i=1}^{N} i(i-P_i)\). Therefore, for all pairs of integers \((i,j)\), we want to find the number of ways to repeat the operation \(M\) times so that \(P_i=j\) in the end.
Let \(\mathrm{dp}[i][j][k] := (\)the number of ways to repeat the operation \(i\) times so that the \(j\)-th element from the left goes to the \(k\)-th from the left\()\). If we see \(\mathrm{dp}[i]\) as a matrix, we have \(\mathrm{dp}[i] \times \mathrm{dp}[j] = \mathrm{dp}[i+j]\). However, finding the power of this matrix naively takes \(\mathrm{O}(N^3\log M)\) time, which is too much.
Consider \(\mathrm{dp}[1]\). We classify the case according to whether \(j\) and \(k\) are equal, and obtain the following.
- If \(j=k\), we have \(\mathrm{dp}[1][j][k] = \min(j,N-j+1) + \frac{j(j-1)}{2} + \frac{(N-j)(N-j+1)}{2}\).
- If \(j\neq k\), we have \(\mathrm{dp}[1][j][k] = \min(\min(j,k),N-\max(j,k)+1)\).
Here is an important property.
- For pairs of integers \((a,b)\) and \((c,d)\), if \( \min(\min(a,b),N-\max(a,b)+1)= \min(\min(c,d),N-\max(c,d)+1)\) holds, then \(\mathrm{dp}[i][a][b]=\mathrm{dp}[i][c][d]\) holds for any integer \(j\).
Proof
We use induction on $i$. It is enough to show that $\mathrm{dp}[i+1][a][b]=\mathrm{dp}[i+1][a][c]$ for any integers $a,b,c(a\le \frac{N}{2},a < b,c \le N-a+1)$. All row sums and column sums of $\mathrm{dp}[i]$ are the same, so let us denote that value by $S$. $\begin{aligned} \mathrm{dp}[i+1][a][b] &= \sum_{j=1}^{N} \mathrm{dp}[i][a][j] \times \mathrm{dp}[1][j][b] \\ &= \left(\sum_{j=a+1}^{N-a+1}\mathrm{dp}[i][a][j] \times \mathrm{dp}[1][j][b]\right) + \left(\sum_{j \le a | j > N-a+1}^{} \mathrm{dp}[i][a][j] \times \mathrm{dp}[1][j][b]\right) \\ &= \left(\mathrm{dp}[i][a][a+1] \times \sum_{j=a+1}^{N-a+1}\mathrm{dp}[1][j][b]\right) + \left(\sum_{j \le a | j > N-a+1}^{} \mathrm{dp}[i][a][j] \times \mathrm{dp}[1][j][b]\right) \\ &= \left(\mathrm{dp}[i][a][a+1] \times \left(S-\sum_{j \le a | j > N-a+1}^{}\mathrm{dp}[1][j][b]\right)\right) + \left(\sum_{j \le a | j > N-a+1}^{} \mathrm{dp}[i][a][j] \times \mathrm{dp}[1][j][b]\right) \\ &= \left(\mathrm{dp}[i][a][a+1] \times \left(S-\sum_{j \le a | j > N-a+1}^{}\mathrm{dp}[1][j][c]\right)\right) + \left(\sum_{j \le a | j > N-a+1}^{} \mathrm{dp}[i][a][j] \times \mathrm{dp}[1][j][c]\right) \\ &= \left(\sum_{j=a+1}^{N-a+1}\mathrm{dp}[i][a][j] \times \mathrm{dp}[1][j][c]\right) + \left(\sum_{j \le a | j > N-a+1}^{} \mathrm{dp}[i][a][j] \times \mathrm{dp}[1][j][c]\right) \\ &= \mathrm{dp}[i+1][a][c] \end{aligned}$ This completes the proof.From this property, \(\mathrm{dp}[i]\) can be represented by maintaining \(N + \left\lfloor\frac{N}{2}\right\rfloor\) elements. Additionally, the formula in the proof enables multiplication of \(\mathrm{dp}[i]\) and \(\mathrm{dp}[j]\) in \(\mathrm{O}(N)\) time.
Thus, one can find the power of the matrix in \(\mathrm{O}(N\log M)\) time, and use the result to find the sum of \(\sum_{i=1}^{N} i(i-P_i)\) in \(\mathrm{O}(N + \log M)\) time.
Therefore, the problem can be solved in \(\mathrm{O}(N\log M)\) time, which is fast enough.
posted:
last update: