4316

原题链接 前情提要，如果对期望的概念不清晰，请点击这里 我犯的错误：因为每条路只走一遍，而错误地判断每条路的概率相同 题解 1.对于任何一个节点来说，设其出边有\(len\)条，其子节点的期望长度为\(sum[j]\) 则该节点的期望长度为\(\frac{\sum sum[j]}{len}\),根据 ......

原题链接：https://www.luogu.com.cn/problem/P4316 这题是经典的概率dp题，通常看到的题解都是逆推的做法，实际上理解了题目的含义后发现逆推其实是正推的一种特殊情况而已 正推做法： 定义dp[i]表示从1~i的路径长度的期望，那么dp[1] = 0，答案就是dp[n ......

[原题](https://www.luogu.com.cn/problem/P4316) 这篇帖子主要解释为什么正推和倒推有区别，如果想询问做法，请移步至[洛谷题解区](https://www.luogu.com.cn/problem/solution/P4316) 倒推：$dp_i$表示从$i \ ......

题目描述 给出张 n 个点 m 条边的有向无环图，起点为 11，终点为 n，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。 绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 k 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 1/k。现在 ......