自动搬运

查看原文

来自洛谷，原作者为

	pythoner713 Hope deferred maketh the something sick.

搬运于2025-08-24 22:03:02，当前版本为作者最后更新于2021-01-28 19:55:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

转自我在知乎上写的文章，可以看一看呀：https://zhuanlan.zhihu.com/p/347566986

---

$$\,$$ $$\Large{1,2,4,11,34,156,1044\cdots}$$ $$\,$$

$\color{red}{\sf Part. 1}$

在欣赏一个有趣的数列前，我们需要引入一个图论概念：同构。

$A,B$ 两图同构的意思是：$A$ 图的顶点可以经过一定的重新标号，使得它的点集和边集与 $B$ 相同。 例如，以下两个图是同构的：

因为如果将左图的 (3,4) 两点交换，两图的点集和边集是相等的。

再如，对于有 $4$ 个顶点的简单无向图，共有 $11$ 种互不同构的图：

现在问题来了： $n$ 个顶点组成的简单无向图中，有多少种图互不同构？

这个问题的答案便是文章开头的数列——A000088。

$$\,$$

$\color{red}{\sf Part.2}$

为了解决这个问题，我们需要求助于数学的另一领域：群论。

将图的顶点重新标号，就相当于对点集进行置换，所有的标号方式便构成了一个置换群 $G$ 。我们要求的即是在 $G$ 作用下本质不同的图的个数。对于有 $n$ 个顶点的图，所有的标号方式便是顶点的全排列，即 $|G|=n!$ 。

现在隆重请出 ${\rm Burnside}$ 引理：

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

$|X/G|$ ：集合 $X$ 在群 $G$ 作用下的轨道数（或本质不同元素数）

$|X^g|$ ：在变换 $g$ 下，$X$ 集合中的不动点数

这个定理对解决计数问题有重要作用，举个例子：

在本题中，$X$ 即为 $n$ 个顶点可以构成的 $2^{n(n-1)/2}$ 个简单无向图的集合，$|X/G|$ 即为所求。难点在于怎么求 $|X^g|$，即对于某个点集置换 $g$ 而言，有多少张图在经历变换 $g$ 后依然和原来的图相同？

$$\,$$

$\color{red}{\sf Part.3}$

好了，让我们随机抽取一名幸运置换 $g$ 进行研究，看看有多少张图在经历 $g$ 后纹丝不动。

若隐若现的边太麻烦啦！不妨假设所有边都已存在，现在在我们面前的是一个 $n$ 个节点的完全图，然后我们需要给边们染色，染成存在或不存在两种颜色，从而得到 $X$ 中所有的图。

如何判断染成什么样子可以使得它成为置换 $g$ 中的不动点呢？

注意到有些边是等价的，等价的边一定要染成同一个颜色，要么同时存在，要么同时不存在。

例如一个三个顶点的三角形，如果置换 $g$ 的作用是将三个顶点顺时针轮换，那么这三条边是等价的（同属一个等价类），要么同时存在（形成一个完整的三角形），要么同时不存在（形成三个孤立的顶点）。不可能出现有两条边存在，一条边不存在的情况，否则经过一次旋转，缺口便到了另外两个点间，与原来的图就不同了。注意到此时三边同属 $1$ 个等价类，每个等价类要么染要么不染，因此在此置换 $g$ 下有 $2^1=2$ 个不动点。

还是这个三角形，这回置换 $g$ 变为交换两个点，另一个点不动。那么两个动点间的边单独属于一个等价类，另外两条边属于另一等价类，一共有 $2$ 个等价类。每个等价类要么染要么不染，因此再此置换 $g$ 下有 $2^2=4$ 个不动点。

换句话说，对于置换 $g$ 如果存在 $k$ 个边的等价类，那么 $X$ 中就有 $2^k$ 个不动点。即：

$$|X^g|=2^k$$ $$\,$$

$\color{red}{\sf Part.4}$

好啦，接下来的问题就是求 $k$ ——置换 $g$ 下边的等价类个数。这部分是关键，而且有些绕，我们分两步走：

第一步，我们要将 $g$ 拆分为若干个不相交的循环置换。

这是什么意思呢？举个例子， $g$ 可以把点 $\{1,2,3,4,5,6\}$ 置换成 $\{2,3,1,5,4,6\}$ ，可以记作： $g= \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 3 & 1 & 5 & 4 & 6 \end{pmatrix}$ 。注意到这个置换可以分解成几个不相交的部分，其中每个部分都是一个循环：

$$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 3 & 1 & 5 & 4 & 6 \end{pmatrix}=\begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix} \circ \begin{pmatrix} 4 & 5\\ 5 & 4 \end{pmatrix} \circ \begin{pmatrix} 6\\ 6 \end{pmatrix} $$

现在将我们当前研究的置换 $g$ 拆成 $K$ 个循环，长度分别为 $b_1,b_2,\cdots,b_K$ 。

第二步，将边按照端点分成两类

1.端点同时存在于同一循环内的边。设循环长度为 $b$ ，则次循环共有 $\left \lfloor \frac{b}{2} \right \rfloor$ 个等价类。例如对于长度为 $6$ 的循环置换 $\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 2 & 3 & 4 & 5 & 6 & 1 \end{pmatrix}$ ，我们把这 $6$ 个点排成正六边形：

（颜色相同的边同属于一个等价类）

不难发现两条边等价当且仅当它们长度相等，等价的边必须同时染/不染，否则会导致图案不具有旋转对称性，经过循环置换后也必定与原图不同。而正 b 边形中，共有 $\left \lfloor \frac{b}{2} \right \rfloor$ 种长度不同的线段，也就是对应 $\left \lfloor \frac{b}{2} \right \rfloor$ 个边的等价类。得证。

因此这一类边一共贡献了 $\sum_{i=1}^K\left \lfloor \frac{b_i}{2} \right \rfloor$ 个等价类。

2.端点存在于不同循环内的边 。例如 $\begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix} \circ \begin{pmatrix} 4 & 5\\ 5 & 4 \end{pmatrix} \circ \begin{pmatrix} 6\\ 6 \end{pmatrix}$ ，则连接 $3,4$ 的边不在同一循环内。这时，设两个循环的长度分别为 $b_1,b_2$ ，那么两个循环间共有 $b_1b_2$ 条这样的边。

（如上图，循环 $(1,2,3)$ 与 $(4,5)$ 间共有 $6$ 条边，但同属于 $\gcd(2,3)=1$ 个等价类）

每条边经过 ${\rm lcm}(b_1,b_2)$ 次循环后会回归原位，所以每个等价类大小为 ${\rm lcm}(b_1,b_2)$ 。也就是说，一共有 $\frac{b_1b_2}{{\rm lcm}(b_1,b_2)}=\gcd(b_1,b_2)$ 个等价类。别忘了，这只是 $g$ 内其中两个循环产生的贡献，要把每对循环的贡献累加起来，也就是： $\sum_{i=1}^K\sum_{j=1}^{i-1}\gcd(b_i,b_j)$ 个等价类。

至此两种情况已经分类讨论完毕，边的等价类个数就等于两种情况数量之和：

$$k=\sum_{i=1}^K\left \lfloor \frac{b_i}{2} \right \rfloor +\sum_{i=1}^K\sum_{j=1}^{i-1}\gcd(b_i,b_j) $$$$|X/G|=\frac{1}{|G|}\sum_{g\in G}2^k$$

是不是感觉离成功不远了呢（

$$\,$$

$\color{red}{\sf Part.5}$

其实到了这里，我们已经找到计算文章开头数列的方法了。但是，别忘了 $|G|=n!$ ，枚举每一个置换 $g$ ，时间复杂度少说也得 $O(n!)$ 。我们是否以优化一下计算方法呢？

注意到有许多置换会被重复计算，如下面两个置换：

$$\begin{pmatrix} 1 & 2 & 3\\ 2 & 3 & 1 \end{pmatrix} \circ \begin{pmatrix} 4 & 5\\ 5 & 4 \end{pmatrix} \circ \begin{pmatrix} 6\\ 6 \end{pmatrix}\qquad\begin{pmatrix} 1 \\ 1 \end{pmatrix} \circ \begin{pmatrix} 2 & 3\\ 3 & 2 \end{pmatrix} \circ \begin{pmatrix} 4 & 5 & 6\\ 6 & 4 & 5 \end{pmatrix} $$

它们间没有本质上的区别，对应的 $k$ 值都相等（因为 $b$ 都是 $1,2,3$ ），本可以统一计算。

一般地，如果两个置换的循环长度排序后一一相等，那么两者对答案的贡献 $2^k$ 是相等的。因此，与其枚举每一种置换再拆分，不如枚举 $n$ 的拆分代表一类置换，再统一计算贡献。 例如 $n=5$ 时，它的拆分有 $(1,1,1,1,1),(1,1,1,2),(1,1,3),(1,2,2),(1,4),(2,3),(5)$ ，其中 $(1,2,2)$ 统一代表了形如

$$\begin{pmatrix} * \\ * \end{pmatrix} \circ \begin{pmatrix} * & *\\ * & * \end{pmatrix} \circ \begin{pmatrix} * & *\\ * & * \end{pmatrix} $$

的置换。也就是循环长度 $b=\{1,2,2\}$ 的置换。

那么对于某个拆分，如何计算有多少对应的置换呢？

首先 $1\sim n$ 随便放一共有 $n!$ 种方案，但长度为 $b$ 的循环会贡献 $b!$ 倍重复方案。所以单是分配每个元素在哪个循环中就有 $\frac{n!}{\prod(b_i!)}$ 种方案。

接着是循环的内部分配，也就是 $b_i$ 个元素的圆排列，有 $\prod(b_i-1)!$ 种方案。

但事实上，对于长度相等的循环它们之间可以彼此交换，本质上是一样的，因此还是会算重。设 $c$ 表示表某个长度的循环的个数，则会算重 $c!$ 倍。因此答案还需除以 $\prod(c_i!)$ 。

结合上述三项，可以得到，拆分 $b_i$ 所对应的置换个数为：

$$\frac{n!}{\prod(b_i)\prod(c_i!)}$$

用这个式子改进之前的 n! 枚举算法，可以得到：

$$|X/G|=\frac{1}{|G|}\sum_b \frac{n!}{\prod(b_i)\prod(c_i!)} 2^k $$

$|G|=n!$ ，里外两项正好抵消，得到最终的形式：

$$\,$$ $$\large{|X/G|=\sum_b \frac{2^k}{\prod(b_i)\prod(c_i!)}} $$$$\large{k=\sum_{i=1}^K\left \lfloor \frac{b_i}{2} \right \rfloor +\sum_{i=1}^K\sum_{j=1}^{i-1}\gcd(b_i,b_j)} $$$$\,$$

大功告成。

最后再提一下时间复杂度。DFS枚举 $n$ 的拆分 $b$ ，再 $O(K^2)$ 求 $k$ 。增长速度是 A000041，A296010 的乘积。前者增速是 $O\left (\frac{e^{\sqrt{n}}}{n}\right )$，后者不知道。估计总复杂度大概在 $O(10^{\sqrt{x}})$ 左右。

$$\,$$

#include<bits/stdc++.h>
#define int long long
using namespace std;

int ans, n, p = 997, b[70], jc[70], jd[70];

int gcd(int a, int b){
	return !b ? a : gcd(b, a % b);
}

int qpow(int A, int B){
	int C = 1;
	while(B){
		if(B & 1) C = C * A % p;
		A = A * A % p, B >>= 1;
	}
	return C;
}

void init(){
	jc[0] = 1;
	for(int i = 1; i < 70; i++){
		jc[i] = i * jc[i - 1] % p;
	}
	// 预处理阶乘
}

void work(int len){
	int u = 0, v = 1;
	for(int i = 1; i <= len; i++){
		u += b[i] >> 1;
		for(int j = 1; j < i; j++){
			u += gcd(b[i], b[j]);
		}
		// 计算边的等价类个数，u 即题解的 k
	}
	for(int i = 1; i <= len; i++){
		v = v * b[i] % p;
	}
	for(int i = 1, j; i <= len;){
		for(j = i; b[i] == b[j] && j <= len; j++);
		v = v * jc[j - i] % p;
		// 去除长度相等的循环带来的重复计算
		i = j;
	}
	ans = (ans + qpow(v, p - 2) * qpow(2, u) % p) % p;
}

void dfs(int now, int last, int rem){
	if(!rem){
		// DFS 枚举 n 的所有拆分
		work(now - 1);
		return;
	}
	for(int i = last; i <= rem; i++){
		b[now] = i;
		dfs(now + 1, i, rem - i);
	}
}

signed main(){
	cin >> n;
	init();
	dfs(1, 1, n);
	cout << ans;
	return 0;
}

$$\,$$

$\color{red}{\sf Part.6}$

不妨思考形式更一般的问题：

$n$ 个节点的完全无向图，用 $m$ 种颜色给每条边染色，可以染出几种互不同构的图？

答案十分简单，只需要将上述式子中的 2 改为 m 即可：

$$\,$$ $$\large{|X/G|=\sum_b \frac{\color{red}{m}^\color{black}k}{\prod(b_i)\prod(c_i!)}} $$$$\large{k=\sum_{i=1}^K\left \lfloor \frac{b_i}{2} \right \rfloor +\sum_{i=1}^K\sum_{j=1}^{i-1}\gcd(b_i,b_j)} $$$$\,$$

因为在原问题中，每条边有存在/不存在两种情况，这等价于用两种颜色给每条边染色，不动点数为 $2^k$ 。现在改为用 $m$ 种颜色染色，自然就是 $m^k$ 了。

双倍经验：P4128