-
求期望，于是逆推。
设 (f[i]) 表示 (i) 节点到终点的距离，则：
[f[i]=sum_{(i,j)in E}{frac{f[j] imes w_{i,j}}{out_i}} ]拓扑后逆序求即可。
-
[x] HNOI2013 游走
由于是无向图，可以走回头路，所以不能简单地拓扑排序。
考虑利用期望的线性性，即每一条边的期望经过次数，乘上它的边权即为总 的期望距离。现在希望总距离最短，所以我们要让期望经过次数最多的边边权最小。
但是边的期望经过次数是不好直接计算的，我们可以先求出每一个点的期望经过次数，那么边的期望经过次数即为两端的点期望经过次数 (/) 各自的出度。
设 (f[i]) 表示 (i) 节点的期望经过次数，那么：
[f[i]=egin{cases} sum_{(i,j)in E}{frac{f[j]}{out_i}} +1 &i=1 \ sum_{(i,j)in E}frac{f[j]}{out_i} &i e1 end{cases} ]因为只要到达了 (n) 就会停止游走，所以不计算 (n) 点的贡献，那么我们就会得到 (n-1) 个方程，而又恰好有 (n-1) 个未知数 (f)。于是可以通过高斯消元来求得 (f)。
求出 (f) 后计算边的期望经过次数，排序即可。
-
[x] Luogu P4550收集邮票
从期望的定义考虑，设 (X) 表示收集了 (X) 张邮票，则
[egin{split} E(X)&=sum_{i}{frac{i(i+1)}{2}cdot P(Y=i)} \ &=frac{sum_{i}{icdot P(Y=i)}+sum_{i}{i^2cdot P(Y=i)}}{2} \ &=frac{E(Y)cdot E^2(Y)}{2} end{split} ]设 (f[i]) 表示已经有 (i) 张邮票，到有 (n) 张的期望次数，(g[i]) 表示已经有 (i) 张邮票，到
有 (n) 张的期望次数。列出转移方程：
[egin{split} f[i]&=frac{i}{n}(f[i]+1)+frac{n-i}{n}(f[i+1]+1) \&=f[i+1]+frac{n}{n-i} end{split} \ egin{split} g[i]&=frac{i}{n}(g[i]+2f[i]+1)+frac{n-i}{n}(g[i+1]+2f[i+1]+1) \&=g[i+1]+2f[i+1]+1+frac{i}{n-i}(2f[i]+1) end{split} ]递推出答案即可。
-
[x] Luogu P3802小魔女帕琪
从最简单的开始思考：
如果要前 (7) 个就触发魔法：设 (N=sum_{i=1}^{n}{a_i})。因为每选一个，样本总量就会减少一个，那么前 (7) 个出发魔法概率为：
[7!prod_{i=1}^{7}{frac{a_i}{N-i+1}} ]如果前 (8) 个触发魔法，即第一个随机选，剩下的再排一遍，概率为：
[sum_{i=1}^{7}{frac{a_i}{N}cdot7!prod_{j=1}^{7}{frac{a_j}{N-j+1}}} ]不难发现，后半部分跟上面是一样的，前半部分的和为 (1)，也就是说，选前 (8) 个触发魔法的概率等于选前 (7) 个，同理，任意结束位置大于等于 (7) 的连续数字触发魔法的概率是一样的，那么答案就是：
[(N-6)cdot7!prod_{i=1}^{7}{frac{a_i}{N-i+1}} ] -
[x] Luogu P2634聪聪可可
假概率题。
点分治 ，再计算点到重心距离时模上 (3)，统计答案时即为 (t[0]^2+2t[1]t[2])。其中， (t[x]) 表示到重心距离模 (3) 为 (x) 的点数量。
-
[x] HNOI2015 亚瑟王
这题难在设状态，如果DP每一轮各张牌的概率就会有后效性，所以本题任需要从期望的线性性入手。
设 (P[i]) 表示 (r) 轮中 (i) 号牌发动的概率，那么答案显然为 (sum_{i}{P[i]cdot d[i]})。
于是问题转化为求 (P[i])。
因为需要满足”使用了当前卡就停止本局“，所以状态要与前缀有关，设 (f[i][j]) 表示在 (r) 轮中前 (i) 张牌发动了 (j) 张的概率，那么：
- 若第 (i) 张牌不发动：可以由 (f[i-1][j]) 转移，同时 (i) 在剩下的 (r-j) 轮中都不能使用，所以 (f[i][j]+=f[i-1][j] imes (1-p_i)^{r-i})。
- 若第 (i) 张牌发动：可以由 (f[i-1][j-1]) 转移，同时 (i) 在剩下的 (r-j+1) 中使用了一次，但是使用的概率并不好算，正难则反，我们可以用 (1) 减去不使用的概率，所以 (f[i][j]+=f[i-1][j-1] imes (1-(1-p_i)^{r-j+1}))。
对于求 (P[i])，可以参照第二种情况的思考方式，所以：
[P[i]=sum_{j=1}^{r}{f[i-1][j] imes (1-(1-p_i)^{r-i})} ]考虑到复杂度可能比较大，需要预处理一下 (1-p_i) 的幂。
-
[x] CF16E Fish
概率状压DP（还是第一次见）
看到 (nle 18)，考虑状压。设 (f[S]) 表示状态 (S) 出现的概率，那么可以枚举一只在状态 (S) 中活着的鱼 (i) ，再枚举一只挂了的鱼 (j)，则有：
[f[S]=sum_{i}{sum_{j}{f[S|(1<<j-1)] imes a[i][j] imes P}} ]其中 (P) 表示上一轮 (i) 与 (j) 相遇的概率，即为 (frac{1}{frac{cnt imes(cnt-1)}{2}})（ (cnt) 为上一轮中活着的鱼的数量）。
边界状态为 (f[(1<<n)-1]=1)，注意从 ((1<<n)-1) 开始枚举。
-
[x] 六省联考2017 分手时祝愿
首先有一个巧妙的贪心思想：再计算最优方案时，我们可以从大到小枚举，只要碰到亮着的就关掉，因为关掉一个灯只能改变小于等于自己的灯的状态，所以我们枚举到的当前亮着的最大的灯是必须要关一次的，而枚举可以通过预处理因数达到 (nlog_2n)。
然后考虑DP。设 (f[i]) 表示从还必须操作 (i) 次到还必须需操作 (i-1) 次的期望操作次数，那么当 (ige k) 时，有 (frac{n-i}{n}) 的概率进行一次不必要的操作，即之后还需要花费一次操作来还原，那么可以得出转移方程：
[f[i]=frac{n-i}{n} imes(f[i]+f[i+1]+1)+frac{i}{n} imes 1 ]化简一下：
[f[i]=frac{1+(n-i) imes f[i+1]}{i} ]当然，当 (ile k) 时，(f[i]=1)。
-
[x] Cnoi2020 线性生物
对于图上随机游走的题目，有一种方法是利用期望的线性性，求出 (E(x ightarrow x+1)) 之后累加起来就可以得到从起点走到终点的期望花费。
本题中，令 (dx) 表示 (x) 的出度，不难发现：
[E(x ightarrow x+1)=frac{1}{dx}+frac{1}{du}sum_{(x,y)in E}{E(y ightarrow x+1)} ]用 (sum_{i=y}^{x}{E(i ightarrow i+1)}) 替换 (E(y)) 并化简可得：
[E(x ightarrow x+1)=frac{1}{dx}+frac{1}{du}sum_{(x,y)in E}{sum_{i=y}^{x} E(i ightarrow i+1)} \frac{1}{dx}E(x ightarrow x+1)=frac{1}{dx}+frac{1}{dx}sum_{(x,y)in E}sum_{i=y}^{x-1}{E(i ightarrow i+1)} \E(x ightarrow x+1)=dx+sum_{(x,y)in E}sum_{i=y}^{x-1}{E(i ightarrow i+1)} ]用 (sum[i]) 记录一下 (sum_{j=1}^{i}{f[j]})，上式即为：
[E(x ightarrow x+1)=dx+sum_{(x,y)in E}{sum[x-1]-sum[y-1]} ]可以 (O(n)) 求解。