1 条题解

  • 0
    @ 2024-3-7 14:41:57

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

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

    题目链接

    题意

    对于一张有 nn 个点,nmnm 条边的有向图(边有编号,编号在 1m1\sim m 之间,可重),我们称它是好的,当且仅当它满足以下条件:

    1. 对于每一个点,以它为起点的边恰好有 mm 条,且编号为 1m1\sim m 的各有一个;
    2. 对于每一个点,以它为终点的边恰好有 mm 条,且编号为 1m1\sim m 的各有一个;
    3. 任选一个点 u(1un)u(1\le u\le n) 与两种编号 j1,j2(1j1,j2m)j_1,j_2(1\le j_1,j_2\le m),设从 uu 出发,先走 j1j_1 边,再走 j2j_2 边到达的点为 v1v_1,从 uu 出发,先走 j2j_2 再走 j1j_1 到达的点位 v2v_2,都有 v1=v2v_1=v_2

    现给定一张 nn 个点 mm 条边的图,保证他是好的。

    你现在需要新建 nknk 条边,边的编号在 m+1m+km+1\sim m+k 之间。

    求最终这张有 (k+m)n(k+m)n 条边的图,有多少种方案是好的。

    1n2×1031\le n\le 2\times 10^3

    0m1030\le m\le 10^3

    1k10151\le k\le 10^{15}

    题解

    这道题实在是太难了,我在最终解决它的过程中也使用了一些工具(oeis)。

    所以这篇题解主要分为两部分,第一部分根据我的考场思路,讲如何自然地推出 6464 分,第二部分讲如何把 6464 分优化为满分。

    本题解中所有的连通均指有向图的弱联通。

    基础结论

    这道题看起来没有任何切入点,我们不妨从简单的情况看起。

    考虑 m=1m=1 的时候,整张图长什么样子。

    不难发现,此时整张图一定被分为若干个环。

    在此基础上,考虑加上编号为 22 的边,看看图会有什么变化。

    假设现在有一个编号为 11 的边构成的环 12311\to 2\to 3\to 1,如下图(黑色表示编号为 11 的边,红色表示编号为 22 的边):

    image

    假设 11 号点连出的 22 边指向 xxxx 连出的 11 边指向 yy

    那么按照第三条条件,从点 11 经过 2,12,1 两条边到了 yy,那么从 111,21,2 两条边也应该走到 yy

    那么我们就知道,22 连出的 22 边应当指向 yy

    同理,33 连出的 22 边,与 yy 连出的 11 边应当指向一个点 zz

    特殊地,我们还可以推出 zz 连出的 11 边应当指向点 xx

    这里可以发现一些规律:

    若存在一条 xxuvu\to v,则 uu 所在的连通块(仅保留前 x1x-1 种边)连出的所有 22 边,一定在连向 vv 所在的连通块。

    入边同理。

    证明是简单的,按照我上述的过程进行构造即可,由于不是重点就不展开讲了。

    特殊地,我们从上述条件中可以看出,如果在连完一条 xx 边后,两个连通块合并,则两个连通块大小一定相等。

    但是,是否所有大小相等的连通块都可以进行连边合并呢?

    显然是不行的。

    image

    例如上图有 33 个连通块,每一个连通块大小都是相等的。

    但是 1,21,2 两个连通块不能合并,2,32,3 两个连通块也不能合并(可以自己试试)。

    唯一可以合并的是 1,31,3 两个连通块,这里画出了可能的一种合并方式。

    为了判断两个连通块能否合并,我们不妨自己进行这样一个定义:

    对于两个只存在编号为 1x1\sim x 的边的连通块 (V1,E1)(V_1,E_1)(V2,E2)(V_2,E_2),与点 uV1u\in V_1vV2v\in V_2

    若称这两个连通块关于 (u,v)(u,v)“同构”,当且仅当:

    1. V1=V2|V_1|=|V_2|E1=E2|E_1|=|E_2|
    2. 存在 V1V_1 的排列 p=(p1,p2,,pV1)p=(p_1,p_2,\dots,p_{|V_1|}) 使得 p1=up_1=u
    3. 存在 V2V_2 的排列 q=(q1,q2,,qV2)q=(q_1,q_2,\dots,q_{|V_2|}) 使得 q1=vq_1=v
    4. 对于任意节点 pi(1iV1)p_i(1\le i\le |V_1|),若从 pip_i 出发走 w(1wx)w(1\le w\le x) 边到达了点 pjp_j,则从 qiq_i 出发走 ww 边一定到达节点 qjq_j

    不知道这个名字起的怎么样,我觉得挺顺耳的。

    显然,按照我们的定义,有一些显然的结论,例如同构具有传递性。

    那么对于任意两个点 u,vu,v,若他们所在的连通块在连完一条 xxuvu\to v 后合法,当且仅当这两个连通块关于 (u,v)(u,v) 同构。

    这个比较简单,就不证了。

    比较重要的是下面这个结论:

    对于一个连通块 (V,E)(V,E) 与其中两点 u,vVu,v\in V,这个连通块与自己关于 (u,v)(u,v) 同构。

    这个也比较显然,归纳就可以证明。

    大题的思路是考虑若干个连通块,在连完一种边后合并在一起的过程。

    就可以利用同构的传递性,以及合并连通块需要同构,这两个性质进行证明。

    那么还可以推出:

    对于两个连通块 (V1,E1)(V_1,E_1)(V2,E2)(V_2,E_2),若他们关于 (u,v)(uV1,vV2)(u,v)(u\in V_1,v\in V_2) 同构。

    则对于任意两个点 uV1u'\in V_1vV2v'\in V_2,这两个连通块关于 (u,v)(u',v') 同构。

    这个也好证,结合上一个结论与传递性即可。

    从这个结论也可以看出,两个连通块同构,和我们选取的两个点 (u,v)(u,v) 并没有什么关系(其实选取也只是为了方便证明)。

    所以下文的同构,会将这两个点省略,直接说某两个连通块同构。

    这个结论是很有意思的,这告诉我们,对于两个同构的连通块。

    如果我们要从第一个连通块向第二个连通块连边,那么我们只需要确定任何一个点所指向的点,就能唯一确定一个合法方案。

    image

    dp 设计

    至此,我们就可以尝试进行做法的设计了。

    首先考虑输入的图。不难发现,若当前的两个连通块在连完了新的 kk 种边后合并了,则这两个连通块此时同构。

    显然,我们可以把所有的连通块分为若干类,其中每一类的所有连通块同构。

    那么每一类之间的答案是独立的,我们只需要把它们的答案分别算出,乘起来即可。

    而将连通块分类也是简单的,容易使用哈希在 O(n2+nm)O(n^2+nm) 复杂度内完成分类。

    现在我们只需要考虑所有连通块都同构的情况了。

    dpi,j,sdp_{i,j,s} 表示现在有 ii 个同构的连通块,每一个大小都是 ss,在连了 jj 种边后,所有点被连进一个连通块的方案数。

    所有点被连进一个连通块如果能算出来,那么最终的方案容易使用另一个 dp 算出。

    考虑这个状态如何转移。

    边界状态是简单的,显然有 dp1,0,s=1dp_{1,0,s}=1

    否则,我们枚举 xx,表示第一次连边之后,整张图剩下了 xx 个连通块,那么每一个连通块必然是由 ix\dfrac{i}{x} 个连通块拼起来的。

    那么有转移方程 $dp_{i,j,s}=\sum\limits_{x\mid i}dp_{x,j-1,\frac{is}{x}}f_{i,x}\times ?$。

    其中 fi,jf_{i,j} 表示将 ii 个连通块分为 jj 个大小相等的圆排列的方案数,容易使用 O(nlnn)O(n\ln n) 的 dp 算出。

    方程中的 ?? 表示连边的方案数,这个需要推一下。

    image

    容易发现,对于前 ix\dfrac{i}{x} 个连通块来说,他们组成的大连通块长什么样子是无所谓的,所以方案数是 sixs^{\frac{i}{x}}

    而对于后面的所有连通块,我们需要保证练成的样子与第一组同构,所以对于每一组的最后一个连通块,我们有唯一的连边限制。

    也就是说,后面所有的方案数是 s(x1)(ix1)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(n2klnn)O(n^2k\ln n) 的复杂度内完成转移。

    dp 显然是正确的,但是他的复杂度太高了。而且似乎有些怪怪的?

    似乎 ss 这一维自始至终都是没有任何用处的?

    考虑 dpi,j,sdp_{i,j,s} 中,ss 总共被乘了多少遍。

    容易发现,上边的 ix+1i-x+1 表示 当前连通块个数 减去 连完一条边的连通块个数 加上 11

    那么裂项相消之后不难想到:

    结论:dpi,j,s=dpi,j,1si+j1dp_{i,j,s}=dp_{i,j,1}s^{i+j-1}

    考虑归纳证明,对 j=0j=0 显然成立。

    假设对 j<pj<p 的情况成立,那么对于 j=pj=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(nklnn)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+n2+nklnn)O(nm+n^2+nk\ln n),可以拿到 6464 分。

    时间复杂度瓶颈在于最后这个 dp。

    dp 优化

    考场上写完这里就只剩 11 分钟了,直接加了个文件走人了。

    考虑先打表看看规律。

    首先可以来看 fi,j(ji)f_{i,j}(j\mid i),可以发现有 fi,j=i!j!(ij)jf_{i,j}=\dfrac{i!}{j!\left(\dfrac{i}{j}\right)^j}

    证明的话还是归纳,显然对 fi,1f_{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} $$

    有个阶乘,还有个指数,很烦,设 fpi,j=dpi,j(i1)!ij1fp_{i,j}=\dfrac{dp_{i,j}}{(i-1)!i^{j-1}}

    其中边界条件有一些变化,为 fpi,1=1fp_{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}$。

    而我们的目标是求出 fp1n,kfp_{1\sim n,k}

    考虑实际意义,fpi,jfp_{i,j} 实际上是在说:

    对于所有长度为 jj,满足 a1=1,ajia_1=1,a_j\mid i,且有 ai1aia_{i-1}\mid a_i 的序列 {aj}\{a_j\}

    定义他的权值是 i1ai\prod\limits_i \dfrac{1}{a_i},求所有合法序列的权值和。

    考虑 fpi,x+yfp_{i,x+y} 的值是多少。

    按照实际意义,我们枚举第 y+1y+1 项填了哪个数字。

    那么 $fp_{i,x+y}=\sum\limits_{j\mid i}\dfrac{fp_{j,x}fp_{i/j,y}}{j^y}$。

    这样我们就可以以一个类似快速幂的形式,求出所有 fp,kfp_{*,k} 的值。

    总时间复杂度是 O(n2+nm+nlnnlogk)O(n^2+nm+n\ln n\log k)。 写完力!

    信息

    ID
    1391
    时间
    2000ms
    内存
    512MiB
    难度
    (无)
    标签
    (无)
    递交数
    0
    已通过
    0
    上传者