专栏文章

20250820 T1 题解

aanalysis
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio8a348
此快照首次捕获于
2025/12/02 14:59
3 个月前
此快照最后确认于
2025/12/02 14:59
3 个月前
查看原文
观前提示：并非严谨。

简化题意

有数列 {1,2,⋯ ,n}\{1,2,\cdots,n\}，给定 aa，bb，你可以任意执行以下操作任意次：
  • reverse [1,a][1,a]
  • reverse [n−b+1,n][n-b+1,n]
求最后的数列种类数。

solution

考虑将操作泛化为置换。记第一个操作对应 nn 阶置换 AA，第二个操作对应 nn 阶置换 BB。
考虑到两个置换其实是翻转，所以有 A2=B2=IA^2=B^2=I。
所以实际上的操作序列只有四种：(AB)k(AB)^k、(BA)kB(BA)^kB、(AB)kA(AB)^kA、(BA)k(BA)^k。
另外，有 (AB)(BA)=A(BB)A=AA=I(AB)(BA)=A(BB)A=AA=I，即 BA=(AB)−1BA=(AB)^{-1}。所以 (BA)k=(AB)−k(BA)^k=(AB)^{-k}，(BA)kB=(AB)−k−1A(BA)^kB=(AB)^{-k-1}A。
所以实际上是两种：(AB)k(AB)^k 和 (AB)kA(AB)^kA。
如果这两类操作本质相同，则应该存在 A=(AB)kA=(AB)^k。
首先可以知道 A=IA=I 或 B=IB=I 是有解的。
假设 ABAB 的阶为 nn，A≠IA \neq I。
AA 的阶是 22，故唯一的可能是 k=n/2k=n/2，然后可以表出 BB：
A=(AB)n/2,B=(AB)n/2+1I=B2=(AB)n+2n∣n+2n=1,2A=(AB)^{n/2},B=(AB)^{n/2+1}\\ I=B^2=(AB)^{n+2}\\ n|n+2\\ n=1,2\\
n=1n=1，AB=I⇒A=(AB)k=IAB=I \Rightarrow A=(AB)^k=I，矛盾。
n=2n=2，A=AB⇒B=IA=AB \Rightarrow B=I
也即 A≠IA \neq I 时 B=IB=I。
所以充要条件就是 A=IA=I 或 B=IB=I。
所以现在的问题就是求出 ABAB 的阶，这个就是 ABAB 的每个环长的 lcm。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...