说明

一、合并与同构的关系

为方便表述，两个连通块的同构称为“异同构”，同一个连通块关于自己同构称为“自同构”。

1. “可以合并”合并意味着“异同构”

1. 存在一个非负整数 $d$ 使得每个城市恰好是 $d$ 条虫洞的起点，也恰好是 $d$ 条虫洞的终点。
2. 对于每个城市而言，在以它为起点的虫洞的编号中，$1$ 到 $d$ 恰好各出现一次。
3. 对于每个城市而言，在以它为终点的虫洞的编号中，$1$ 到 $d$ 恰好各出现一次。
4. 任意选取一个城市 $u$ 和正整数 $1\le j_1, j_2 \le d$。设从 $u$ 出发，先经过一次编号为 $j_1$ 的虫洞，再经过一次编号为 $j_2$ 的虫洞，到达城市 $v_1$。设从 $u$ 出发，先经过一次编号为 $j_2$ 的虫洞，再经过一次编号为 $j_1$ 的虫洞，到达城市 $v_2$。则条件 $v_1=v_2$ 必定满足。

• 定义 $V(u,w)$ 表示从 $u$ 出发走种类为 $w$ 的边到达的点。由于性质 2，该点唯一。
• 定义 $P(u,w)$ 表示从 $u$ 出发走种类为 $w$ 的反向边到达的点。由于性质 3，该点唯一。

注意：我们认为 $u$ 可以从 $u$ 到达，也可以到达 $u$，因此这两个导出子图一定是有交的。

2. 连通块一定自同构

• 当 $k = 0$ 时（其实就是个点），显然成立。
• 若 $k - 1$ 时成立，那么对于任意一个连通块上的点 $u$：
  • 对于任意一个合并以后处于同一个连通块的节点 $v$，它们所在的小连通块一定是同构的。
  • $u$ 和 $v$ 一定都有一条 $k$ 边连向下一个连通块。由于小连通块是自同构的，所以连接的位置不重要。
  • 两点连向的下一个连通块也一定满足上述性质，因此整个大连通块都满足。
  • 因此这个大连通块自同构。

二、组合计数的公式

这部分的字母会参考 @Wuyanru的题解，建议随时翻阅。

1. 计算连通块的排列

1. 我们要把连通块分成 $j$ 组。这个要求的一种可行的刻画是直接求出这些连通块的全排列 $i!$，然后前 $j$ 个是一组，第 $j + 1$ 到 $2j$ 个是一组，以此类推。
2. 接下来考虑圆排列。我们知道对于每一组，圆排列的方案数要除以连通块的数量 $\frac{i}{j}$。因此，$j$ 个连通块就需要将这个数算 $j$ 次。
3. 考虑这样是否还有重复？显然，$1,2,3,4,5,6$ 和 $3,4,1,2,5,6$ 是一样的，但是被重复计算在内。也就是说，在分组的时候我们并没有考虑组间的顺序，因此总方案数就要再除以 $j!$。

2. DP 方程的压维

• 大的连接方向是清晰的，并且在点和连通块上都一样。
• 对于一个连通块向下一个连通块连边的连接上，一个连通块会有 $s$ 种连接方式，因此如果每个连通块都随意连边，会比点连边多出 $s^i$ 的系数。
• 然而我们要确保同构。这事实上意味着，有些连通块可以自由选择如何连向下一个连通块，而有些并没有自由，只能“被迫”处在一个位置。

• 当只有一个大连通块的时候，显然只有这一个连通块是自由的。
• 否则，我们让这个连通块先随便连。这样，这个连通块所在的大连通块的连接方式就被确定了。接下来，由于其它连通块连接到最后时，封圈的那一个连通块不是自由的，这一次我们就让这个连通块选择连边方式。
  • 而这个连通块又是由几个更小的连通块合并来的，所以我们再找小连通块中封圈的连通块，同理这个封圈的块又可以找到更小的连通块，以此类推，就会找到最初封圈的连通块。

三、一些实现上的小问题

1. 哈希

2. 倍增的实现

这部分的字母依然会参考@Wuyanru的题解。

for (int j = 50; j >= 0; j--) {
    if (1ll << j <= nw) {
        swap(now, old);
        for (int i = 1; i <= n; i++) res[i][now] = 0;
        nw -= (1ll << j);
        for (int i = 1; i <= n; i++) {
            for (auto k : fac[i]) {
                res[i][now] =
                    (res[i][now] + res[k][old] * p[i / k][j] % MD *fast(fast(k, 1ll << j), MD - 2) % MD) %MD;
            }
        }
    }
}

四、结语