20250820 T1 题解

· · 个人记录

观前提示：并非严谨。

简化题意

有数列 \{1,2,\cdots,n\}，给定 a，b，你可以任意执行以下操作任意次：

求最后的数列种类数。

solution

考虑将操作泛化为置换。记第一个操作对应 n 阶置换 A，第二个操作对应 n 阶置换 B。

考虑到两个置换其实是翻转，所以有 A^2=B^2=I。

所以实际上的操作序列只有四种：(AB)^k、(BA)^kB、(AB)^kA、(BA)^k。

另外，有 (AB)(BA)=A(BB)A=AA=I，即 BA=(AB)^{-1}。所以 (BA)^k=(AB)^{-k}，(BA)^kB=(AB)^{-k-1}A。

所以实际上是两种：(AB)^k 和 (AB)^kA。

如果这两类操作本质相同，则应该存在 A=(AB)^k。

首先可以知道 A=I 或 B=I 是有解的。

假设 AB 的阶为 n，A \neq I。

$$ A=(AB)^{n/2},B=(AB)^{n/2+1}\\ I=B^2=(AB)^{n+2}\\ n|n+2\\ n=1,2\\ $$ $n=1$，$AB=I \Rightarrow A=(AB)^k=I$，矛盾。 $n=2$，$A=AB \Rightarrow B=I

也即 A \neq I 时 B=I。

所以充要条件就是 A=I 或 B=I。

所以现在的问题就是求出 AB 的阶，这个就是 AB 的每个环长的 lcm。