置换的刻画们

以下置换的定义域都在 \(\{1, 2, \dots, n\}\) 上。

复合

先使用双行记号来刻画。

若

\[\sigma = \begin{pmatrix}1 & 2 & \dots & n \\p_1 & p_2 & \dots & p_n \end{pmatrix} , \pi = \begin{pmatrix}p_1 & p_2 & \dots & p_n \\q_1 & q_2 & \dots & q_n \end{pmatrix} \]

则

\[\pi \circ \sigma = \begin{pmatrix}1 & 2 & \dots & n \\q_1 & q_2 & \dots & q_n \end{pmatrix} \]

逆置换

因为置换是双射，所以左逆置换和右逆置换必定存在且唯一，且它们相等。形式化地说，对于任意置换 \(\sigma\)，存在唯一的 \(\sigma^{-1}\) 使得

\[\sigma^{-1} \circ \sigma = \sigma \circ \sigma^{-1} = \text{id} \]

其中 \(\text{id} = \begin{pmatrix}1 & 2 & 3 & \cdots & n \\1 & 2 & 3 & \cdots & n \end{pmatrix}\)，为置换的幺元。不难通过两行的相等性得到幺元也不分左右。

这样刻画复合的好处是：一眼就可以盯出一个置换的逆置换。

若

\[\sigma = \begin{pmatrix}1 & 2 & \dots & n \\p_1 & p_2 & \dots & p_n \end{pmatrix} \]

则

\[\sigma^{-1} = \begin{pmatrix}p_1 & p_2 & \dots & p_n \\1 & 2 & \dots & n \end{pmatrix} \]

反代入此刻画，容易验证

\[\sigma^{-1} \circ \sigma = \sigma \circ \sigma^{-1} = \text{id} \]

成立。

通过这样盯出结合律也是不难的，这里就不演示了。形式化地说，对于任意 \(a\)、\(b\)、\(c\)，有 \((a \circ b) \circ c = a \circ (b \circ c)\)。

没有交换律，不然上面也不会区分左右逆元。

应用：CF1792D Fixed Prefix Permutations

简要题意

给定 \(n\) 个长度皆为 \(m\) 的置换 \(a_1, a_2, \dots, a_n\)，对于每个 \(1 \leq i \leq n\) 的 \(i\)，报告：

\[\max_{1 \leq j \leq n} f(a_i \circ a_j) \]

\(f(\sigma)\) 定义为最大的 \(i\) 满足 \(\forall j \in \{1, 2, \dots, i\}，\sigma(j) = j\)。

\(1 \leq n \leq 5 \times 10^4, 1 \leq m \leq 10\)。

分析

\((\sigma \circ \pi)(j) = j\) 等价于 \((\sigma \circ \pi)(j) = \text{id}(j)\)，两边同乘 \(\pi^{-1}\)：

\[(\sigma \circ \pi \circ \pi^{-1})(j) = (\text{id} \circ \pi^{-1})(j) \iff \\(\sigma \circ (\pi \circ \pi^{-1}))(j) = (\pi^{-1})(j)\iff \\\sigma(j) = \pi^{-1}(j) \]

因此 \(f(\sigma \circ \pi)\) 可以重写成，最大的 \(i\)，满足 \(\forall j \in \{1, 2, \dots, i\}，\sigma(j) = \pi^{-1}(j)\)。

不难发现，这是 \(\text{LCP}(\sigma, \pi^{-1})\) 的定义。

问题现在转换为了经典的多模式串 \(\text{LCP}\) 匹配，将所有 \(a_i^{-1}\) 事先插入字典树，对于每个询问只需 trie 上游走 \(O(m)\) 次即可得到答案。

时空复杂度 \(\Theta(nm)\)。

轮换分解