群论小记 更新于 2026/7/9 19:53:10 作者

command_block

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定理

这道题里的置换就是旋转。

有旋转 $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:

#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]图的同构记数

第一眼这道题以为是子集$\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:

#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]有色图

• 题解 P4916 【魔力环】