题解：P4321 随机漫游

Aegleseeker_ · 2025-08-25 13:41:16 · 题解

考虑每个点被走到的时刻 t_i，答案为 E(\max t_i)。一手 min-max 容斥，转换为 E(\min\limits_{i\in U}t_i)。令 f_{u,s} 代表，从点 u 开始随机游走，走到 s 中任何一个点的期望时间。答案就是 \sum\limits_{U\subset S}-1^{|U|+1}f_{x,U}，可以将 f_{x,U} 乘上系数然后放进 sosdp 里跑出子集和，这样求答案就是 O(1) 的了。考虑如何求 f_{u,s}，首先显然有对于 u\in s,f_{u,s}=0，另一个朴素的转移是 f_{u,s}=1+\sum\limits_{(u,v)\in E}\frac{f_{v,s}}{\text{deg}_u}。可以对于每个 s 跑一遍高斯消元，总复杂度为 O(2^nn^3+qn)，可以通过通过本题。

submission：https://www.luogu.com.cn/record/232972449