https://loj.ac/p/2542

给定一棵 n 个结点的树,你从点 x 出发,每次等概率随机选择一条与所在点相邻的边走过去。

Q 次询问,每次询问给定一个集合 S,求如果从 x 出发一直随机游走,直到点集 S 中所有点都至少经过一次的话,期望游走几步。

特别地,点 x(即起点)视为一开始就被经过了一次。

答案对 998244353 取模。

Solution :

目标为全集S的期望,由\min-\max容斥转化为到达至少一个节点x,x\in S所需要的期望步数

f_u 是从u出发走到集合S中至少一个点的期望步数,可以得到环状转移

f_u=\frac{1}{{\rm deg}_u}(f_{fa_u}+\sum_{v\in {\rm son}(u)}f_v)+1

考虑边界情况

  1. 对于在起点x处,没有父亲,那么仅仅跟所有儿子v相关
  2. 对于在叶子v处,没有儿子,那么仅仅跟父亲f_u相关。此时f_u可以被表征为以f_v为自变量的一次函数,或者反过来说f_v=a_vf_u+b_v

因为叶子能够按上述方式表征父亲,因为环状转移的形式不变,所以迭代后依然具有正确性,对于任意非根节点都可以表征它们的父亲。

我们尝试用已知量来表示一下f_u=a_uf_{fa_u}+b_u

f_v带入转移得到f_u的转移,整理后可以得到

f_u=\frac{1}{\deg_u - \sum_v a_v}f_{fa_u}+\frac{\deg_u + \sum_v b_v}{\deg_u-\sum_v a_v}

那么就分别得到了由与v,v\in{\rm son}(u)相关的变量表征的a_u,b_u

因为是q次询问,并且容斥之后容斥系数和|S|无关,仅仅与子集大小|T|相关,为(-1)^{|T|-1},那么可以对于每一个S预处理出子集和乘上对应的系数。可以\rm FWT or或者高维前缀和实现

\rm dp复杂度O(n2^n\log n),带了一个求逆的\log,预处理O(n2^n),回答O(1),总复杂度O(n2^n\log n)

当然其实不做预处理直接暴力回答询问O(q2^n)也能过,卡一卡甚至O(n^32^n)高消也能过

Min-Max容斥 FWT 前缀和 概率期望

2022.9.20补
上一篇 «
2022.9.16补
» 下一篇
© 2017 - 2024 云雀.
...... visits · ...... visitors