[题解] [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\le 2\cdot 10^5$，$0\le K\le 5000$

题目链接

---

思路

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} $$

我们设 $G_i H_{n-i}$ 为 $F_i$，那么有：

$$ \begin{aligned} ans_k&=\frac1{n^k}\sum_{i=1}^ni^k\binom niF_i\\ &=\frac{n!}{n^k}\sum_{i=1}^n\frac{F_i}{i!(n-i)!}i^k\\ &=\frac{n!}{n^k}\sum_{i=1}^n\frac{F_i}{i!(n-i)!}\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}i^{\underline{j}}\\ &=\frac{n!}{n^k}\sum_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}\sum_{i=j}^n\frac{F_i}{(n-i)!(i-j)!} \end{aligned} $$

后面那个东西下标反转后很明显可以卷积，那么就 $O(n\log n+k^2)$ 解决了。

此外这道题实际上可以做 $1\le K\le 2\cdot 10^5$。这里是 加强版 和 题解。

代码

mivik.h

代码