自动搬运

查看原文

来自洛谷，原作者为

	LCuter 金牌打包盒生产有限公司 CEO

搬运于2025-08-24 22:21:31，当前版本为作者最后更新于2020-05-03 18:14:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

F - Quark and Graph

$\text{Description}$

现有一 $n$ 个点 $m$ 条边的有标号简单无向连通图，边权全为 $1$。

已知 $1$ 节点到所有节点的最短路长，求这张图有多少种可能的形态，答案对 $998244353$ 取模。

两张图 $G=(V,E)$ 和 $G'=(V',E')$ 形态不同当且仅当存在一个二元组 $(u,v)$ 满足 $u,v\in[1,n]\cap N_+,(u,v)\in E,(u,v)\notin E'$。

$\text{Solution}$

按照最短路长分层（最短路长即层数），记 $1$ 到 $x$ 的最短路长为 $d_x$，定义 $t_i,T$：

$$t_i=\displaystyle\sum_{j=1}^n[d_j=i],T=\max\limits_{t_i>0}\{i\} $$

我们称相邻两层之间的边为树边，同层之间的边为非树边，定义 $f_i,f^\ast_i$ 分别表示树边取 $i$ 条的方案数，非树边取 $i$ 条的方案数，那么最后答案为：

$$Ans=\displaystyle\sum_{i+j=m}f_i\cdot f^\ast_j$$

上式是一个卷积的形式，我们可以分别求出 $f_i,f^\ast_i$，然后再卷起来。

先考虑 $f_i$。发现最后答案是第 $1$ 层到第 $T$ 层与其上一层之间的答案的卷积。所以我们分别考虑每一层。我们将每一层与其上一层之间的边按照当前层的点分为 $t_i$ 个部分，第 $i$ 个部分包含的是其中一个端点为 $i$ 节点的边。那么每一层与其上一层的答案又是其每个部分的答案的卷积。每个部分的生成函数根据二项式定理可以得到是：

$$K(x)=(1+x)^{t_{i-1}}-1$$

进一步地，每一层的答案实际上是：

$K^{\ast}(x)=[(1+x)^{t_{i-1}}-1]^{t_i}$

那么树边的生成函数实际上就是：

$F(x)=\displaystyle \prod\limits_{i=1}^T[(1+x)^{t_{i-1}}-1]^{t_{i}}$

PS：做到这一步时，我们把每一层的生成函数处理出来，然后用类似合并果子的方法，每次取出次数最低的两个多项式相乘，在本题的限制下可以做到 $O(n\log^2 n)$，做法来自 EA。

为了方便处理，我们定义 $G(x)$：

$$G(x)=F(x-1)=\displaystyle\prod\limits_{i=1}^T[x^{t_{i-1}}-1]^{t_{i}} $$

右边是乘积，不好搞，对它取 $\ln$ 后再做 $\exp$：

$$G(x)=\displaystyle\exp\ln \prod_{i=1}^T[x^{t_{i-1}}-1]^{t_{i}} $$

然后常规地乘化加，幂化乘：

$$G(x)=\displaystyle\exp[\sum_{i=1}^Tt_i\ln(x^{t_{i-1}}-1) ] $$

然后需要把 $\ln$ 化成我们想要的形式：

$$G(x)=\displaystyle\exp\{\sum_{i=1}^Tt_i[\ln(-1)-\ln(\frac{1}{1-x^{t_{i-1}}})] \} $$

发现前半部分可以拆出来：

$$G(x)=\displaystyle\frac{(-1)^{\sum\limits_{i=1}^Tt_i}}{\exp[\sum\limits_{i=1}^Tt_i\cdot\ln(\frac{1}{1-x^{t_{i-1}}})]} $$

我们定义 $H(x)$：

$$H(x)=\displaystyle\sum\limits_{i=1}^Tt_i\cdot\ln(\frac{1}{1-x^{t_{i-1}}}) $$

然后对 $\ln$ 来一波泰勒展开：

$$H(x)=\displaystyle\sum\limits_{i=1}^Tt_i\cdot\sum\limits_{j=1}^{+\infty}\frac{x^{jt_{i-1}}}{j} $$

记 $c_k=\displaystyle\sum\limits_{i=1}^Tt_i[t_{i-1}=k]$

枚举 $k$，合并一下同类项：

$$H(x)=\displaystyle\sum_{k=1}^nc_k\sum\limits_{j=1}^{+\infty}\frac{x^{jk}}{j} $$

由于我们实际要求的：

$$G(x)=\displaystyle\frac{(-1)^{n-1}}{\exp H(x)}$$

记树边总数为 $s$，我们要求出 $G$ 的前 $s+1$ 项，因为高次项可以通过二项式定理贡献到低次项。

那么怎么通过 $G(x)=F(x-1)$ 求得 $F(x)$ 呢？

注意到 $G(x+ 1)=F(x)$，我们展开按照 CF923E 的做法即可。

---

现在来考虑非树边的生成函数 $F^\ast(x)$。

先求非树边总数：

$S=\displaystyle\sum_{i=1}^T\frac{t_i(t_{i}-1)}{2}$

那么生成函数应该是：

$$F^\ast(x)=\displaystyle\sum_{i=0}^{+\infty}{S\choose i}x^i $$

由于我们是在模 $P=998244353$ 意义下进行运算，所以当 $S>P$ 时会有些奇怪的问题。进一步分析，发现当 $i>S\bmod{P}$ 时系数都为 $0$。这是因为将组合数拆开后，$(S-i)!$ 没能把 $S!$ 的质因子中的 $P$ 全部消去。故我们只需计算：

$$F^\ast(x)=\displaystyle\sum_{i=0}^{\min(m,S\bmod{P})}{S\choose i}x^i $$

我们观察组合数公式：

$$\displaystyle{n\choose m}=\frac{n!}{m!(n-m)!}$$

在式子中，$m$ 的阶乘由于其比较小，我们在上面预处理时已经求过了，所以重点观察另两个阶乘。

注意到我们要求的实际上是：

$$S^{\underline{k}},(0\le k\le S\bmod{P})$$

在求值的时候动态维护一个后缀积即可。

最后复杂度实际上和树边总数有关（一个 log），那个奇怪的限制实际上是对树边总数一个粗略的估计。