题面

给定长度为 \(n\) 的序列 \(A\) 和 \(B\). 一次 \(k\)-区间轮换是指: 选择 \(A\) 中一个长度为 \(k\) 的子区间, 将区间内的数字进行轮换. 求最大的 \(k\le n\), 满足: 对 \(A\) 进行若干次 \(k\)-区间轮换后, 可以将 \(A\) 变为 \(B\). 若没有 \(k\) 满足条件, 输出 \(-1\).

数据范围

\[ 1\le n\le 2\times 10^5 \]

题解

若序列 \(A,B\) 的元素不完全相同 (不记顺序), 则必然不存在满足题意的 \(k\). 若序列 \(A,B\) 的元素完全相同 (不记顺序), 则取 \(k=2\), 一定可以满足题意, 意即 \(k\) 必然存在.

考虑 \(k\) 可以取 \(n\) 的场景: 此时 \(A\) 本身经过若干次轮换可以得到 \(B\), 即 \(A\) 和 \(B\) 在循环序列意义下是相同的序列. 只需要使用 KMP 算法判断 \(A\) 是否为 \(\overline{BB}\) 的子串即可. 复杂度为 \(O(n)\).

下面考虑 \(k\) 无法取到 \(n\), 即 \(k<n\) 的场景.

排列情形

为方便讨论轮换, 首先考虑 \(A,B\) 是 \(1\) 到 \(n\) 的排列的情形.

\(k\) 可以取 \(n-1\) 的排列

考虑 \(k\) 何时可以取 \(n-1\):

此时, 我们只有两种 \(k\)-区间轮换: \[ \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \alpha:=\pmat{ a_1&a_2&\cdots&a_{n-1}&a_n\\ a_2&a_3&\cdots&a_1&a_n } \]

\[ \beta:=\pmat{ a_1&a_2&a_3&\cdots&a_n\\ a_1&a_3&a_4&\cdots&a_2 } \]

现考虑我们可以通过若干次 \(\alpha,\beta\) 后可以得到的轮换.

首先, 我们可以通过如下操作得到一个长度为 \(3\) 的轮换 \(\tau\):

  1. 任取 \(i\in(1,n)\).

  2. 进行 \(i-1\) 次 \(\beta\) 操作, 得到: \[ \beta^{i-1}=\pmat{ a_1&a_2&a_3&\cdots&a_{n-i+1}&a_{n-i+2}&\cdots&a_{n-1}&a_n\\ a_1&a_{i+1}&a_{i+2}&\cdots&a_n&a_2&\cdots&a_{i-1}&a_i } \]

  3. 再进行 \(n-i\) 次 \(\alpha\) 操作, 得到: \[ \newcommand{\algn}[1]{\begin{aligned} #1 \end{aligned}} \algn{ \tau_{i,1,n}:=\alpha^{n-i}\beta^{i-1}&= \pmat{a_1&a_2&\cdots&a_{i-1}&a_i&a_{i+1}&\cdots&a_{n-1}&a_n\\a_n&a_2&\cdots&a_{i-1}&a_1&a_{i+1}&\cdots&a_{n-1}&a_i}\\ &=(a_i\ a_1\ a_n) } \]

由于 \(\newcommand{\mfk}{\mathfrak}\mfk A_n\) 的一个生成元系为: \[ \newcommand{\agle}[1]{\left\langle #1 \right\rangle}\newcommand{\brac}[1]{\left( #1 \right)}\mfk A_n=\agle{\brac{1\ 2\ 3},(1\ 2\ 4),\cdots,(1\ 2\ n)} \] 故自然地, 我们猜想: 经过若干次 \(\tau\) 操作后, 我们可以得到所有 \(\mfk A_n\) 的元素. 为证明该命题, 只需证明任意两个对换的乘积均可以通过若干次 \(\tau\) 操作得到即可. 证明可以采取构造法, 构造放在本文末尾, 此处暂不做证明.

若 \(A, B\) 的奇偶性相同, 则 \(\delta_{BA}:=BA^{-1}\in\mfk A_n\). 将 \(\delta_{BA}\) 作用于 \(A\) 即可得到 \(B\). \(k=n-1\) 满足条件.

若 \(A,B\) 的奇偶性不同, 则需要考虑 \(\alpha,\beta\) 的奇偶性. 因为 \(\alpha,\beta\) 是长度为 \(n-1\) 的轮换, 其可以表示为 \(n-2\) 个对换的乘积, 奇偶性与 \(n\) 的奇偶性相同. 则根据 \(n\) 的奇偶性讨论:

  1. 若 \(n\) 是偶数, 则 \(\alpha,\beta\) 均为偶变换. \(A\) 经过若干次偶变换后, 奇偶性不变, 无法得到 \(B\). 此时 \(k\) 无法取 \(n-1\)​.
  2. 若 \(n\) 是奇数, \(\alpha\) 是奇变换. 令 \(A'=\alpha A\), 则 \(A'\) 与 \(B\) 的奇偶性相同, \(\delta_{BA'}=BA'^{-1}\in\mfk A_n\). 将 \(\delta_{BA'}\alpha\) 作用于 \(A\) 即可得到 \(B\), \(k=n-1\) 满足条件.
\(k\) 不能取 \(n-1\) 的排列

考虑 \(n\) 是偶数且 \(A,B\) 奇偶性不同的情况下, \(k\) 能否取 \(n-2\). 设 \(B[1]=A[i]\), 则经过若干次 \(k\)-区间轮换 \(\delta_1\), 可以得到 \(A'=\delta_1A\), 满足 \(A'[1]=A[i]=B[1]\). 子序列 \(A'[2:n],B[2:n]\) 是两个长度为 \(n-1\) 的序列, 由于 \(n-1\) 是奇数, 故一定可以对 \(A'[2:n]\) 通过若干次 \(k\)-区间轮换 \(\delta_2\) 得到 \(B[2:n]\). 此时, \(B=\delta_2\delta_1A\). \(k=n-2\) 满足条件.

一般序列情形

最后考虑回 \(A,B\) 是一般序列的情况. 每一组相同的数字里, 设置位置编号作为区分. 将 \(A,B\) 映射到长度为 \(n\) 的排列, 满足:

  1. 若 \(X[i]<X[j]\), 映射后满足 \(f(X)[i]<f(X)[j]\).
  2. 若 \(X[i]=X[j], i<j\), 映射后满足 \(f(X)[i]<f(X)[j]\).

则 \(f(A)\) 和 \(f(B)\) 是两个排列, 且若 \(\delta f(A)=f(B)\), 则 \(f^{-1}(\delta) A=B\). 应用之前排列的结论, 若 \(n\) 是奇数或 \(f(A),f(B)\) 奇偶性相同, 则 \(k\) 可以取到 \(n-1\). 若 \(n\) 为偶数且 \(f(A),f(B)\) 奇偶性不同, 则根据是否有重复元素讨论:

  1. 若 \(A,B\) 中没有重复元素, 则 \(f\) 是双射, \(A,B\) 和 \(f(A),f(B)\) 同构, \(k\) 的取值无法取到 \(n-1\).
  2. 若 \(A\) 中有重复元素, 则任取 \(A[i]=A[j]\), 交换 \(f(A)[i]\) 和 \(f(A)[j]\) 的位置得到 \(C=\varepsilon f(A)\). 此时若 \(\delta C=f(B)\), 则 \(f^{-1}(\delta) A=f^{-1}(\delta)f^{-1}(\varepsilon) A=B\). 而 \(C\) 和 \(f(B)\) 奇偶性相同, 故 \(k\) 可以取 \(n-1\).

结论总结

  1. 若 \(A, B\) 元素不同, 则不存在 \(k\).
  2. 若 \(A\) 是 \(\overline{BB}\) 的子串, 则最大 \(k=n\).
  3. 否则:
    • 若 \(n\) 为奇数, 则最大 \(k=n-1\).
    • 若 \(n\) 为偶数且 \(A\) 中有重复元素, 则最大 \(k=n-1\).
    • 若 \(n\) 为偶数且 \(A,B\) 奇偶性相同, 则最大 \(k=n-1\).
    • 若 \(n\) 为偶数且 \(A,B\) 奇偶性不同, 则最大 \(k=n-2\).

复杂度分析

判断 \(k\) 可否取 \(n\), KMP 算法复杂度为 \(O(n)\).

求 \(A,B\) 逆序对数, 复杂度为 \(O(n\log n)\).

总复杂度为 \(O(n\log n)\)​.

补充证明

任意两个对换的乘积均可以由若干次 \(\tau\) 操作得到. 证明如下:

对于任意 \(i,j\in(1,n)\) 定义 \(\sigma\) 操作如下: \[ \sigma_{i,j,1,n}:=\tau_{j,n,i}\tau_{i,1,n}= \pmat{ a_1&a_i&a_j&a_n\\ a_i&a_1&a_n&a_j }=(a_1\ a_i)(a_n\ a_j) \] 则任意两个对换的乘积均可以表示为下列对换乘积的一种:

\[ \algn{ (a_i\ a_1)(a_i\ a_n)&=(a_i\ a_n\ a_1)=\tau_{1,n,i}\tau_{i,1,n}\\ (a_i\ a_j)(a_i\ a_n)&=(a_i\ a_n\ a_j)=\tau_{j,i,1}\tau_{1,n,i}\tau_{i,1,n}\\ (a_i\ a_j)(a_i\ a_t)&=(a_i\ a_t\ a_j)=\sigma_{1,n,j,i}\tau_{i,t,j}\tau_{j,i,t}\sigma_{i,t,1,n}\\ (a_i\ a_1)(a_s\ a_n)&=\sigma_{i,s,1,n}\\ (a_i\ a_j)(a_1\ a_n)&=\sigma_{n,1,i,j}\sigma_{i,j,1,n}\\ (a_i\ a_j)(a_s\ a_n)&=\sigma_{1,s,j,n}\sigma_{j,n,i,s}\sigma_{i,s,1,n}\\ (a_i\ a_j)(a_s\ a_t)&=\sigma_{1,n,j,t}\sigma_{j,t,i,s}\sigma_{i,s,1,n}\\ } \] 上述表示并非唯一. 由于情况有限, 也可以通过打表法求出乘积表示.