洁骜攻子

2019-04-09 20:36 莱州市第一中学 C++

关注

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

零.约定：

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

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

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

$3.$ 元素 $a$ 进行置换 $g$ 我们记做 $a\otimes g$ 。

$4.$ 置换之间的乘积记做 $\odot$ ， $g_i=g_j\odot g_k$ ，当且仅当 $\forall a,a\otimes g_i=a\otimes g_j\otimes g_k$ ，将 $g_j\odot g_k$ 代入 $g_i$ 得 $a\otimes(g_j\odot g_k)=a\otimes g_j\otimes g_k$ 。

一.前置知识：

$1.$ 置换：

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

$\left(\begin{matrix}1&2&3&4\\2&3&1&4\end{matrix}\right)=\left(\begin{matrix}1&4&3&2\\2&4&1&3\end{matrix}\right)$

我们的一个元素 $\left(\begin{matrix}3&2&4&1\end{matrix}\right)$ 在经过这个置换后就变成了 $\left(\begin{matrix}4&3&2&1\end{matrix}\right)$ 。列 ${^a_b}$ 表示原来第 $a$ 位的元素置换后到了第 $b$ 位。

$2.$ 循环：

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

$\left(\begin{matrix}a_1&a_2&a_3&\cdots&a_n\\a_2&a_3&a_4&\cdots&a_1\end{matrix}\right)$

$3.$ 置换的分解：

指把置换 $g$ 分解成 $r_1^{k_{1}}r_2^{k_{2}}\cdots r_n^{k_{n}}$ 的形式（ $r_j^{k_{j}}$ 表示阶循环一共有 $k_{j}$ 个（同阶循环可以不相同）），各个循环之间的元素互不相交。感性理解一下就是，对于列 $^a_b$ ，从 $a$ 向 $b$ 连一条有向边，这样会形成一个个环，一个长度为 $i$ 的环对应着一个 $r_i$ 。令 $w(g)=\sum_{i=1}^n k_i$ ，即循环总个数。

$4.$ 不动点：

如果元素 $a\otimes g_i = a$ ，那么我们称 $a$ 为置换 $g_i$ 的不动点， $g_i$ 的不动点个数用 $\chi(g_i)$ 表示。

$5.$ 群：

群用 $(G,\oplus)$ 表示，其中 $G$ 是一个集合， $\oplus$ 是定义在 $G$ 上的一个二元运算，并且满足:

封闭性( $\forall a,b \in G,a\oplus b \in G$ )

结合律( $a\oplus(b\oplus c)=(a\oplus b)\oplus c$ )

存在单位元( $\exists e,\forall a,e\oplus a = a\oplus e = a$ )

存在逆元( $\forall a,\exists a^{-1},a\oplus a^{-1} = a^{-1}\oplus a = e$ )

那么这是一个群。

$6.$ 置换群：

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

证明：

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

结合律：手模小样例可知， $a\odot b\odot c=a\odot(b\odot c)$ 。

单位元：

$\left(\begin{matrix}1&2&3&\cdots&n\\1&2&3&\cdots&n\end{matrix}\right)$

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

$7.$ 等价类：

如果 $\exists g,s.t.~a\otimes g = b$ 那么我们称 $a\Leftrightarrow b$ ，所有互相等价的元素组成一个等价类，元素 $a$ 所属的等价类记做 $E_a$ 答案 $L$ 便是等价类的种类。

$8.$ 不动置换类：

置换群 $G$ 中，使元素 $a$ 不变的置换全体，称为 $a$ 的不动置换类，记做 $Z_a(\forall g \in Z_a,a\otimes g=a\&\&\forall g\notin Z_a,a\otimes g\ne a)$ 。

二. $Burnside$ 引理：

内容：

等价类个数

$L = \frac {\sum_{g\in G} \chi(g_j)}{|G|}$

证明：

$step~1:$ 首先看两个定理：

$1.$

~~仿佛没什么用的~~定理： $|Z_k|$ 是 $G$ 的一个子群。

证明：

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

结合律：显然。

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

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

$2.$

重要定理： $\forall a,|E_a||Z_a|=|G|$

证明：

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

首先，因为 $b\in E_a$ 一定存在一个置换 $p$ 使得 $a\otimes p = b$ 。因为 $Z_a$ 是 $a$ 的不动置换类，所以

$\forall z\in Z_a$

$\because a\otimes z=a,a\otimes p = b$

$\therefore a\otimes z\otimes p = b$

$\therefore a\otimes(z\odot p)=b$

$z$ 互不相同，所以 $z\odot p$ 互不相同， $z$ 有 $|Z_a|$ 种取值，所以有**至少** $|Z_a|$ 种置换，使 $a$ 转化成 $b$ 。现在我们只要能证明 $z\odot p$ 能够取遍所有使 $a$ 转化成 $b$ 的置换即可。

我们考虑反证法：

同上，因为 $b\in E_a$ 一定存在一个置换 $p$ 使得 $a\otimes p = b$ ，

假设存在一个置换 $q$ ， $a\otimes q = b$ ，且 $\forall z\in Z_a,z\odot p\neq q$ 。

显然 $\exists c=q\odot p^{-1}\in G,s.t.~c\odot p = q$ 。

$\because a\otimes q =b,c\odot p = q$

$\therefore a\otimes(c\odot p)=b$

$\therefore a\otimes c\otimes p=b$

$\because a\otimes p =a$

$\therefore a\otimes c = a$

$\therefore c\in Z_a,$ 与假设 $\forall z\in Z_a,z\odot p\neq q$ 相悖，所以不成立。

证毕。

$step~2:$

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

设 $n$ 是元素总数。

$\because \forall a,|E_a||Z_a|=|G|$

$\therefore |Z_a|=\frac{|G|}{|E_a|}$

$\therefore \sum_{i=1}^n|Z_i|=|G|\sum_{i=1}^n\frac{1}{|E_i|}$

因为每个 $E_i$ 大小为 $|E_i|$ ，贡献 $\frac{1}{|E_i|}$ ，会被算 $|E_i|$ 次，所以每一种等价类的总贡献 $1$ 。 $\sum_{i=1}^{n}\frac{1}{|E_i|}=$ 等价类的种类即答案 $L$ 。

$\therefore \sum_{i=1}^n|Z_i|=|G|L$

$\therefore L=\frac{\sum_{i=1}^n|Z_i|}{|G|}$

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

$\therefore L=\frac{\sum_{g\in G}\chi(g)}{|G|}$

证毕。

三. $Polya$ 定理：

内容：

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

$\chi(g)=m^{w(g)}$ $L=\frac{\sum_{g\in G}m^{w(g)}}{|G|}$

证明：

若 $a$ 是 $g$ 的不动点，对于每一列 $^x_y$ ，都有 $a_x=a_y$ ，而一个循环是许多列首尾相接，所以他们都相等。所以对于 $g$ 的一个循环 $r$ ， $\forall i,j\in r,a_i =a_j$ ，所以 $\chi(g)$ 就相当于给 $g$ 每个循环染色的方案数（每个循环染相同的颜色）。所以 $\chi(g)=m^{w(g)}$ 。

证毕。

扩展：

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

四.应用与例题：

常见置换的循环个数：

$1.$ （套路 $1$ ）将长度为 $n$ 序列（或者环）循环移 $k$ 位，循环个数为 $\gcd(n,k)$ 。

$2.$ （套路 $2$ ）将长度为 $n$ 环沿对称轴反转，若 $n$ 是奇数则 $n$ 条对称轴的循环个数都是 $\lceil\frac n 2\rceil$ ；否则，有 $\frac n 2$ 对称轴的循环个数是 $\frac n 2$ ，另外一半对称轴个数是 $\frac n {2}+1$ 。

例题：

$1.$ luogu 1446

$a.$ 题目大意：

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

$b.$ 题目分析：

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

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

$c.$ 具体做法：此处染色有数目限制，不能直接使用 $Polya$ 定理。我们首先 $\Theta(n)$ 求出每一种洗牌方案的循环个数。然后我们对于每一种洗牌方案，通过 $dp$ 求染色方案，具体的说， $f[i][a][b][c]$ 表示前 $i$ 个循环已经染完色，三种颜色分别剩 $a,b,c$ 个，初始状态 $f[0][Sum_a][Sum_b][Sum_c]$ 答案是 $f[w][0][0][0]$ 。

总复杂度 $\Theta(nmSum_aSum_bSum_c)$ ，可过。

$2.$ luogu 4980

$a.$ 题目大意：~~自己看吧~~

$b.$ 题目分析：直接套公式，置换为 $n$ 种循环移位，直接套用套路 $1$ ，循环个数为 $\gcd(n,k)$ 的性质来优化。

$ans = \frac 1 {|G|}{\sum_{i = 0} ^ {n-1}m^{\gcd(n,i)}}$

我们优化一下：

$\sum_{i=0}^{n-1}m^{\gcd(n,i)}=\sum_{t|n}\sum_{i=1}^{\frac n t}I[\gcd(it,n)==t]\times m^t=\sum_{t|n}\sum_{i=1}^{\frac n t}I[\gcd(i,\frac n t)==1]\times m^t=\sum_{t|n}\varphi(\frac n t)m^t$

我们只需要枚举 $t$ 到 $\sqrt{n}$ 就可以了，然后再 $\sqrt{n}$ 求 $\varphi$ ，复杂的 $\Theta(Tn^{\frac 3 4})$ 。~~您也可以大力Pollad-rho一发~~。