[题解] [Mivik Round nurture] Look At The Sky 加强版

记一张无向图的连通块集合 $f(G)$ 为这张图所有极大连通块的大小形成的任意顺序的序列，要求对所有 $k\in [0,K]$ 求：

$$ \sum_{G\in S(n)}\frac{\sum_{i=1}^{|f(G)|}{f(G)_i^k}}{\left(\sum_{i=1}^{|f(G)|}f(G)_i\right)^k} $$

$S(n)$ 为所有大小为 $n$ 的无向图形成的集合。答案对 $998244353$ 取模。

$1\le n,K\le 2\cdot 10^5$

题目链接

---

思路

Subtask 1

显然输出 $(K+1)$ 行 1 即可。

Subtask 2

发现答案就是 $\frac{1^k+1^k}{2^k}+\frac{2^k}{2^k}=2^{1-k}+1$，直接计算即可。

Subtask 3

观察到分母恒为 $n^k$，那么就变成了问所有 $n$ 个点的无向图的连通块大小的 $k$ 次方之和。这个是很显然的。首先我们设 $n$ 个点无向图的个数的 EGF 为 $H(x)$，显然有：

$$ H(x)=\sum_{i=0}^\infty\frac{2^\binom i2}{i!}x^i $$

设 $n$ 个点无向连通图的个数的 EGF 为 $G(x)$。由于无向图是由多个无向连通图形成的连通块组合形成的，那么根据 EGF 的组合意义我们得到：

$$ \begin{aligned} H(x)&=\sum_{i=0}^\infty \frac{G^i(x)}{i!}\\ &=e^{G(x)} \end{aligned} $$

于是有 $G(x)=\ln H(x)$。然后我们来考虑答案。对于一个 $k$ 来讲，我们枚举连通块的大小及其贡献，得到：

$$ ans_k=\frac1{n^k}\sum_{i=1}^ni^k\binom niG_iH_{n-i} $$

我们设 $\binom niG_i H_{n-i}$ 为 $F_i$，然后考虑 $ans$ 的 OGF $Ans$，显然有：
$$
Ans=\sum_{i=1}^n\frac{F_i}{1-ix}
$$
可以分子分母拆开分治 FFT 求解。

代码

mivik.h

代码