P6154 游走
原题
期望题通常有两种解决方案：
-
直接递推期望的答案
-
用总的答案/总的方案数
本人就在这道题上有第一种方案卡了很长时间，最后才发现用第二种方案解决很简单
下面直接说解法
首先\(E(x) = \frac{sum}{cnt}\)，其中\(sum\)为总的路径长度之和，\(cnt\)为总的路径个数
因此我们对这两个东西分开\(dp\)，设\(f_i\)表示从\(i\)开始的路径长度之和，\(cnt\)为从\(i\)开始的路径个数
容易想到递推式：
\[\begin{align}
f_u &= \sum_{(u,v) \in E}{ f_v + g_v } \\
g_u &= \sum_{(u,v) \in E}{ g_v } + 1 \\
\end{align}
\]
直接递推即可，最终答案为\(\frac{\sum{f_i}}{\sum{g_i}}\)，总复杂度\(O(n)\)
\(dp\)的状态也可以设成到\(x\)结束的路径个数，转移类似，答案类似