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$：
我们称相邻两层之间的边为树边，同层之间的边为非树边，定义 $f_i,f^\ast_i$ 分别表示树边取 $i$ 条的方案数，非树边取 $i$ 条的方案数，那么最后答案为：
上式是一个卷积的形式，我们可以分别求出 $f_i,f^\ast_i $，然后再卷起来。
先考虑 $f_i$。发现最后答案是第 $1$ 层到第 $T$ 层与其上一层之间的答案的卷积。所以我们分别考虑每一层。我们将每一层与其上一层之间的边按照当前层的点分为 $t_i$ 个部分，第 $i$ 个部分包含的是其中一个端点为 $i$ 节点的边。那么每一层与其上一层的答案又是其每个部分的答案的卷积。每个部分的生成函数根据二项式定理可以得到是：
进一步地，每一层的答案实际上是：
$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)$：
右边是乘积，不好搞，对它取 $\ln$ 后再做 $\exp$：
然后常规地乘化加，幂化乘：
然后需要把 $\ln $ 化成我们想要的形式：
发现前半部分可以拆出来：
我们定义 $H(x)$：
然后对 $\ln$ 来一波泰勒展开：
记 $c_k=\displaystyle\sum\limits_{i=1}^Tt_i[t_{i-1}=k]$
枚举 $k$，合并一下同类项：
由于我们实际要求的：
记树边总数为 $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}$
那么生成函数应该是：
由于我们是在模 $P=998244353$ 意义下进行运算，所以当 $S>P$ 时会有些奇怪的问题。进一步分析，发现当 $i>S\bmod{P}$ 时系数都为 $0$。这是因为将组合数拆开后，$(S-i)!$ 没能把 $S!$ 的质因子中的 $P$ 全部消去。故我们只需计算：
我们观察组合数公式：
在式子中，$m$ 的阶乘由于其比较小，我们在上面预处理时已经求过了，所以重点观察另两个阶乘。
注意到我们要求的实际上是：
在求值的时候动态维护一个后缀积即可。
最后复杂度实际上和树边总数有关（一个 log），那个奇怪的限制实际上是对树边总数一个粗略的估计。