1 条题解

  • -1
    @ 2024-6-1 11:23:37

    关于 bib_i,可以在拓扑排序访问到时直接乘上,表示在这里停留带来的额外代价。

    不考虑回到 11 的限制,对于每条路径,回到 11 相当于给整条路径乘上一个权值作为新的期望值。

    正图不好做,考虑建立反图。令 cic_i 表示 ii 的出边走到每个点的概率,可以快速求出。

    fif_i 表示 ini\to n 的期望回滚次数。gig_i 表示 ini\to n 的期望步数。

    拓扑排序即可。

    信息

    ID
    913
    时间
    2500ms
    内存
    512MiB
    难度
    10
    标签
    (无)
    递交数
    3
    已通过
    1
    上传者