对P10219的一些补充说明

SnowFlavour · 2025-05-10 16:27:36 · 题解

说明

本题解不提供完整思路，是对于其他题解的补充说明（主要是证明了一些性质）。

建议理解思路后再翻阅本题解。

一、合并与同构的关系

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

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

首先，对于题目中的条件：

存在一个非负整数 d 使得每个城市恰好是 d 条虫洞的起点，也恰好是 d 条虫洞的终点。

对于每个城市而言，在以它为起点的虫洞的编号中，1 到 d 恰好各出现一次。

对于每个城市而言，在以它为终点的虫洞的编号中，1 到 d 恰好各出现一次。

任意选取一个城市 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，该点唯一。

考虑证明同构。

假设当前已经连接了 k 种边，现在连接 k + 1 种边，那么先连接一条 k + 1 种边 u \to v，可以得到 \forall w \in [1,k] 且 w \in \mathbb{N},V(u,w) \to V(v, w)。

而这个结论具有传递性。所以所有能从 u 到达的节点都满足这个性质，因而这些点构成的子图同构。

同理，能够到达 u 的点也是同构的。

因此两个子图是同构的。

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

2. 连通块一定自同构

这个性质可以通过归纳证明。

假设一个连通块连接了 k 种边，

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

二、组合计数的公式

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

1. 计算连通块的排列

大部分题解对这个公式的解释是归纳法、瞪眼法和 oeis 法。

定义将 i 个连通块等分成 j 组（满足 j|i），各组内部进行圆排列的方案数是 f_{i, j}。

首先，f_{i,j} 显然可以用 dp 来求。但是我们可以考虑推式子：

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

因此，得到公式：

f_{i,j}=\frac{i!}{j!(\frac{i}{j})^j}

2. DP 方程的压维

考虑到压维以后的方程实际上相当于连通块是点的合并，我们只需要计算从一个点到一个连通块的变化即可。

首先明确原方程的 s^{i - x + 1} 仅解决了连边的问题，所有连通块的位置是通过 f_{i,j} 计算的，在连边时相当于位置锁定。

那么我们就看看点和连通块的区别。

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

也就是说，我们只要找到在多次合并中，“自由”的连通块数量即可。（注意：无论合并以后的连通块如何，我们的连通块合并始终是由点的合并“膨胀”而来的，所以每一次一个连通块即使是自由的，也仍然只有 s 种连边的方式。）

由于每一次合并的时候都必然存在自由的连通块，我们不妨钦定一个连通块始终是自由的。

以下的内容是在多次合并过程中的某一次，也就是说原先的连通块现在已经被合并成了大连通块。

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

这样我们发现，这个始终自由的连通块再 j 次合并中都是可以自由连接的，方案为 s^j，而剩下的连通块只要有一次不是作为封圈的连通块，它就再也不会自由连接了，而所有的连通块都一定有一次是自由的（毕竟最后合并成了一个连通块），所以方案是 s^{i-1}。

因此，我们得到了如下公式：

dp_{i,j,s}=dp_{i,j,1} \times s^{i+j-1}

为什么我们得到的结论如此简洁？一是因为我们合并时一个连通块要么完全自由，要么就是没有任何自由，所以自由的方案数一定是 s 的次方；二是因为合并的过程中只关心从“点”到“连通块”的变化，并没有关注连接位置的不同（那部分内容在 f_{i,j} 里面），并且最终结果是“一个连通块”。

三、一些实现上的小问题

1. 哈希

免责声明：这部分内容能通过所有数据，不保证正确性，如果能证明正确性或者能给出正确的概率，欢迎在评论留言。

具体地，我们从任何一个点开始，按照边权的顺序 BFS，依次把经过的边存储起来。由于自同构性，两个同构的连通块显然会得到一个相同的序列。

2. 倍增的实现

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

根据推导，我们有如下式子：

fp_{i,x+y}=\sum_{j|i}\frac{fp_{j,x}fp_{\frac{i}{j},y}}{j^y}

考虑当 x=y=2^a 时，原式可化为：

fp_{i,2^{a+1}}=\sum_{j|i}\frac{fp_{j,2^a}fp_{\frac{i}{j},2^a}}{j^{2^a}}

这玩意可以 O(n\log k \ln n) 求。（当然，快速幂复杂度也得算上，所以最后事实上会多一个 \log。）

最终，我们要求的是 fp_{i,k}。这可以通过二进制分解来实现。简单来说就是套公式，由于描述比较复杂，我就直接摆代码了：

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;
            }
        }
    }
}

（我的码风可能有点抽象……）

四、结语

虽然没有完整思路，但是这篇题解的篇幅也不算小了。

事实上我认为最重要的是推式子的能力。第二部分的两个公式都可以打表+归纳得出结论，但是这样的问题是不稳定，毕竟你不能指望当式子很复杂的时候还能够瞪出结果。然而构造和组合公式的力量是强大的，它可以确保你无论结论多复杂，它都应当没有问题。

当然，考场上你只要能够得到正确结论就能得分，所以场上什么方式都随便用，但是平时应该多锻炼的是后者，这是更强的道路。

同时不应该忽视一些实现的细节（~~我才不会告诉你我因为上面的代码滚的时候没清空调了一个小时~~），毕竟信竞的题目就是这样，一个细节可以把分数直接归零。

如果能勘误，欢迎随时在评论留言！