关于 bib_ibi,可以在拓扑排序访问到时直接乘上,表示在这里停留带来的额外代价。
不考虑回到 111 的限制,对于每条路径,回到 111 相当于给整条路径乘上一个权值作为新的期望值。
正图不好做,考虑建立反图。令 cic_ici 表示 iii 的出边走到每个点的概率,可以快速求出。
令 fif_ifi 表示 i→ni\to ni→n 的期望回滚次数。gig_igi 表示 i→ni\to ni→n 的期望步数。
拓扑排序即可。
注册一个 CZOJ 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 CZOJ 通用账户