排列（置换群Polya定理）_成型笔记

排列（置换群 Polya定理）

在通常的理解中，置换是一个元素两两不同且长度与值域大小相同的数组，但将置换看作“可运算的元素"是更本质的理解。

• 定义 $a*b$ 这个运算得到的排列为满足 $\forall i,p_i=b_{a_i}$ 的唯一排列 $p$。

类似于将 $a$ 这个排列过了一遍 $b$ 这个”混淆器“，将原本的 $a_i$ 全部变成了 $b_{a_i}$。

类似的，我们有逆排列和元排列的定义：

• 元排列 $e$ 有且仅有一个：$1,2,\dots,n$，元排列的性质是 $\forall a,e*a=a*e=a$。
• 逆排列 $a^{-1}$ 表示满足 $aa^{-1}=a^{-1}a=e$ 的唯一排列，可以证明每个排列都有逆排列，构造方式是逆排列满足 $p^{-1}_{p_i}=i$。
• $e^{-1}=e$。

将其理解成矩阵的乘法即可，很多性质都可以套用，例如其满足结合律却通常不满足交换律。

置换和矩阵都是描述变换的，只不过置换描述的是变成了什么，而矩阵描述的是变成哪个元素的几倍。

有的时候我们只想要描述变成了什么，也可以称为一种广义的“置换”，这常用在数据结构中，来看例题：

CF911G Mass Change Queries

给定一个序列 $a$，每次区间修改把 $[l,r]$ 内等于 $x$ 的数变成 $y$，问最后的序列。

$n\le2\times10^5,x,y,a_i\le 100$。

这道题有其他更优秀的做法，但这里提供一种置换的简单做法。

考虑线段树，每个 $\text{tag}$ 大小是 $100$，维护每个数变成了什么，由于线段树 $\text{tag}$ 有一个性质是两个 $\text{tag}$ 合并的时候下面的 $\text{tag}$ 是先打上的，所以下传是朴素的。

P8969 幻梦 | Dream with Dynamic

给定序列，要求支持区间加，区间取 popcount，单点查。

$n\le 10^5$。

不难发现取完 popcount 之后的有效原值只有 $64$，所以我们找到第一次取 popcount 的时刻，那之后就只需要维护 $64$ 个值分别变成了什么。

所以我们的 tag 里面需要有 ll ad,to[64];bool b;，b 代表有没有进行过 popcount，b=0 时只有 ad 有用，代表区间加了多少，b=1 时表示区间里的数先加了 ad 然后又做了一次 popcount，最终的值是 to[ppct(x+ad)]。

Ex：需要支持区间求和？

线段树不大好搞了，考虑分块。

依然是每块维护同样的信息，没有 popcount 都好说，有的话就顺便维护一下每个数的出现次数即可。

其实以上两道题利用了区间维护的信息本质不多的原则，类似的可以用线段树求 $n=100,m=10^5$ 的区间最小生成树。

P4119 [Ynoi2018] 未来日记

给定序列，需要区间替换，区间 $\text{kth}$。

$n\le 10^5$。

毒瘤数据结构，抽空补。

置换的图论形式

在一个排列中，你可以 $\forall i\in[1,n],$ 把 $i$ 向 $a_i$ 连一条边。

每个点恰有一条入边和出边，不难发现，这是若干个环组成的图。

这张图有很良好的性质，来些例子：

NFLS 2023.11.11 B

给定两个排列 $a,b$，定义一次操作为随机选三个数轮换，问在 $m$ 步内把 $a$ 变成 $b$ 的概率。

$n\le 14,m\le 10^9$。

运用图同构的知识，我们可以知道只要两个置换的图同构，那对一个排列进行轮换，另外一个排列总能找到一种对应的轮换方式使得二者轮换出来的排列仍然同构。

这个性质极其优美，每当我们做“交换”“轮换”之类字眼的题其实都能这样减少状态数。

假设我们把状态数压缩下来了，那这题其实是可以轻松爆搜 + 矩阵快速幂通过的。

那这个状态数有多少呢？

纯环图的同构其实就是把所有环的大小找出来形成的可重集相等。

直观上来看不会太多，但隐约感觉仍然是阶乘级别？

下面我们来看看这张可爱的表，设状态数为 $d$（pdf 版里面表格地方不大够，咋调也不行/kk）：

$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$1$	$2$	$3$	$5$	$7$	$11$	$15$	$22$	$30$	$42$
$11$	$12$	$13$	$14$	$15$	$16$	$17$	$18$	$19$	$20$
$56$	$77$	$101$	$135$	$176$	$231$	$297$	$385$	$490$	$627$
$21$	$22$	$23$	$24$	$25$	$26$	$27$	$28$	$29$	$30$
$792$	$1002$	$1255$	$1575$	$1958$	$2436$	$3010$	$3718$	$4565$	$5604$
$31$	$32$	$33$	$34$	$35$	$36$	$37$	$38$	$39$	$40$
$6842$	$8349$	$10143$	$12310$	$14883$	$17977$	$21637$	$26015$	$31185$	$37338$
$41$	$42$	$43$	$44$	$45$	$46$	$47$	$48$	$49$	$50$
$44583$	$53174$	$63261$	$75175$	$89134$	$105558$	$124754$	$147273$	$173525$	$204226$

真的令人震惊。

感觉状态数远小于 $2^n$，更别提 $n!$ 了，在 $n\le 16$ 的时候甚至 $d_n\le n^2$。

而且这是所有置换的有效状态数，有的题可能不是两个数交换而是四五个数，那有可能导致更少的状态。

求出这些状态都是什么只需要爆搜即可，并且需要把一个数组映射到一个数，这里采用 $\text{Trie}$ 实现。

int GT(int a[]) {
    F(i,1,n) vis[i]=0;*c=0;
    F(i,1,n) if(!vis[i]) {
        int x=i,cnt=0;
        do vis[x=a[x]]=1,++cnt;while(x^i);
        c[++*c]=cnt;
    } sort(c+1,c+*c+1);
    int now=0;F(i,1,*c) {
        if(!nxt[now][c[i]]) nxt[now][c[i]]=++snt;
        now=nxt[now][c[i]];
    } if(!id[now]) id[now]=++nid;
    return id[now];
}
void dfs() {int id=GT(a);
    if(has[id]) return;has[id]=1;
    F(i,1,n) F(j,i+1,n) {
        swap(a[i],a[j]);
        dfs();
        swap(a[i],a[j]);
    }
}

用 $\{a\}=\{b\}$ 表示 $a$ 与 $b$ 图同构。

注意若 $\{a\}=\{b\}$，那么仅能说明 $\forall c,d,ac=bd:\{c\}=\{d\}$。

并不能说明 $\{ac\}=\{bc\}$。

这其实也有一个好处，类似于上题，若我们所求的排列有多个同构排列一起被算进去了，其实是比较难处理的。

那么我们就可以将其事先映射到 $e$，$e$ 的图是唯一的，没有人与它同构。

换句话说就是所有排列都事先乘上了 $b^{-1}$。

Polya 定理

要引入一些群论记号了。

证明不一定严谨，仅作为理解参考。

群：由一个集合和一个二元运算组成，二元运算满足封闭性和结合律，存在单位元、逆元，一般用 $G$ 表示一个群。

子群：若 $(G,\times)$ 构成一个群，$H\sube G\wedge(H,\times)$ 也构成一个群，那么 $(H,\times)$ 称为 $(G,\times)$ 的子群，记为 $(H,\times)\le(G,\times)$。

陪集：若 $g\in G$，$(H,\times)\le(G,\times)$，则 $\set{h\times g|h\in H}$ 称为 $H$ 的陪集，记作 $Hg$。

实际上该定义被称为右陪集，左陪集在本文没什么用。

陪集具有如下性质（$H\le G,g\in G$）：

• $|Hg|=|H|$，假设 $h_1g=h_2g=k$，由于逆元唯一，所以 $h_1=h_2=kg^{-1}$，也就是说不同的元素经过 $g$ 的变换仍然不同。
• $g\in Hg$，由于 $e\in H$，所以 $eg=g\in Hg$。
• $Hg=H\iff g\in H$，右推左根据封闭性以及性质 $1$ 会得到 $|H|$ 个元素来证明，左推右反证即可。
• $Ha=Hb\iff ab^{-1}\in H$，两边同时右乘 $b^{-1}$ 变为性质 $3$。
• $Ha\cap Hb\ne \varnothing\Rightarrow Ha=Hb$，即陪集之间要么不交要么相等，证明：

首先若 $g\notin H,h\in H$，则 $hg\notin H$，假设 $hg\in H$ 则 $h^{-1}hg=g\in H$，矛盾。

所以若 $g\notin H$，则 $Hg$ 与 $H$ 无交，$g\in H$ 是性质 $3$。

• 全体陪集的并为 $G$，证明考虑 $g\in Hg$，所以每个元素都至少在一个陪集中出现，事实上在且仅在一个陪集中出现，因为性质 $5$。

若 $H\le G$，记 $G/H$ 为 $G$ 中 $H$ 的右陪集构成的集合 $\set{Hg|g\in G}$。

洛谷第一篇题解中该记号指左陪集，本文为了叙述的统一性定义其为右陪集。

若 $H\le G$，记 $[G:H]$ 为 $|G/H|$。

（怎么感觉后者还简洁了些，不过前者是公认的记号。）

$\rm Lagrange$ 定理：$|H|[G:H]=|G|$，证明方法就是所有陪集大小相同且无交且并起来为 $G$。

群作用：对于群 $G$ 和集合 $M$，定义群作用为满足如下条件的二元函数 $\varphi(m,g)$，以下记 $m*_{\varphi}g$ 为 $\varphi(m,g)$：

• $g\in G,m\in M$。
• $m*_{\varphi}e=m$。
• $m*_{\varphi}a*_{\varphi}b=m*_\varphi(a\times b)$。

称 $G$ 作用于集合 $M$，值得注意的是这里的集合 $M$ 要求所有 $m*_\varphi g\in M$，即 $*_{\varphi}$ 一个 $G$ 中的元素这个操作对 $M$ 是封闭的。

轨道：若 $G$ 作用于集合 $X$，则 $x\in X$ 的轨道 $G(x)$ 定义为 $x$ 通过 $G$ 能转移到的元素集合，即 $\set{x*_\varphi g|g\in G}$，可以理解为 $G$ 对 $x$ 有 $G(x)$ 这么多作用效果。

无需在意是一步转移还是两步转移，因为根据群的性质后者可以压缩成前者。

稳定子：$x$ 的稳定子 $G^x=\set{g|x*_{\varphi}g=x}$，即（作用于 $x$ 不改变 $x$）的 $G$ 元素的个数。

轨道 - 稳定子定理：$|G(x)||G^x|=|G|$。

证明：

首先可以证明 $G^x\le G$，只需验证封闭性、逆元、单位元即可。

接下来只需证 $|G(x)|=[G:G^x]$。

若 $x*_\varphi f=x*_\varphi g$，则 $x*_\varphi(f\times g^{-1})=x$，所以 $f\times g^{-1}\in G^x$，根据陪集性质我们得到 $G^xf=G^xg$。

这告诉我们作用效果相同意味着在同一陪集中，上述过程也可以逆过来告诉我们这是充要的，由于 $G^x$ 的陪集数量为 $\frac{|G|}{|G^x|}$，可得总共有这么多种作用效果，作用效果数也就是 $|G(x)|$。

等价类：若 $G$ 作用于 $X$，$x,y\in X,\exist f\in G$ 满足 $x*_\varphi f=y$，那么定义 $x,y$ 属于同一个等价类，不难看出 $G(x)$ 是一个无法扩展的等价类（极大等价类），所以等价类的概念其实就是轨道。

不动点：$X^g=\set{x|x*_\varphi g=x}$，注意与稳定子区分开，不动点是 $x$ 的数量。

$\rm Burnside$ 引理：记 $X$ 在 $G$ 作用下不同的等价类集合为 $X/G=\set{x*_\varphi g|x\in X,g\in G}$，则：

$$|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|$$

用文字描述就是每个元素 $g$ 作用于 $X$ 的不动点个数的算术平均值。

证明：

$$\begin{aligned}|X/G|&=\sum_{x\in X}\frac{1}{G(x)}\\&=\sum_{x\in X}\frac{1}{\frac{|G|}{|G^x|}}\\&=\sum_{x\in X}\frac{|G^x|}{|G|}\\&=\frac{1}{|G|}\sum_{x\in X}|G^x|\\&=\frac1{|G|}\sum_{g\in G}|X^g|\end{aligned}$$

后面几步应该都能看懂，第一步是考虑每个等价类会被统计 $G(x)$ 次。

那这个东西有什么用呢，其最大的用处就是把对 $x$ 的枚举变为对 $g$ 的枚举。

我们进一步可以得到 $\rm Pólya$ 定理：$m$ 个元素对 $n$ 个对象染色，额外给定置换群 $G$，若 $g\in G,x=y*_\varphi g$ 则 $x,y$ 两种方案认为是相同的，则不同的染色方案为：

$$\frac{1}{|G|}\sum_{p\in G}m^{C(p)}$$

其中 $C(p)$ 表示 $p$ 这个置换的构成中有多少个环。

理解起来很方便，每个环的颜色必须相同嘛。

P4980 【模板】Polya 定理

$T$ 组数据，每次给定一个 $n$，求大小为 $n$ 的环，$n$ 种颜色，给每个点染色，问有多少种不同的染色方案，不同定义为不存在一种旋转方式使得两个环完全相同。

$T\le10^3,n\le 10^9$。

可以将集合 $X$ 的视为所有的 $n^n$ 个对序列的染色方案，将 $G$ 视为旋转。

显然 $|G|=n$，你可以有 $n$ 种旋转方案。

我们枚举这 $n$ 种旋转方案，考虑旋转 $i$ 个单位会产生多少个不动点原序列。

考虑每个元素 $j$ 向 $(j+i)\bmod n$ 连一条边，这会产生 $\gcd(i,n)$ 个子环，每个子环的颜色必须相同，环与环之间无所谓，于是：

$$\begin{aligned}{\rm ans}&=\frac 1 n\sum_{i=1}^nn^{\gcd(i,n)}\\&=\frac 1 n\sum_{k\mid n}n^k\sum_{d=1}^{n/k}[(d,n/k)=1]\\&=\frac 1 n\sum_{k\mid n}n^k\varphi(n/k)\end{aligned}$$

式子化的熟练了我们其实可以知道 $\sum_{i=1}^nf(\gcd(n,i))=\sum_{i|n}f(i)\varphi(n/i)$。

暴力根号求 $\varphi$ 即可，但精细实现的话可以做到 $\cal O(d(n)+p(n))$ 完成该过程，其中 $d$ 为约数个数，$p$ 为质因数分解复杂度，方法是搜因数的质因数分解的同时求出 $\varphi$。

P3307 [SDOI2013] 项链

$T$ 组数据，每次给定 $n,a$，定义环上每个元素为 $(x,y,z)(x,y,z\in[1,a],\gcd(x,y,z)=1)$ 这样的 无序三元组，要求对 $n$ 个元素的环计数，要求相邻两个元素不能相同。

$T\le10,n\le10^{14},a\le 10^7$。

首先我们先求出每个元素有多少种取值方案，可以讨论用了几种颜色，设其为 $d$：

首先是后面会用到的一些函数：

$$\begin{aligned}&{\rm S}_1(x)=\frac{x(x+1)}{2}\\&{\rm S}_2(x)=\frac{x(x+1)(2x+1)}6\end{aligned}$$

一种颜色：$1$。

两种颜色（式子中的 $n$ 是 $a$）：

$$\begin{aligned}&2\sum_{i=1}^n\sum_{j=1}^{i-1}[(i,j)=1]\\=\ &2\sum_{d=1}^n\mu(d)\sum_{i=1}^{n/d}\sum_{j=1}^{i-1}1\\=\ &2\sum_{d=1}^n\mu(d){\rm S}f(n/d-1),f(x)=x\\&{\rm S}f(x)={\rm S}_1(x)\end{aligned}$$

三种颜色（式子中的 $n$ 是 $a$）：

$$\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^{i-1}\sum_{k=1}^{j-1}[(i,j,k)=1]\\=\ &\sum_{d=1}^n\mu(d)\sum_{i=1}^{n/d}\sum_{j=1}^{i-1}\sum_{j=1}^{j-1}1\\=\ &\sum_{d=1}^n\mu(d)\sum_{i=1}^{n/d}{\rm S}_1(i-2)\\=\ &\sum_{d=1}^n\mu(d)\sum_{i=1}^{n/d}\frac{(i-2)(i-1)}{2}\\=\ &\sum_{d=1}^n\mu(d)f(n/d),f(x)=\frac{{\rm S}_2(x)-3{\rm S}_1(x)+2x}2\end{aligned}$$

---

接下来我们要解决这样一个问题：每个元素有 $d$ 种情况，相邻元素必须不同，对环计数。

首先还是连边变成 $\gcd(i,n)$ 个环，每个环的颜色必须相等，然后就转化成对满足长度为 $\gcd(i,n)$ 且相邻元素（包括首和尾）不同的 序列 计数。

对这种序列计数我们设 $f_i$ 是长为 $i$ 的序列，每次可以把第一个元素抠掉，若两边颜色相同就把三个缩成一个，被缩掉的中间元素有 $d-1$ 种选择，否则就仅仅把中间的给缩掉，并有 $d-2$ 种选择。

$$f_1=d,f_2=d(d-1),f_i=(d-1)f_{i-2}+(d-2)f_{i-1}$$

约数估算一下 $n$ 大概有 $n^{1/3}$ 个约数，所以 $f$ 使用矩阵快速幂解决足够。

需要注意一个小细节，$\gcd(i,n)\ne 1$，否则每个点就会被要求跟相邻元素的颜色相同。

$${\rm ans}\gets \frac 1 n\sum_{i=1}^n[\gcd(i,n)\ne 1]f(\gcd(i,n))=\frac 1 n\sum_{i|n,i\ne 1}f(i)\varphi(n/i)$$

带权 Burnside/生成函数形式

有空了补，目前没见到应用。