AT_abc253_h [ABC253Ex] We Love Forest

题目描述

有一个包含 $N$ 个顶点、$0$ 条边的图 $G$，顶点编号为 $1$ 到 $N$。另外，给定长度为 $M$ 的数列 $u=(u_1,u_2,\ldots,u_M)$ 和 $v=(v_1,v_2,\ldots,v_M)$。

你需要进行 $N-1$ 次如下操作：

• 每次操作中，等概率地随机选择一个 $i$（$1 \leq i \leq M$），并在 $G$ 中添加一条连接顶点 $u_i$ 和顶点 $v_i$ 的无向边。

注意，即使 $G$ 中已经存在一条连接 $u_i$ 和 $v_i$ 的边，也要再添加一条新的边。也就是说，操作结束后，$G$ 可能包含重边。

对于 $K=1,2,\ldots,N-1$，请你求出经过 $K$ 次操作后，$G$ 仍然是森林的概率，并对 $998244353$ 取模。

森林的定义：不包含环的无向图称为森林。森林可以是不连通的。

概率的 $\bmod\ 998244353$ 的定义：本题中要求的概率一定是有理数。在本题的约束下，设概率为最简分数 $\frac{y}{x}$，保证 $x$ 不会被 $998244353$ 整除。

此时，存在唯一的 $0$ 到 $998244352$ 之间的整数 $z$，满足 $xz \equiv y \pmod{998244353}$。请输出这个 $z$。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$
$u_1$ $v_1$
$\vdots$
$u_M$ $v_M$

输出格式

输出 $N-1$ 行。第 $i$ 行输出经过 $i$ 次操作后，$G$ 仍然是森林的概率，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

3 2
1 2
2 3

输出 #1

1
499122177

输入输出样例 #2

输入 #2

4 5
1 2
1 2
1 4
2 3
2 4

输出 #2

1
758665709
918384805

说明/提示

约束

• $2 \leq N \leq 14$
• $N-1 \leq M \leq 500$
• $1 \leq u_i, v_i \leq N$
• $u_i \neq v_i$
• 所有输入均为整数

样例解释 1

用 $(u,v)$ 表示一条连接顶点 $u$ 和顶点 $v$ 的边。进行 $1$ 次操作后，$G$ 可能如下：

• 以 $1/2$ 的概率，存在边 $(1,2)$。
• 以 $1/2$ 的概率，存在边 $(2,3)$。

无论哪种情况，$G$ 都是森林，因此 $K=1$ 时的答案是 $1$。

进行 $2$ 次操作后，$G$ 可能如下：

• 以 $1/4$ 的概率，存在边 $(1,2),(1,2)$。
• 以 $1/4$ 的概率，存在边 $(2,3),(2,3)$。
• 以 $1/2$ 的概率，存在边 $(1,2),(2,3)$。

只有存在边 $(1,2),(2,3)$ 时，$G$ 是森林。因此，所求概率为 $1/2$，对 $998244353$ 取模后输出 $499122177$。

由 ChatGPT 4.1 翻译