E - Reverse and Inversion Editorial
by 
PCTprobability
\(2\) つの解法があるため、両方を解説します。
1.操作の特徴によって得られる \(\mathrm{O}(N\log M)\) 解法：https://atcoder.jp/contests/arc154/editorial/5556
2.dp を高速化することによって得られる \(\mathrm{O}(N\log M)\) 解法：本解説
\(2\) 個の解説の前半パートは全く同じものです。
\(f(P)\) は、\(\sum_{i=1}^{N} (j<i,P_j > P_i\) を満たす \(j\) の個数\()\times i -\sum_{i=1}^{N} (i<j,P_i > P_j\) を満たす \(j\) の個数\()\times i\) と等しいです。
以降、\(g(i):=「(j<i,P_j>P_i\) を満たす \(j\) の個数\()-(i<j,P_i>P_j\) を満たす \(j\) の個数\()\)」 とします。また、\(\mathrm{inv}(i) := 「P_j = i\) を満たす整数 \(j\) 」とします。
すると、\(g(i) = i - P_i\) が成り立ちます。
証明
$P=(1,2,\dots,N)$ のとき、$P_x=x$ であるため「$g(x)=x-x(=0)$」が成り立ちます。 ここで、$x$ の左にある要素を $1$ 個選び $x$ の右に移動させます。すると、その要素と $x$ の大小関係によらず $g(\mathrm{inv}(x))$ は $1$ 減ります。$x$ の右にある要素を左に移動させたときも同様に $1$ 増えます。 よって、$g(i)=i-P_i$ が成り立ちます。よって、\(f(P) = \sum_{i=1}^{N} i(i-P_i)\) が成り立ちます。なので、全ての整数対 \((i,j)\) に対して \(M\) 回の操作終了後に \(P_i=j\) となる通り数が求められれば良いです。
\(\mathrm{dp}[i][j][k] :=「 i\) 回操作したときに、始めに \(j\) 番目にあった要素が \(k\) 番目に移動するような通り数」とします。ここで、\(\mathrm{dp}[i]\) を行列とみなすと \(\mathrm{dp}[i] \times \mathrm{dp}[j] = \mathrm{dp}[i+j]\) が成り立ちます。ですが、このまま行列累乗をすると計算量が \(\mathrm{O}(N^3\log M)\) となり間に合いません。
\(\mathrm{dp}[1]\) を考えます。\(j,k\) が一致しているかどうかで場合分けすると、以下のようになります。
- \(j=k\) のとき、\(\mathrm{dp}[1][j][k] = \min(j,N-j+1) + \frac{j(j-1)}{2} + \frac{(N-j)(N-j+1)}{2}\)
- \(j\neq k\) のとき、\(\mathrm{dp}[1][j][k] = \min(\min(j,k),N-\max(j,k)+1)\)
ここで、重要な性質として以下が成り立ちます。
- 整数対 \((a,b),(c,d)\) に対して、\( \min(\min(a,b),N-\max(a,b)+1)= \min(\min(c,d),N-\max(c,d)+1)\) ならば任意の整数 \(i\) に対して \(\mathrm{dp}[i][a][b]=\mathrm{dp}[i][c][d]\) が成り立つ。
証明
$i$ についての帰納法で証明します。 任意の整数 $a,b,c(a\le \frac{N}{2},a < b,c \le N-a+1)$ に対して、$\mathrm{dp}[i+1][a][b]=\mathrm{dp}[i+1][a][c]$ であることが言えれば十分です。 $\mathrm{dp}[i]$ の全ての行、列ごとの要素の総和は等しいので、これを $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}$ よって示されました。この性質により、\(\mathrm{dp}[i]\) を \(N + \left\lfloor\frac{N}{2}\right\rfloor\) 個の要素を持つことで表現できます。また、証明内部の式を扱うことによって \(\mathrm{dp}[i]\) と \(\mathrm{dp}[j]\) の乗算を \(\mathrm{O}(N)\) で行うことが出来ます。
よって、先ほどの行列累乗を \(\mathrm{O}(N\log M)\) で行うことができ、\(\sum_{i=1}^{N} i(i-P_i)\) の総和もその結果から \(\mathrm{O}(N + \log M)\) で求めることが出来ます。
上記より、本問題を \(\mathrm{O}(N\log M)\) で解くことが出来ます。これは十分高速です。
posted:
last update: