In this article, we study the expected subword complexity of random words and some of its properties.

本篇文章研究了随机字符串期望的本质不同子串个数及其相关的性质。

记一张无向图的连通块集合 $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$

记一张无向图的连通块集合 $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$

对于所有 $1\le i\le n$ 求出 $i$ 个点的有哈密顿回路的竞赛图的哈密顿回路数量的期望。

$1\le n\le 100000$

给定 $n$ 和 长度为 $n+1$ 的数组 $a_0\cdots a_n$，求

$$
\sum_{k=0}^n a_k\sum_{i=0}^x i^k
$$

的各项系数（共 $n+2$ 项）。$1\le n\le 250000$，答案对 $998244353$ 取模。

求长度为 $n$、字符集大小为 $m$ 的随机字符串的期望本质不同子串个数。

$1\le n\le 20$，$1\le m\le 5\cdot 10^6$

给定 $n$、$m$ 和字符串 $S$，问长度为 $n$、字符集大小为 $m$ 的随机字符串中包含 $S$ 作为子串的概率。答案对 $998244353$ 取模。

$1\le |S|\le n\le 10^5$，$1\le m\le 10^8$