P10219 [省选联考 2024] 虫洞
Wuyanru
·
·
题解
赛时拿到高分，赛后和 lrs 花了 1h 推到满分，写题解纪念之。
我也不知道这篇题解怎么这么长。
题目链接
题意
对于一张有 n 个点，nm 条边的有向图（边有编号，编号在 1\sim m 之间，可重），我们称它是好的，当且仅当它满足以下条件：
- 对于每一个点，以它为起点的边恰好有 m 条，且编号为 1\sim m 的各有一个；
- 对于每一个点，以它为终点的边恰好有 m 条，且编号为 1\sim m 的各有一个；
- 任选一个点 u(1\le u\le n) 与两种编号 j_1,j_2(1\le j_1,j_2\le m)，设从 u 出发，先走 j_1 边，再走 j_2 边到达的点为 v_1，从 u 出发，先走 j_2 再走 j_1 到达的点位 v_2，都有 v_1=v_2。
现给定一张 n 个点 m 条边的图，保证他是好的。
你现在需要新建 nk 条边，边的编号在 m+1\sim m+k 之间。
求最终这张有 (k+m)n 条边的图，有多少种方案是好的。
$0\le m\le 10^3$。
$1\le k\le 10^{15}$。
## 题解
这道题实在是太难了，我在最终解决它的过程中也使用了一些工具（oeis）。
所以这篇题解主要分为两部分，第一部分根据我的考场思路，讲如何自然地推出 $64$ 分，第二部分讲如何把 $64$ 分优化为满分。
**本题解中所有的连通均指有向图的弱联通。**
### 基础结论
这道题看起来没有任何切入点，我们不妨从简单的情况看起。
考虑 $m=1$ 的时候，整张图长什么样子。
不难发现，此时整张图一定被分为若干个环。
在此基础上，考虑加上编号为 $2$ 的边，看看图会有什么变化。
假设现在有一个编号为 $1$ 的边构成的环 $1\to 2\to 3\to 1$，如下图（黑色表示编号为 $1$ 的边，红色表示编号为 $2$ 的边）：
假设 $1$ 号点连出的 $2$ 边指向 $x$，$x$ 连出的 $1$ 边指向 $y$。
那么按照第三条条件，从点 $1$ 经过 $2,1$ 两条边到了 $y$，那么从 $1$ 走 $1,2$ 两条边也应该走到 $y$。
那么我们就知道，$2$ 连出的 $2$ 边应当指向 $y$。
同理，$3$ 连出的 $2$ 边，与 $y$ 连出的 $1$ 边应当指向一个点 $z$。
特殊地，我们还可以推出 $z$ 连出的 $1$ 边应当指向点 $x$。
这里可以发现一些规律：
若存在一条 $x$ 边 $u\to v$，则 $u$ 所在的连通块（仅保留前 $x-1$ 种边）连出的所有 $2$ 边，一定在连向 $v$ 所在的连通块。
入边同理。
证明是简单的，按照我上述的过程进行构造即可，由于不是重点就不展开讲了。
特殊地，我们从上述条件中可以看出，如果在连完一条 $x$ 边后，两个连通块合并，则两个连通块大小一定相等。
但是，是否所有大小相等的连通块都可以进行连边合并呢？
显然是不行的。
例如上图有 $3$ 个连通块，每一个连通块大小都是相等的。
但是 $1,2$ 两个连通块不能合并，$2,3$ 两个连通块也不能合并（可以自己试试）。
唯一可以合并的是 $1,3$ 两个连通块，这里画出了可能的一种合并方式。
为了判断两个连通块能否合并，我们不妨自己进行这样一个定义：
>对于两个只存在编号为 $1\sim x$ 的边的连通块 $(V_1,E_1)$ 和 $(V_2,E_2)$，与点 $u\in V_1$ 和 $v\in V_2$。
>
>若称这两个连通块关于 $(u,v)$“同构”，当且仅当：
>
>1. $|V_1|=|V_2|$ 且 $|E_1|=|E_2|$；
>2. 存在 $V_1$ 的排列 $p=(p_1,p_2,\dots,p_{|V_1|})$ 使得 $p_1=u$；
>3. 存在 $V_2$ 的排列 $q=(q_1,q_2,\dots,q_{|V_2|})$ 使得 $q_1=v$；
>4. 对于任意节点 $p_i(1\le i\le |V_1|)$，若从 $p_i$ 出发走 $w(1\le w\le x)$ 边到达了点 $p_j$，则从 $q_i$ 出发走 $w$ 边一定到达节点 $q_j$。
~~不知道这个名字起的怎么样，我觉得挺顺耳的。~~
显然，按照我们的定义，有一些显然的结论，例如同构具有传递性。
那么对于任意两个点 $u,v$，若他们所在的连通块在连完一条 $x$ 边 $u\to v$ 后合法，当且仅当这两个连通块关于 $(u,v)$ 同构。
这个比较简单，就不证了。
比较重要的是下面这个结论：
>对于一个连通块 $(V,E)$ 与其中两点 $u,v\in V$，这个连通块与自己关于 $(u,v)$ 同构。
这个也比较显然，归纳就可以证明。
大题的思路是考虑若干个连通块，在连完一种边后合并在一起的过程。
就可以利用同构的传递性，以及合并连通块需要同构，这两个性质进行证明。
那么还可以推出：
> 对于两个连通块 $(V_1,E_1)$ 与 $(V_2,E_2)$，若他们关于 $(u,v)(u\in V_1,v\in V_2)$ 同构。
>
> 则对于任意两个点 $u'\in V_1$ 与 $v'\in V_2$，这两个连通块关于 $(u',v')$ 同构。
这个也好证，结合上一个结论与传递性即可。
从这个结论也可以看出，两个连通块同构，和我们选取的两个点 $(u,v)$ 并没有什么关系（其实选取也只是为了方便证明）。
所以下文的同构，会将这两个点省略，直接说某两个连通块同构。
这个结论是很有意思的，这告诉我们，对于两个同构的连通块。
如果我们要从第一个连通块向第二个连通块连边，那么我们只需要确定任何一个点所指向的点，就能唯一确定一个合法方案。
### dp 设计
至此，我们就可以尝试进行做法的设计了。
首先考虑输入的图。不难发现，若当前的两个连通块在连完了新的 $k$ 种边后合并了，则这两个连通块此时同构。
显然，我们可以把所有的连通块分为若干类，其中每一类的所有连通块同构。
那么每一类之间的答案是独立的，我们只需要把它们的答案分别算出，乘起来即可。
而将连通块分类也是简单的，容易使用哈希在 $O(n^2+nm)$ 复杂度内完成分类。
现在我们只需要考虑所有连通块都同构的情况了。
设 $dp_{i,j,s}$ 表示现在有 $i$ 个同构的连通块，每一个大小都是 $s$，在连了 $j$ 种边后，所有点被连进一个连通块的方案数。
所有点被连进一个连通块如果能算出来，那么最终的方案容易使用另一个 dp 算出。
考虑这个状态如何转移。
边界状态是简单的，显然有 $dp_{1,0,s}=1$。
否则，我们枚举 $x$，表示第一次连边之后，整张图剩下了 $x$ 个连通块，那么每一个连通块必然是由 $\dfrac{i}{x}$ 个连通块拼起来的。
那么有转移方程 $dp_{i,j,s}=\sum\limits_{x\mid i}dp_{x,j-1,\frac{is}{x}}f_{i,x}\times ?$。
其中 $f_{i,j}$ 表示将 $i$ 个连通块分为 $j$ 个大小相等的圆排列的方案数，容易使用 $O(n\ln n)$ 的 dp 算出。
方程中的 $?$ 表示连边的方案数，这个需要推一下。
容易发现，对于前 $\dfrac{i}{x}$ 个连通块来说，他们组成的大连通块长什么样子是无所谓的，所以方案数是 $s^{\frac{i}{x}}$。
而对于后面的所有连通块，我们需要保证练成的样子与第一组同构，所以对于每一组的最后一个连通块，我们有唯一的连边限制。
也就是说，后面所有的方案数是 $s^{(x-1)(\frac{i}{x}-1)}$。
所以转移方程是 $dp_{i,j,s}=\sum\limits_{x\mid i}dp_{x,j-1,\frac{is}{x}}f_{i,x}s^{i-x+1}$。
这样我们就可以在大约 $O(n^2k\ln n)$ 的复杂度内完成转移。
dp 显然是正确的，但是他的复杂度太高了。而且似乎有些怪怪的？
似乎 $s$ 这一维自始至终都是没有任何用处的？
考虑 $dp_{i,j,s}$ 中，$s$ 总共被乘了多少遍。
容易发现，上边的 $i-x+1$ 表示 当前连通块个数 减去 连完一条边的连通块个数 加上 $1$。
那么裂项相消之后不难想到：
> 结论：$dp_{i,j,s}=dp_{i,j,1}s^{i+j-1}$。
考虑归纳证明，对 $j=0$ 显然成立。
假设对 $j<p$ 的情况成立，那么对于 $j=p$ 的情况：
$$
\begin{aligned}
dp_{i,j,s}&=\sum_{x\mid i}dp_{x,j-1,\frac{is}{x}}f_{i,x}s^{i-x+1}\\
&=\sum_{x\mid i}dp_{x,j-1,1}f_{i,x}s^{i-x+1}\left(\dfrac{is}{x}\right)^{x+j-2}\\
&=s^{i+j-1}\sum_{x\mid i}dp_{x,j-1,1}f_{i,x}\left(\dfrac{i}{x}\right)^{x+j-2}\\
&=s^{i+j-1}\sum_{x\mid i}dp_{x,j-1,\frac{i}{x}}f_{i,x}\\
&=s^{i+j-1}dp_{i,j,1}\\
\end{aligned}
$$
显然是对的。
这样我们就可以在 $O(nk\ln n)$ 的时间复杂度内完成这个 dp。
那么这个 dp 就可以只保留前两维，有转移式 $dp_{i,j}=\sum\limits_{x\mid i}dp_{x,j-1}f_{i,x}\left(\dfrac{i}{x}\right)^{x+j-2}$。
总时间复杂度是 $O(nm+n^2+nk\ln n)$，可以拿到 $64$ 分。
时间复杂度瓶颈在于最后这个 dp。
### dp 优化
考场上写完这里就只剩 $1$ 分钟了，直接加了个文件走人了。
考虑先打表看看规律。
首先可以来看 $f_{i,j}(j\mid i)$，可以发现有 $f_{i,j}=\dfrac{i!}{j!\left(\dfrac{i}{j}\right)^j}$。
证明的话还是归纳，显然对 $f_{i,1}$ 都成立。
$$
\begin{aligned}
f_{i,j}&=f_{i-\frac{i}{j},j-1}\left(\dfrac{i}{j}-1\right)!\dbinom{i-1}{\frac{i}{j}-1}\\
&=\dfrac{\left(i-\dfrac{i}{j}\right)!}{(j-1)!\left(\dfrac{i}{j}\right)^{j-1}}\left(\dfrac{i}{j}-1\right)!\dfrac{(i-1)!}{\left(\dfrac{i}{j}-1\right)!\left(i-\dfrac{i}{j}\right)!}\\
&=\dfrac{(i-1)!}{(j-1)!\left(\dfrac{i}{j}\right)^{j-1}}\\
&=\dfrac{(i-1)!}{(j-1)!\left(\dfrac{i}{j}\right)^{j}}\times\dfrac{i}{j}\\
&=\dfrac{i!}{j!\left(\dfrac{i}{j}\right)^j}
\end{aligned}
$$
所以结论成立。
带回原来的式子。
$$
\begin{aligned}
dp_{i,j}&=\sum_{x\mid i}dp_{x,j-1}f_{i,x}\left(\dfrac{i}{x}\right)^{x+j-2}\\
&=\sum_{x\mid i}dp_{x,j-1}\left(\dfrac{i}{x}\right)^{x+j-2}\dfrac{i!}{x!\left(\dfrac{i}{x}\right)^x}\\
&=\sum_{x\mid i}dp_{x,j-1}\left(\dfrac{i}{x}\right)^{j-2}\dfrac{i!}{x!}\\
&=\sum_{x\mid i}dp_{x,j-1}\left(\dfrac{i}{x}\right)^{j-1}\dfrac{(i-1)!}{(x-1)!}\\
\end{aligned}
$$
有个阶乘，还有个指数，很烦，设 $fp_{i,j}=\dfrac{dp_{i,j}}{(i-1)!i^{j-1}}$。
其中边界条件有一些变化，为 $fp_{i,1}=1$，可以发现结果不变。
那么 $fp_{i,j}=\dfrac{dp_{i,j}}{(i-1)!i^{j-1}}=\sum\limits_{x\mid i}\dfrac{fp_{x,j-1}}{x}$。
而我们的目标是求出 $fp_{1\sim n,k}$。
考虑实际意义，$fp_{i,j}$ 实际上是在说：
对于所有长度为 $j$，满足 $a_1=1,a_j\mid i$，且有 $a_{i-1}\mid a_i$ 的序列 $\{a_j\}$。
定义他的权值是 $\prod\limits_i \dfrac{1}{a_i}$，求所有合法序列的权值和。
考虑 $fp_{i,x+y}$ 的值是多少。
按照实际意义，我们枚举第 $x+1$ 项填了哪个数字。
那么 $fp_{i,x+y}=\sum\limits_{j\mid i}\dfrac{fp_{j,x}fp_{i/j,y}}{j^y}$。
这样我们就可以以一个类似快速幂的形式，求出所有 $fp_{*,k}$ 的值。
总时间复杂度是 $O(n^2+nm+n\ln n\log k)$。
代码比较好写，就不放了~~其实是懒得粘下来~~。
写完力！
update：代码贴到[这里](https://www.luogu.com.cn/paste/x4mg5m28)了，最后一个 dp 的实现不太一致。