随机游走算法

随机游走公式算步数dis(u)1deg(u)∑v,(v,u)∈Edis(v)1dis(u)\frac 1 {deg(u)} \sum_{v,(v,u)\in E} dis(v)1dis(u)deg(u)1​∑v,(v,u)∈E​dis(v)1树上随机游走设x到fa_x的期望步数为f(x)1deg(x)(wx,fax∑v∈son(wx,vf(v)f(x)))∑e(x,y)wx,y∑v∈sonf(v)f(x)\frac 1 {deg(x)} (w_{x,fa_x}\sum_{v \in son}{(w_{x,v}f(v)f(x)}))\sum_{e(x,y)} w_{x,y} \sum_{v \in son}f(v)f(x)deg(x)1​(wx,fax​​v∈son∑​(wx,v​f(v)f(x)))e(x,y)∑​wx,y​v∈son∑​f(v)无限随机游走p(u)1deg(u)∑v,(v,u)∈Ep(v)p(u)\frac 1 {deg(u)} \sum_{v,(v,u)\in E} p(v)p(u)deg(u)1​∑v,(v,u)∈E​p(v)2542. 「PKUWC2018」随机游走定一棵 n 个结点的树你从点 x 出发每次等概率随机选择一条与所在点相邻的边走过去。有 Q 次询问每次询问给定一个集合 S求如果从 x 出发一直随机游走直到点集 S 中所有点都至少经过一次的话期望游走几步。特别地点 x即起点视为一开始就被经过了一次。答案对 998244353 取模。1≤n≤181≤Q≤50001≤k≤n1\leq n\leq 181\leq Q\leq 50001\leq k\leq n1≤n≤181≤Q≤50001≤k≤n树上dp#3675. 「北大集训 2021」随机游走给定一张 n 个点的有向图点标号为 1,2,\dots,n初始时对 \forall i\in{1,2,\dots,n-1}从 i 到 i1 有一条有向边。你可以在其中再加入 m 条有向边起点终点任意允许有重边和自环。小 A 会从 1 出发以随机游走的形式行动直到抵达 n。你希望最大化小 A 从 1 移动到 n 的期望步数。定义随机游走是这样的一种移动方式设小 A 当前在点 xx 有 d 条出边则小 A 会从这 d 条出边中等概率随机选择一条走过去。可以通过打表观察规律dp公式代入算EX(1)CF 963E Circles of Waiting网格随机游走主元法Expected Value简单无向图随机游走起点和终点给出求期望时间。暴力解方程O(n2)O(n^2)O(n2)考虑对于一个点s表示走了 i 步当前停留在 j且没有走到过 n 的概率fi,jf_{i,j}fi,j​有FiMFi−1F_iMF_{i-1}Fi​MFi−1​Berlekamp–Massey算法在O(n2)O(n^2)O(n2)的时间内求解出Fi和∑j≤iFjF_i和\sum_{j\le i} F_jFi​和∑j≤i​Fj​的最短递推式的最短递推式长度也不超过 n.一个 k 阶线性递推序列 a 的生成函数A(x)A0(x)A(x)C(x)A(x)A_0(x)A(x)C(x)A(x)A0​(x)A(x)C(x)答案为A(1)A(1)A(1)可以通过A0(1),C(1)A_0(1),C(1)A0​(1),C(1)的值算出。A Boring Problem树上随机游走每次询问给出树上任意2个节点u,vu,vu,v的期望边数。Random Walk On Tree树上随机游走f(u,v)f(u,v)f(u,v)u到v的期望边数的平方每次询问给出树上任意2个子树求子树上的节点u,vu,vu,v的f(u,v)f(u,v)f(u,v)的和。n,q≤1e5n,q\le1e5n,q≤1e5ARC 185 Random Walk on Tree树有n∗m1n*m1n∗m1个点树的构造为先构造m条n个点的链把所有链的一端和根节点相连。树上随机游走问多久经过每个点至少一次。链上随机游走从1端走到另一端的期望步数d(i)i2d(i)i^2d(i)i2iii为链的长度一个n面骰子每面出现概率相同让每面都出现至少一次期望为n/1n/2⋯n/nn/1n/2\cdotsn/nn/1n/2⋯n/n。答案为m2∗(n/1n/2⋯(n−1)/n)∗2m2∗nm^2*(n/1n/2\cdots(n-1)/n)*2m^2*nm2∗(n/1n/2⋯(n−1)/n)∗2m2∗n