群论小记
command_block
2019-03-18 13:26:12
# 1.群的概念与基本性质
$\color{blue}\text{定义}:$ 给定一个集合 $G$ ,和其上的二元运算 $*$ , 满足如下性质:
- 封闭性 : 若 $a,b\in G$ ,则必有 $(a*b)\in G$。
- 结合律 : 对于任意的 $a,b,c\in G$ ,有 $(a*b)*c=a*(b*c)$
- 存在单位元 : 存在一个 $e\in G$ ,使得对于任意的 $a\in G$ ,满足 $a*e=e*a=a$。
元素 $e$ 则被称作单位元。
- 存在逆元 : 对于任意的 $a\in G$ ,存在一个 $b\in G$ ,满足 $a*b=b*a=e$。
元素 $b$ 可以记作 $a^{-1}$。
则称 $G$ 在 $*$ 运算下是一个**群**。
有时把 $*$ 省略不写。
- $\color{blue}\text{定理 1.1}:$ 群的单位元唯一。
设有两个不同的单位元 $e_1,e_2$ ,根据单位元的定义能得到 $e_1=e_1e_2=e_2$ ,矛盾。
- $\color{blue}\text{定理 1.2}:$ $ab=ac\Rightarrow b=c,\ ba=ca\Rightarrow b=c$
证左部,右部同理。
$ab=ac\ \Rightarrow\ a^{-1}(ab)=a^{-1}(ac)\ \Rightarrow\ (a^{-1}a)b=(a^{-1}a)c\ \Rightarrow\ b=c$
- $\color{blue}\text{定理 1.3}:$ 每个元素的逆唯一。
若 $a$ 有两个不同的逆 $b,c$。
则有 $ab=e=ac$ ,使用$\color{blue}\text{定理1.2}$ 约去 $a$ 得到 $b=c$。
若只希望了解置换计数，可以到此为止。
------------
- $\color{blue}\text{定理 1.4}:$ 对于任意的(有限)群 $G=\{e,a_1,a_2...a_n\}$
对于任意的 $a\in G$ 都存在一个常数 ${\rm ord}(a)$ ,使得 $a^{{\rm ord}(a)}=e$。此时称 ${\rm ord}(a)$ 为 $a$ 的阶。
且有 $a^{-1}=a^{{\rm ord}(a)-1}$。
任取 $a\in G$ ,构造 $\{a,a^2,a^3...a^n,a^{n+1}\}$。
由于封闭性,这 $n+1$ 个元素都属于 $G$ ,但 $|G|=n$ ,所以必有两者相等。
不妨设 $a^x=a^y,x<y$。约掉 $a^x$ 则有 $a^{y-x}=e$。
令 ${\rm ord}(a)=y-x$ ,则有 $a^{r(a)-1}a=a^{r(a)}=e$。 能得到 $a^{r(a)-1}=a^{-1}$
# 2. 置换与置换群
- **置换的定义**
假设有 $1,2,3...n$ 这 $n$ 个元素, 令 $k$ 被元素 $a_k$ 所取代。
满足各个 $a_k$ 互不相同,也就是“移动”后, $n$ 个元素仍然都存在。
写作置换 : $\begin{pmatrix}1&2&3&...&n\\a_1&a_2&a_3&...&a_n\end{pmatrix}$
如 $p=\begin{pmatrix}1&2&3&4\\3&1&4&2\end{pmatrix}$
这个置换就代表着:
- 把 $1$ 移到第 $3$ 个
- 把 $2$ 移到第 $1$ 个
- 把 $3$ 移到第 $4$ 个
- 把 $4$ 移到第 $2$ 个
又作:
$1\xrightarrow{p}3,\quad 2\xrightarrow{p}1,\quad 3\xrightarrow{p}4,\quad 4\xrightarrow{p}2$
- **置换乘法**
置换的乘法就是把映射叠加。
设 $p_2=\begin{pmatrix}1&2&3&4\\2&1&4&3\end{pmatrix}$
则 $1\xrightarrow{p}3\xrightarrow{p_2}4,\quad 2\xrightarrow{p}1\xrightarrow{p_2}2,\quad 3\xrightarrow{p}4\xrightarrow{p_2}3,\quad 4\xrightarrow{p}2\xrightarrow{p_2}1$
所以有 $p*p_2=\begin{pmatrix}1&2&3&4\\4&2&3&1\end{pmatrix}$
也可以这样写 :
$\small\begin{pmatrix}1&2&3&4\\3&1&4&2\\\end{pmatrix}*\begin{pmatrix}1&2&3&4\\2&1&4&3\end{pmatrix}=\begin{pmatrix}1&2&3&4\\3&1&4&2\end{pmatrix}*\begin{pmatrix}3&1&4&2\\4&2&3&1\end{pmatrix}=\begin{pmatrix}1&2&3&4\\4&2&3&1\end{pmatrix}$
容易证明如下的几条基本性质 :
- 置换的乘积还是置换。
- 置换乘法满足结合律。
- 单位元为 $\begin{pmatrix}1&2&3&...&n\\1&2&3&...&n\\\end{pmatrix}$
- $\begin{pmatrix}1&2&...&n\\a_1&a_2&...&a_n\end{pmatrix}$ 的逆为 $\begin{pmatrix}a_1&a_2&...&a_n\\1&2&...&n\end{pmatrix}$
但注意,置换乘法一般**不满足**交换律。
- **置换群**
根据上面的若干性质,不难证明对 $1...n$ 作用的**所有置换**形成一个群。
总是研究全体置换,未免乏味,我们一般只研究一个子群。
有如下事实 : 对于任意一个 $n$ 阶有限群,存在一个 $n$ 阶置换群与其同构。
解释一下同构是什么意思,想想一个二分图,左侧的点用对子 $(a,b)$ 描述,向右侧的 $a*b$ 连边。
若这两个图同构,则称两个群同构。(其实就是把所有的运算结果打了个表)
现在我们就是要证明置换群能够造出任意的图来。
对于 $G=\{a_1,a_2...a_n\}$ ,取 $a_k$ ,写出 $a_ka_1,a_ka_2...a_ka_n$。
这些乘积必然两两不同。假设有 $a_ka_i=a_ka_j$ ,约去 $a_k$ 可得 $a_i=a_j$ ,矛盾。
我们设 $p_k=\begin{pmatrix}a_1&a_2&...&a_n\\a_1a_k&a_2a_k&...&a_na_k\end{pmatrix}$ (其实就是把所有关于 $a_k$ 的运算写出来)
令 $a_k$ 和 $p_k$ 相对应,写作 $a_k\leftrightarrow p_k$。
则有 $a_ia_j\leftrightarrow p_ip_j$ ,证明如下 :
$p_ip_j=\begin{pmatrix}a_1&a_2&...&a_n\\a_1a_i&a_2a_i&...&a_na_i\end{pmatrix}\begin{pmatrix}a_1&a_2&...&a_n\\a_1a_j&a_2a_j&...&a_na_j\end{pmatrix}$
$=\begin{pmatrix}a_1&a_2&...&a_n\\a_1a_i&a_2a_i&...&a_na_i\end{pmatrix}\begin{pmatrix}a_1a_i&a_2a_i&...&a_na_i\\(a_1a_i)a_j&(a_2a_i)a_j&...&(a_na_i)a_j\end{pmatrix}$
$=\begin{pmatrix}a_1&a_2&...&a_n\\a_1(a_ia_j)&a_2(a_ia_j)&...&a_n(a_ia_j)\end{pmatrix}$
注意到,前面的“二分图”有 $n^2$ 个 $ 1...n$ 的信息,而 $n$ 阶置换群也有 $n^2$ 个信息,所以本质上其实是暴力打表。
- **置换的循环**
把置换看做一张有向图, 连边 $i\rightarrow a_i$ 。不难发现,每个点只有一个出度一个入度,所以会形成若干个环。
$\begin{pmatrix}1&2&3&4\\3&1&4&2\\\end{pmatrix}$
的循环是 $(1,2,3,4)$
$\begin{pmatrix}1&2&3&4\\2&1&4&3\\\end{pmatrix}$
的循环是 $(1,2)(3,4)$
$\begin{pmatrix}1&2&3&4\\2&1&3&4\\\end{pmatrix}$
的循环是 $(1,2)(3)(4)$ ,通常省略一元循环写作 $(1,2)$。
置换可以用这些环来表示,而且表示方法是唯一的。
由于比双层写法更简洁,下面有时会以循环的方式写出置换。
# 2. Burnside / Polya
设 $G$ 是 $1...n$ 的一个置换群。
- **不动点**
对于 $p\in G$,若 $k\xrightarrow{p}k$ ,则称 $k$ 是 $p$ 下的不动点。
将 $p$ 下的不动点个数即为 $c(p)$。
- $\bf k$ **不动置换类**
对于 $p\in G$ ,若 $k$ 是 $p$ 的不动点,则称 $p$ 属于 $k$ 不动置换类。
记作 $p\in Z_k$。能够发现, $Z_k$ 是 $G$ 的一个子群。
- **等价类**
等价类 $E_k$ 设为 对元素 $k$ 施加任意的 $G$ 中置换,能够获得的元素集合。 (又称为轨迹)
如 $G=\{e,(1,2),(3,4),(1,2)(3,4)\}$。
那么 $1$ 在置换的作用下可以到达 $1,2$ ,但不可能到达 $3,4$ ,则有 $E_1=\{1,2\}$。
$\color{blue}\text{定理 2.1}:$ 当 $x,y$ 属于一个等价类时,有 $|Z_x|=|Z_y|$
$\color{blue}\text{证明}:$ 构造 $Z_x,Z_y$ 之间的双射。
根据等价类的定义,存在置换 $t\in G$ 使得 $\ x\xrightarrow{t} y,\quad y\xrightarrow{t^{-1}} x$。
对于任意的 $p\in Z_x$ ,有 $y\xrightarrow{t^{-1}} x\xrightarrow{p} x\xrightarrow{t}y$ ,构造 $p'=t^{-1}pt$ ,则必有 $p'\in Z_y$。
这就是一组从 $Z_x$ 到 $Z_y$ 的映射,同理也有 $Z_y$ 到 $Z_x$ 的映射。
构建了双射之后,元素个数显然是相同的。
- **轨道-稳定化子定理**
$\color{blue}\text{定理 2.2}:$ $|Z_k|\times|E_k|=|G|$
$\color{blue}\text{证明}:$ 设 $m=|E_k|$ ,设 $E_k=\{a_1(=k),a_2...a_m\}$
根据等价类的定义,对于每个 $a_i$ 都存在 $p_i\in G$ 使得 $k\xrightarrow{p_i} a_i$。
设置换集合 $G_i=Z_kp_i$ ,显然有 $G_i\subseteq G$。
由于 $k\xrightarrow{p\in Z_k}k\xrightarrow{p_
i}a_i$ ,则有 $k\xrightarrow{p\in Z_kp_i}a_i$
能够发现 $i≠j$ 时 ,$G_i∩G_j=\varnothing$。(这是显然的,因为两个群对 $k$ 的作用不同)
那么有 $G_1+G_2+...G_m\subseteq G$。
另一方面,对于任意的 $p\in G$ ,由等价类的定义,必有 $a_i$ 使得 $k\xrightarrow{p}a_i$。
那么有 $k\xrightarrow{p}a_i\xrightarrow{p_i^{-1}}k \Longrightarrow p*p_i^{-1}\in Z_k \Longrightarrow p\in Z_kp_i$
所以, $G$ 中的每个置换都被包含在某个 $G_i$ 中,则有 $G\subseteq G_1+G_2+...+G_m$。
综上可得 $G=G_1+G_2+...+G_m=Z_kp_1+Z_kp_2+...+Z_kp_m$
$|G|=|Z_kp_1|+|Z_kp_2|+...+|Z_kp_m|=m|Z_k|=|E_k||Z_k|$ ,证毕。
- **Burnside引理**
$\color{blue}\text{定理 2.3}:$ 称 $E_{1...n}$ 中本质不同的个数,为等价类个数,设为 $l$ ,则有
$$l=\dfrac{1}{|G|}\sum\limits_{p\in G}c(p)$$
人话 : 等价类个数=各个置换下不动点个数的和的平均数。
$\color{blue}\text{证明}:$ 设 $m=|G|,G=\{a_1,a_2...a_m\}$。
记 $s_{i,k}=[k\xrightarrow{a_i}k]$。
能够发现, $\sum\limits_{k=1}^ns_{i,k}=c(a_i)$ (对置换 $a_i$ ,枚举各个元素,查看是否不动)
同时也有 $\sum\limits_{i=1}^ms_{i,k}=|Z_k|$ (对元素 $k$ ,枚举各个置换,查看是否不动)
则所有 $s$ 的和 $=\sum\limits_{i=1}^m\sum\limits_{k=1}^ns_{i,k}=\sum\limits_{i=1}^mc(a_i)=\sum\limits_{k=1}^n|Z_k|$。
**不妨**设 $l$ 个**互不相同**的等价类为 $E_1,E_2...E_l$ ,则有 $N=E_1,E_2...E_l$。
那么,由于 $R$ 是 $N$ 的一个划分,我们可以把 $\sum\limits_{i=1}^n$ 换成 $\sum\limits_{t=1}^l\sum\limits_{i\in E_t}$
则有 $\sum\limits_{k=1}^n|Z_k|=\sum\limits_{t=1}^l\sum\limits_{i\in E_t}|Z_i|$
回忆 $\color{blue}\text{定理 2.1}$ ,由于 $i,t$ 同属于一个等价类,可以把 $|Z_i|$ 换成 $|Z_t|$。
$\sum\limits_{t=1}^l\sum\limits_{i\in E_t}|Z_t|=\sum\limits_{t=1}^l|E_t||Z_t|$
又因为 $|E_t||Z_t|=|G|$ ,所以有上式 $=l\times|G|$
于是就有 $\dfrac{1}{|G|}\sum\limits_{i=1}^mc(a_i)=l$ ,证毕。
- **Polya定理**
以问题引入 : 给出一条长度为 $6$ 的链条,每一节可以染上 $4$ 种不同的颜色,但是翻转之后相同的方案被视为本质相同,问不同的染色方案数。
若将每种染色方案视为一个元素,令 $N$ 为这些元素的集合,那么 $N$ 在“翻转置换”作用下的等价类个数即为答案。
问题在于,置换的大小是 $|N|=6^4$ ,非常庞大,不便于计算。
能够发现,“翻转”同样是对 $1...6$ 这些“位置”的置换,且也是群。
若能把对“位置”的小置换群,和对“状态”的大置换群联系起来,就能更方便地计算了。
- $\color{blue}\text{定理 2.4}:$ 设有 $n$ 个元素,每个元素有 $m$ 种染色方法。
设 $G$ 是 $n$ 个元素的置换群,则染色总方案数为 :
$$\dfrac{1}{|G|}\sum\limits_{p\in G}T(p)$$
其中 $T(p)$ 指在置换 $p$ 下,不动的染色方案数。
- 比如 $\begin{pmatrix}1&2&3&4\\2&1&4&3\\\end{pmatrix}$。
那么染成 $\{a,a,b,b\}$ ,置换完了之后还是 $\{a,a,b,b\}$ ,则称之为不动的染色方案
染成 $\{a,b,c,d\}$ 置换完了之后是 $\{b,a,d,c\}$ ,和原来不相等,则不是“不动方案”。
- $\color{blue}\text{证明}:$
设 $G'$ 是对状态的置换群。不难发现大置换和小置换有对应关系,使用小置换对每种状态讨论即可得到大置换。
形式化的讲,设 $p\in G$ 对应 $p'\in G'$。
若一种染色方案 $a$ 在经过 $p$ 的“移动”之后,变为了 $b$ ,则 $a\xrightarrow{p'}b$。
所以有 $|G|=|G'|$。
根据经典的Burnside引理,可以得到答案为 $\dfrac{1}{|G'|}\sum\limits_{p'\in G'}c(p')$
而 $c(p')$ 的意义正是 $G$ 中**相对应**的置换 $p$ 下不动的染色方案数,证毕。
- 接下来介绍如何求 $T(p)$。
设 $d(p)$ 为 $p$ 的循环个数,则(根据等式的传递性)每个循环中必须染上同一种颜色,且不同循环之间没有影响。
能得到 $T(p)=m^{d(p)}$。
回到题目, $G$ 中有两个置换 : $e,\begin{pmatrix}1&2&3&4&5&6\\6&5&4&3&2&1\end{pmatrix}$。
后者有循环节 $(1,2)(3,4)(5,6)$ ,则贡献为 $4^3$
前者有循环节 $(1)(2)(3)(4)(5)(6)$ ,则贡献为 $4^6$
总方案数是 $\dfrac{1}{2}(4^6+4^3)$。
# 3. 习题
- [P4980 【模板】Polya定理](https://www.luogu.com.cn/problem/P4980)
这道题里的置换就是旋转。
有旋转 $0...n-1$ 格的置换,共 $n$ 个。
设 $p_i=\begin{pmatrix}1&2&...&n-i&n-i+1&...&n\\1+i&2+i&...&n&1&...&i\\\end{pmatrix}$ (旋转 $i$ 格)
Polya式子 : $\dfrac{1}{n}\sum\limits_{i=0}^{n-1}n^{d(p_i)}$
暴力 : 根据上文介绍的方法，对每个置换缩点求循环个数 $d(p)$ ,复杂度 $O(n^2)$。
打表或者拿出草稿纸画了一通后,你会发现 $d(p_i)=\gcd(n,i)$。
- $\color{blue}\text{证明}:$ 首先注意到 $d(p_i)=\gcd(n,i)\Longleftrightarrow$ 循环节大小为 $\dfrac{n}{\gcd(n,i)}$。
若每次跳 $i$ 步,在长度为 $n$ 的环上,多少次才能回到原点呢?
当 $i\perp n$ 时,可以证明 $0,i,2i,3i...(n-1)i$ 在$\pmod n$ 意义下互不相同。
此时的答案就是 $n$。
若 $i\not\perp n$ ,采用模分类,设 $d=\gcd(i,n)$ ,若从 $0$ 开始,不难发现 $d\!\!\not|\ i$ 的位置都是无用的。
这就变成了子问题 $\frac{n}{d},\frac{i}{d}$ ,此时两者互质,答案就是 $\frac{n}{d}$。
得 ${\rm Ans}=\dfrac{1}{n}\sum\limits_{i=1}^nn^{gcd(n,i)}$
相信已近在学习群论的你,一定能把这道数论水题秒掉的。
$=\dfrac{1}{n}\sum\limits_{d|n}k^d\sum\limits_{i=1}^n[\gcd(n,i)=d]$
- 后面的 $\sum\limits_{i=1}^n[\gcd(n,i)=d]$
$=\sum\limits_{i=1}^{n/d}[n\perp i]=\varphi(n/d)$
整理得 ${\rm Ans}=\sum\limits_{d|n}\varphi(d)k^{n/d}$
大力求欧拉函数大概是$O(\sqrt{n}\log n)$的样子(反正快速幂也是这个复杂度)。
然而还有一个质因数分解+dfs凑出所有因数+光速幂的 $O(\sqrt{n})$ 解法,懒得写。
**Code:**
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
const int mod=1000000007;
ll powM(ll a,int t){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
int phi(int n)
{
int ans=n;
for (int i=2;i*i<=n;i++)
if (n%i==0){
ans=ans/i*(i-1);
while(n%i==0)n/=i;
}
if (n>1)ans=ans/n*(n-1);
return ans;
}
void solve(int n)
{
ll ans=0;
for (int i=1;i*i<=n;i++)
if (n%i==0){
if (i*i!=n)ans=(ans+powM(n,n/i-1)*phi(i))%mod;
ans=(ans+powM(n,i-1)*phi(n/i))%mod;
}
printf("%lld\n",ans);
}
int T,n;
int main()
{
scanf("%d",&T);
while(T--){
scanf("%d",&n);
solve(n);
}return 0;
}
```
- [P4727 [HNOI2009]图的同构记数](https://www.luogu.com.cn/problem/P4727)
第一眼这道题以为是子集$\rm DP$或者容斥什么的,结果数据范围 $n\leq 60$?
怕不是有多项式算法?
今早闲得无聊拿着《组合数学(第4版)》看了看,里面居然有讲到这个问题。
边 (有,无) 的状态可以看做**对一个完全图染色**,某条边染成黑色说明存在,染成白色就假装不存在,我们成功地把这个问题转化成了一个染色计数问题。
我们先看看式子 : $\dfrac{1}{|G|}\sum\limits_{p∈G}T(p)$
我们现在是在对边计数,但是我们的置换是所有的点置换。
显然,可以由点置换构造出边置换,但是点置换的个数是 $n!$ 的,无法直接枚举。我们需要找到更好的性质来批量处理。
万幸的是, **点置换循环节的构成** 和 **边置换的不动点个数** 有一定的关系。
考虑一个点置换,他每个循环的大小为 $\{S_1,S_2,S_3,...S_m\}$ ($m$为循环节个数,且 $S_1\leq S_2\leq ...\leq S_m$)
能够感知,所有循环节组成相同的点置换,边的等价类个数是相同的。
也就是说我们只要枚举 $S$ ,也就是 $n$ 的**正整数拆分**,就能确定一类边置换。
而正整数拆分的数量级是 $O(e^{\sqrt{\frac{2}{3}n\pi}})$ ,是亚指数的。本题中极限情况**仅在百万级**。
现在,对于一组 $S$ ,计算出这个完全图会究竟会被分成多少个等价类,设其为 $c$ ,根据 $\rm Polya$ 那么不动点个数就是 $2^c$。
- 对于**循环节内的边**,会被分为$\left\lfloor\dfrac{S}{2}\right\rfloor$个等价类。
理解 : 我们可以**把这个循环节看成一个圈**,由于这个圈会转,肯定会让某些边相同。
循环内节点按 $1...S$ 编号,假设有边 $(1,p)$ ,那么边 $(2,p+1)$ , $(3,p+2)$ ……和 $(S-p+1,S)$ 肯定都和 $(1,p)$ 相同。
我们枚举p,会发现 $p>\left\lfloor\dfrac{S}{2}\right\rfloor$ 的情况会和 $p\leq \left\lfloor\dfrac{S}{2}\right\rfloor$的情况重复。
如图 : 左边 $S=8$ ,等价类数为 $\left\lfloor\dfrac{8}{2}\right\rfloor=4$ ; $\quad$ 右边 $S=7$ ,等价类数为 $\left\lfloor\dfrac{7}{2}\right\rfloor=3$。
- 对于**两个循环节之间的边**,会被分为$gcd(S_1,S_2)$个等价类。
理解 : 我们还是采用圈来理解,由于这个两个圈都会转,情况有点复杂。
循环内节点按 $1...S_1$ 与 $1...S_2$ 编号,假设有边 $(x,y)$ ,那么有多少条边和这条边相同呢?
这等价于考虑 : **这条边会在多少次置换后回到原位** ?
答案是 $lcm(S_1,S_2)$ ,如果不理解的话,想象着两个齿轮咬合着转。
那么每个等价类的边得个数为 $lcm(S_1,S_2)$ ,边的总数为 $nm$ ,则等价类的总数是 $\dfrac{nm}{lcm(S_1,S_2)}=gcd(S_1,S_2)$
如图 : 左边 $S_1=4,S_2=2$ ,等价类数为 $gcd(2,4)=2$;
第一个等价类的边 $(1,1),(2,2),(3,1),(4,2)$
第二个等价类的边 $(1,2),(2,1),(3,2),(4,1)$
那么根据上述,对于循环节大小为 $\{S_1,S_2,S_3,...S_m\}$ 的点置换,其对应的边置换的贡献为:
$$\large{2^{\small\sum\limits_{i=1}^m\lfloor\frac{S_i}{2}\rfloor+\sum\limits_{i=1}^m\sum\limits_{j=i+1}^mgcd(S_i,S_j)}}$$
我们接下来还要算循环节大小为 $\{S_1,S_2,S_3,...S_m\}$ 的点置换有几个。
我们考虑把 $\{1,2,3,...,n\}$ 分成 $m$ 个**集合**,大小分别为 $\{S_1,S_2,S_3,...S_m\}$。
我们考虑生成一个长为 $n$ 的排列,然后按照 $S$ 分成 $m$ 组,其实就是多重排列问题。
得 $\dfrac{n!}{\Pi_{i=1}^mS_i!}$
如果有两个 $S$ 相同,是可以调换顺序的,所以还要除掉一些东西。
设 $B_i$ 为 $S=i$ 的个数,得 $\dfrac{n!}{\Pi_{i=1}^mS_i!*\Pi_{i=1}^nB_i!}$
我们还要在每个集合内连边,使得它构成一个循环。
$n$ 元有标号环的个数显然是 $(n-1)!$。
> 可以视作把 $n$ 元链首尾相,由于旋转,每个换对应 $n$ 个链,方案数即为 $n!/n=(n-1)!$。
乘回划分集合的方案数,得到$\dfrac{n!*\Pi_{i=1}^m(S_i-1)!}{\Pi_{i=1}^mS_i!*\Pi_{i=1}^nB_i!}=\dfrac{n!}{\Pi_{i=1}^mS_i*\Pi_{i=1}^nB_i!}$
然后在乘上对应的边置换的贡献,得到
$$\dfrac{n!}{\Pi_{i=1}^mS_i*\Pi_{i=1}^nB_i!}*\large{2^{\small\sum\limits_{i=1}^m\lfloor\frac{S_i}{2}\rfloor+\sum\limits_{i=1}^m\sum\limits_{j=i+1}^mgcd(S_i,S_j)}}$$
别忘了除以置换个数 $n!$。
最后注意实现复杂度和常数,小心被卡。
**Code:**
```cpp
#include<cstdio>
using namespace std;
const int mod=997;
int n;
int powM(int a,int t=mod-2){
int ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
int facn,inv[66],ifac[66],gcd[66][66],
s[66],b[66],ans;
void dfs(int num,int pos,int last)
{
if (num==0){
int t=0,sav=facn;
for (int i=1;i<=n;i++)b[i]=0;
for (int i=1;i<pos;i++)b[s[i]]++;
for (int i=1;i<=n;i++)sav=sav*ifac[b[i]]%mod;
for (int i=1;i<pos;i++)sav=sav*inv[s[i]]%mod;
for (int i=1;i<pos;i++)
for (int j=i+1;j<pos;j++)
t+=gcd[s[i]][s[j]];
for (int i=1;i<=n;i++)t+=s[i]/2;
sav=sav*powM(2,t)%mod;
ans=(ans+sav)%mod;
return ;
}if (last>num)last=num;
for (int i=1;i<=last;i++){
s[pos]=i;
dfs(num-i,pos+1,i);
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)inv[i]=powM(i);
ifac[0]=1;
for (int i=1;i<=n;i++)
ifac[i]=ifac[i-1]*inv[i]%mod;
facn=powM(ifac[n]);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++)
if (i%k==0&&j%k==0)gcd[i][j]=k;
dfs(n,1,n);
printf("%d",ans*ifac[n]%mod);
return 0;
}
```
类似的题目 : [P4128 [SHOI2006]有色图](https://www.luogu.com.cn/problem/P4128)
- [题解 P4916 【魔力环】](https://www.luogu.com.cn/blog/command-block/solution-p4916)