【博客】等价类计数问题学习笔记

零.约定：

(置换等名词会在前置知识中有解释）

在本文中，题目要求的染色方案等统称为“元素”。

两个元素严格相等我们记做“”，两个元素等价（按题目所给的置换可以互相得到）我们记做“”。

元素进行置换我们记做。

置换之间的乘积记做，，当且仅当，将代入得。

一.前置知识：

置换：

如下图所示，这是一个置换，一个置换只与两行之间的对应关系有关，与列的顺序无关。

我们的一个元素在经过这个置换后就变成了。列表示原来第位的元素置换后到了第位。

循环：

形式如下的置换叫做一个阶循环（任意一个阶循环可以记做）：

置换的分解：

指把置换分解成的形式（表示阶循环一共有个（同阶循环可以不相同）），各个循环之间的元素互不相交。感性理解一下就是，对于列，从向连一条有向边，这样会形成一个个环，一个长度为的环对应着一个。令，即循环总个数。

不动点：

如果元素，那么我们称为置换的不动点，的不动点个数用表示。

群：

群用表示，其中是一个集合，是定义在上的一个二元运算，并且满足:

封闭性()

结合律()

存在单位元()

存在逆元()

那么这是一个群。

置换群：

置换群就是将置换作为元素的群。

证明：

封闭性：置换的乘积也是置换，在这个群中。

结合律：手模小样例可知，。

单位元：

逆元：将置换的两行交换位置便是逆元。

等价类：

如果那么我们称，所有互相等价的元素组成一个等价类，元素所属的等价类记做答案便是等价类的种类。

不动置换类：

置换群中，使元素不变的置换全体，称为的不动置换类，记做。

二.引理：

内容：

等价类个数

证明：

首先看两个定理：

仿佛没什么用的定理：是的一个子群。

证明：

封闭性：使不动的两个置换的积也使不动，属于这个群。

结合律：显然。

存在单位元：显然任何元素都单位元的不动点。

存在逆元：置换属于元素的不动置换类，当且仅当的每一列，。显然的逆元也满足这个条件，也在不动置换类中。

重要定理：

证明：

如果对于都有**恰好**个不同置换使转化成，那么定理得证（因为进行一种置换有且仅有一个结果）。

首先，因为一定存在一个置换使得。因为是的不动置换类，所以

互不相同，所以互不相同，有种取值，所以有**至少**种置换，使转化成。现在我们只要能证明能够取遍所有使转化成的置换即可。

我们考虑反证法：

同上，因为一定存在一个置换使得，

假设存在一个置换，，且。

显然。

与假设相悖，所以不成立。

证毕。

设为一个等价类集合，共个等价类。

设是元素总数。

因为每个大小为，贡献，会被算次，所以每一种等价类的总贡献。等价类的种类即答案。

不动点和不动置换的关系是相互的，所有置换的不动点之和等于所有元素的不动置换之和。

证毕。

三.定理：

内容：

若题目是对个对象染种颜色，则

证明：

若是的不动点，对于每一列，都有，而一个循环是许多列首尾相接，所以他们都相等。所以对于的一个循环，，所以就相当于给每个循环染色的方案数（每个循环染相同的颜色）。所以。

证毕。

扩展：

这个式子是基于可以给每个循环任意染色这个前提的，如果染色数量有限制，我们就需要求给每个循环染色的方案数，通常用来扩展此问题。

四.应用与例题：

常见置换的循环个数：

（套路）将长度为序列（或者环）循环移位，循环个数为。

（套路）将长度为环沿对称轴反转，若是奇数则条对称轴的循环个数都是；否则，有对称轴的循环个数是，另外一半对称轴个数是。

例题：

luogu 1446

题目大意：

有张扑克牌，染三种颜色，每种颜色规定数目。再给定中洗牌方法，通过洗牌可以互相得到的方案等价，求有多少种不同方案。

题目分析：

在本题中，洗牌方法就是置换，而染色方案是“元素”。

本题给了 “输入数据保证任意多次洗牌都可用这种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态” 的条件，使满足封闭性和存在逆元。至于单位元，我们需要人为添加一种置换（自己到自己），来使之满足条件，由于单位元的性质，不会对答案产生影响，但我们必须添加使之可以使用引理。

具体做法：此处染色有数目限制，不能直接使用定理。我们首先求出每一种洗牌方案的循环个数。然后我们对于每一种洗牌方案，通过求染色方案，具体的说，表示前个循环已经染完色，三种颜色分别剩个 ，初始状态答案是。

总复杂度，可过。

luogu 4980

题目大意：自己看吧

题目分析：直接套公式，置换为种循环移位 ，直接套用套路，循环个数为的性质来优化。

我们优化一下：

我们只需要枚举到就可以了，然后再求，复杂的。您也可以大力Pollad-rho一发。

UVA11255

大水题限制染色次数+可以翻转旋转，直接套用套路、即可。

UVA10601

题目大意：一个正方体，给棱染色，有数量限制，旋转同构。

题目分析：

我们本题置换种类繁多：横向旋转（面向自己的面不变），竖向旋转（面向自己的面发生改变），以及两种旋转的组合。

但是我们发现有一些旋转的组合结果是相同的，我们考虑枚举结果，即选定面向自己的正方形的下底边为基准，枚举原来哪个位置的边转到了这个位置，共十二种置换，然后统计每个置换的循环个数（暴枚或者手模都可以），再根据数量限制扩展一下定理即可。

五.总结：

全是废话

定理实质上是引理的一个扩展，虽然式子简单，但是能够解决的问题却很有限。我们通常通过，组合数等来求不动点个数，这既可以说是定理的扩展也可以说是引理的扩展。