[QkOI#R1] Quark and Graph 官方题解

· · 题解

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），那个奇怪的限制实际上是对树边总数一个粗略的估计。