群,一种特殊的代数结构,满足封闭性,结合律,存在幺元和对于每个元素存在逆元的四种性质.
一种描述交换操作(置换)的记号.
可以考虑成: 一张包含 \(n\) 个点的图,然后使 点\(i\) 与 点\(a_i\) 有边相连.对于每个连通块来说,图的形态一定是一个环,从环上一个点开始按照任意方向遍历图,得到的遍历顺序就是上面描述中的一个括号内的内容.联通块的个数就是上面描述中的括号数量,其实这个可以被称为轨道数.
一道例题 众所周知,小葱同学擅长计算,尤其擅长计算组合数,但这个题和组合数没什么关系.
现在为了打破迷宫的结界,你需要在迷宫的某些边上开一扇门.你总共需要开 \(r\) 扇门,每条边最多打开一扇门.但是如果两种开门的方案通过旋转相同,那么视为同一种方案.以及由于是死亡迷宫,所以死了也是可以的,所以你并不需要保证你开门的方案能够让你走出去.求总共的方案数.
循环节:即对于一种置换方案的轨道长度.简单理解为转多少次能够转到原来的位置.
以某个对象为旋转轴,其置换群中必然有两个长度为 \(1\) 的轨道,作为旋转轴的对象,旋转前后应该是重叠的. 然后剩下的根据轨道循环节直接算出即可. 可以发现这是一个无脑的工作