YbtOJ 735「动态树」毒瘤染色
题目链接：YbtOJ #735
对于一个无向图，若图中的每条边 至多处于一个无向环中，则称这个图为一个 毒瘤图。
小 A 有一个图 $G$，初始包含 $n$ 个点，没有边。显然它是一个毒瘤图。
接下来小 A 会进行 $q$ 次操作，每次操作给出两个正整数 $x,y$，要求判断往 $G$ 中加入 $(x,y)$ 后该图是否仍然是毒瘤图，若是则加入这条边，否则不加入。
在所有操作进行前，小 A 会确定一个非负整数 $k$。在每次操作后，小 A 都会针对当前图进行询问：假设初始所有点为白色，进行 $k$ 次染色，每次等概率随机选择一个点将它染成黑色（一个点可能被重复选择多次），求 $k$ 次染色后图中 仅保留白点时的连通块个数+仅保留黑点时的连通块个数 的 期望值（向 $998244353$ 取模）。
为了让你有更多的得分空间，小 A 还会给定一个辅助变量 $\omega$。若 $\omega=1$，你需要回答上述询问。若 $\omega=0$，对于每次询问你只需要求出 仅保留白点时的连通块个数 的 期望值。
因为一些奇怪的原因，本题 强制在线。
$1\le n\le10^5$，$1\le q\le 3\times10^5$，$0\le k\le 10^9$。
Solution
在仙人掌中，连通块个数=点数-边数+环数
由于期望的线性性，E(连通块个数)=E(点数)-E(边数)+E(环数)
所以将权值为 $0$ 的点与 $1$ 的点分开求期望即可。
下面不妨称权值为 $0$ 为白点，$1$ 为黑点。
点
一个点为白点概率为 $(\frac{n-1}n)^k$。
一个点为黑点概率为 $1-(\frac{n-1}n)^k$。
边
一条边为白边的概率为 $(\frac{n-2}n)^k$。
一条边为黑边的概率为 $1-Pr(x \text{为白点})-Pr(y \text{为白点})+Pr(x \text{为白点且}y\text{为白点})=1-2(\frac{n-1}n)^k+(\frac{n-2}n)^k$。
环
一个大小为 $m$ 的白环的概率为 $(\frac{n-m}n)^k$。
一个大小为 $m$ 的黑环的概率有两种做法：
法一：分治 NTT
设 $f_i$ 表示大小为 $i$ 的环在 $k$ 次操作后全黑的概率，$g_i$ 表示包含 $i$ 个点的集合在 $k$ 次操作后全白的概率。
显然有 $g_i=(\frac{n-i}n)^k$。
$$
f_i=1-Pr(\text{不是全黑})=1-\sum_{j=0}^{i-1}f_jg_{i-j}\binom ij
$$
直接分治 NTT 就可以 $O(n\log^2n)$ 求出 $f_i$。
法二：容斥
$$
f_m=\sum_{i=0}^m(-1)^i\binom mi(\frac{n-i}n)^k
$$
其中 $i$ 枚举的是环中至少有 $i$ 个白点，由于所有环只算一次，于是这部分复杂度为 $O(\sum m\log k)=O(n\log k)$。
Code
1 |
|