問題
解法
問題を少し変更して $\displaystyle \sum _ {i = 0} ^ {N - 1} |P _ i - P _ {i + 1}|$ の総和を求める問題を考えます。ここで、$P _ 0 = P _ N$ とします (つまり円環上で隣接している項の差分の絶対値の和)。
元の $P$ における $P _ i, P _ j$ が最終的に (円環上で) 隣接するような操作の個数を $C _ {i, j}(M)$ とすると、円環 ver. の答えは $\displaystyle \sum _ {0\leq i\lt j\lt N} |P _ i - P _ j| C _ {i, j}(M)$ です。
$C _ {i, j}$ について、次の予想が立ちます。
- $|j - i| \equiv 1 \pmod{N}$ なる全ての $(i,j)$ で $C _ {i, j}(M)$ は等しい
- $|j - i| \not\equiv 1 \pmod{N}$ なる全ての $(i,j)$ で $C _ {i, j}(M)$ は等しい
この予想が正しいことは、$|j - i| \equiv 1 \pmod{N}$ なる $(i,j)$ に対する $C _ {i, j}(M)$ を $C _ 0(M)$ とし、$|j - i| \not\equiv 1 \pmod{N}$ なる $(i,j)$ に対する $C _ {i, j}(M)$ を $C _ 1(M)$ とすると次の漸化式が立つことから従います。
$$\begin{aligned} C _ 0 (0) &= 1, & C _ 0(M) &= \left(\binom{n}{2} - 2(n-3)\right) C _ 0(M - 1) + 4 C _ 1(M - 1) & \text{for\ } M\gt 0, \cr C _ 1 (0) &= 0, & C _ 1(M) &= 2(n-3) C _ 0(M - 1) +\left(\binom{n}{2} - 4\right) C _ 1(M - 1) & \text{for\ } M\gt 0. \end{aligned}$$
つまり $\begin{pmatrix} C _ 0(M) \cr C _ 1(M) \end{pmatrix} = \begin{pmatrix} \displaystyle\binom{n}{2} - 2(n-3) & 4 \cr 2(n-3) & \displaystyle\binom{n}{2} - 4 \end{pmatrix} ^ M \begin{pmatrix} 1 \cr 0 \end{pmatrix}$ です。
以上で円環 ver. の問題を解けたので、あとは端で隣接する部分の寄与を除けばよいです。
元の $P$ における $P _ i, P _ j$ が最終的に両端に位置するような操作の個数を $D _ {i, j}(M)$ とすると、円環 ver. の答えから $\displaystyle \sum _ {0\leq i\lt j\lt N} |P _ i - P _ j| D _ {i, j}(M)$ を引いた値が元の問題の答えです。
$D _ {i, j}$ について、次の予想が立ちます。
- $i, j$ のうち端である (つまり $0$ または $N - 1$ である) ものの個数が等しい $(i, j)$ の間で $D _ {i, j}$ は等しい
この予想が正しいことは、$i, j$ のうち端であるものの個数が $k$ であるような $i, j$ に対する $D _ {i, j}(M)$ を $D _ {2 - k}(M)$ とすると次の漸化式が立つことから従います。
$$\begin{aligned} D _ 0 (0) &= 1, & D _ 0(M) &= \left(\binom{n}{2} - 2(n - 2)\right) D _ 0(M - 1) + D _ 1(M - 1)& \text{for\ } M\gt 0, \cr D _ 1 (0) &= 0, & D _ 1(M) &= 2(n-2) D _ 0(M - 1) +\left(\binom{n}{2} - (n - 2)\right) D _ 1(M - 1) + 4D _ 2 (M - 1)& \text{for\ } M\gt 0, \cr D _ 2 (0) &= 0, & D _ 2(M) &= (n-3) D _ 1(M - 1) +\left(\binom{n}{2} - 4\right) D _ 2(M - 1)& \text{for\ } M\gt 0, \cr \end{aligned}$$
つまり $\begin{pmatrix} D _ 0(M) \cr D _ 1(M) \cr D _ 2(M) \end{pmatrix} = \begin{pmatrix} \displaystyle \binom{n}{2} - 2(n - 2) & 1 & 0 \cr 2(n-2) & \displaystyle\binom{n}{2} - (n - 2) & 4 \cr 0 & n - 3 &\displaystyle \binom{n}{2} - 4\end{pmatrix} ^ M \begin{pmatrix} 1 \cr 0 \cr 0 \end{pmatrix}$ です。
以上より本問題を $O(N + \log M)$ 時間で解けました。
