随机游走
公式
算步数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)∈Edis(v)+1
树上随机游走，设x到fa_x的期望步数为f(x)=1deg(x)(wx,fax+∑v∈son(wx,v+f(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)∈Ep(v)
2542. 「PKUWC2018」随机游走
定一棵 n 个结点的树，你从点 x 出发，每次等概率随机选择一条与所在点相邻的边走过去。
有 Q 次询问，每次询问给定一个集合 S，求如果从 x 出发一直随机游走，直到点集 S 中所有点都至少经过一次的话，期望游走几步。
特别地，点 x（即起点）视为一开始就被经过了一次。
答案对 998244353 取模。
1≤n≤18，1≤Q≤5000，1≤k≤n1\leq n\leq 18，1\leq Q\leq 5000，1\leq k\leq n1≤n≤18，1≤Q≤5000，1≤k≤n
树上dp，
#3675. 「北大集训 2021」随机游走
给定一张 n 个点的有向图，点标号为 1,2,\dots,n，初始时对 \forall i\in{1,2,\dots,n-1}，从 i 到 i+1 有一条有向边。
你可以在其中再加入 m 条有向边（起点终点任意），允许有重边和自环。
小 A 会从 1 出发，以随机游走的形式行动，直到抵达 n。你希望最大化小 A 从 1 移动到 n 的期望步数。
定义随机游走是这样的一种移动方式：设小 A 当前在点 x，x 有 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，有Fi=MFi−1F_i=MF_{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≤iFj的最短递推式的最短递推式长度也不超过 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≤1e5
ARC 185 Random Walk on Tree
树有n∗m+1n*m+1n∗m+1个点，树的构造为，先构造m条n个点的链，把所有链的一端和根节点相连。树上随机游走，问，多久经过每个点至少一次。
链上随机游走，从1端走到另一端的期望步数d(i)=i2d(i)=i^2d(i)=i2，iii为链的长度
一个n面骰子，每面出现概率相同，让每面都出现至少一次，期望为n/1+n/2+⋯+n/nn/1+n/2+\cdots+n/nn/1+n/2+⋯+n/n。
答案为m2∗(n/1+n/2+⋯+(n−1)/n)∗2+m2∗nm^2*(n/1+n/2+\cdots+(n-1)/n)*2+m^2*nm2∗(n/1+n/2+⋯+(n−1)/n)∗2+m2∗n
