题目
点这里看题目。
给定一棵 \(n\) 个结点的树。
进行如下过程：
-
初始时，所有结点都是白色，且计数器变量 \(c=0\)。
-
重复一下两个步骤：
-
如果所有结点都是黑色，停止该过程。
-
从所有不“好”的结点中，随机选择一个，将它染成黑色，并令 \(c\) 为 \(c+1\)。
-
一个结点为“好”的，当且仅当它和它的所有祖先都是黑色。
求过程结束时的 \(E[c] \bmod 998244353\)。
所有数据满足 \(1\le n\le 2\times 10^5\)（原版）或 \(1\le n\le 10^7\)（加强版）。
分析
有一个看起来很合理，但是貌似又不太合理的转化：
对于 \(u\in V\)，设随机变量 \(X_u\) 为 \(u\) 在随机过程中，被选中并染成黑色的次数。
因为 \(c=\sum_u X_u\)，所以 \(E[c]=\sum_u E[X_u]\)。
不用担心，这个推理过程完全完全正确。问题是，如何才能正确地计算 \(E[X_u]\)？
可以使用全期望公式吗？比如枚举一种黑色状态，计算这种状态下 \(u\) 被选中的概率？那么这种算法怎么处理“黑色状态没有改变，\(u\) 却被多次选中”的情况？
我们捋一下“随机过程”这个概念。在本题中，随机过程可以看作是一个概率空间列 \(\{(\Omega_k,\mathscr F_k,P_k)\}_{k\ge 0}\)，其中 \(\Omega_k=V^k,\mathscr F_k=2^{\Omega_k}\)。
概率测度怎么定义？首先，\(P_0[()]\) 显然应当是成立的。此后，我们当然可以按照题意，直接递推出每一个 \(P_k\)。然而，为了后续叙述不绕弯，我们此处认为 \(P_k(\omega)=n^{-k},\omega\in \Omega_k\)。
Note.
这其实就是一个经典的转化：允许“好”的结点被选中并继续被染黑，这样原先一个过程可能被插入若干个冗余“好”的结点。
相应地，新序列的概率和原先概率计算方式不同。所以在这样的变化之后原先某一个过程的概率不发生改变。具体可以自行计算验证。
进一步地，一个随机过程，其实就是一个序列列 \(\mathscr S=\{S_k\}_{k=0}^m\)，满足：
-
对于 \(0\le k\le m,S_k\in \Omega_k\)。
-
对于 \(0\le k<m\)，存在 \(u\in V\)，\(u\) 在 \(S_k\) 中从未出现过。而 \(S_m\) 恰好包含所有结点。
-
对于 \(0<k\le m\)，\(S_{k-1}\) 为 \(S_k\) 的长度为 \(k-1\) 的前缀（长度为 \(0\) 的前缀即为空序列）
不过，此时的随机变量似乎就不能叫做“随机变量”了。在解题中这不是一个特别重要的点，我们仍然沿用 \(X_u\) 的记号，不过一个 \(\mathscr S\) 对应的 \(X_u\) 为 \(\sum_{k=0}^m[S_k[k]=u]\)。
回头考察 \(E[X_u]\)，那就是 \(\sum_{k=0}^mP(S_k[k]=u)\)。我们要计算的就是，在任何一个合法的过程“前缀”下，\(u\) 被选中概率之和。
结合题意，我们发现 \(\sum_{k=0}^mP(S_k[k]=u)\) 可以很简单地讨论出来：如果 \(u\) 要被选中，则要么 \(u\) 的父亲还不是“好”的结点，要么 \(u\) 的父亲已经是好的结点，且 \(u\) 在前缀中还没有出现过。
要求某个结点是“好”的结点或反之都可以容斥计算。设 \(u\) 的父亲的深度为 \(d\)，我们于是有：
\[\begin{aligned} P_1&=\sum_{k=1}^d(-1)^{k-1}\binom{d}{k}\sum_{j\ge 0}\left(\frac{n-k}{n}\right)^j\\ P_2&=\sum_{k=0}^d(-1)^k\binom{d}{k}\sum_{j\ge 0}\left(\frac{n-k-1}{n}\right)^j \end{aligned} \]首先，用等比数列求和将 \(\sum_j\) 这层和式收起来：
\[\begin{aligned} P_1&=\sum_{k=1}^d(-1)^{k-1}\binom{d}{k}\frac{n}{k}\\ P_2&=\sum_{k=0}^d(-1)^k\binom{d}{k}\frac{n}{k+1} \end{aligned} \]注意到 \(\frac{1}{k+1}=\left.(\mathrm{E}^kx^{\underline{-1}})\right|_{x=0}\)，我们可以先用高阶差分将第二项收起来：
\[\begin{aligned} P_2 &=(-1)^dn\left.\left(\Delta^dx^{\underline {-1}}\right)\right|_{x=0}\\ &=\frac{nd!}{(d+1)!}\\ &=\frac{n}{d+1} \end{aligned} \]不幸的是，\(P_1\) 的和式不能手动补齐 \(k=0\) 的项，因为会出现 \(\frac{n}{0}\) 而直接 GG。不过，我们可以直接手算前面若干项，可以发现有 \(1,\frac{3}{2},\frac{3}{2}+\frac{1}{3}\) 的规律，这让我们想起了调和级数。也就是说，我们可以猜测：
\[P_1=nH_d \]猜到了结论，证明可以直接归纳法。如果不喜欢猜结论，为了让 \(k\) 可以被吸收进组合数里，我们也可以使用 \(\binom{d}{k}=\sum_{r=k-1}^{d-1}\binom{r}{k-1}\) 来降下指标，而这就是最终结果是一个级数而非单项的原因！
Remark.
如果引入 \(\frac{1}{0}\)，我们可以附加变量 \(x\)，并计算 \(x\rightarrow -1\) 的极限。理论上来说可以使用洛必达，然而我技术不过关算不出来
标签：结点,frac,int,Removing,sum,ARC150D,inline,Gacha,mod From： https://www.cnblogs.com/crashed/p/16793148.html