赛时拿到高分，赛后和 lrs 花了 1h 推到满分，写题解纪念之。

我也不知道这篇题解怎么这么长。

题目链接

题意

对于一张有 $n$ 个点，$nm$ 条边的有向图（边有编号，编号在 $1\sim m$ 之间，可重），我们称它是好的，当且仅当它满足以下条件：

1. 对于每一个点，以它为起点的边恰好有 $m$ 条，且编号为 $1\sim m$ 的各有一个；
2. 对于每一个点，以它为终点的边恰好有 $m$ 条，且编号为 $1\sim m$ 的各有一个；
3. 任选一个点 $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$ 条边的图，有多少种方案是好的。

$1\le n\le 2\times 10^3$。

$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}$ 的值是多少。

按照实际意义，我们枚举第 $y+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)$。 写完力！