萌新求助简单期望

学术版

PrincessQi @ 2022-12-29 19:52:04

给定一个 n 个点 m 条边的有向图，每个点在每一天都有 p 的几率产生病毒；且若一个点 u 感染了病毒，则接下来每一天病毒都有可能通过图上的边传染给相邻的点 v，概率为边权 w。求每个点期望感染病毒的天数。答案向 998244353 取模。

by PrincessQi @ 2022-12-29 19:53:09

不取模很好做，直接一个点经过很多天还没感染的概率忽略不计即可

by WZKQWQ @ 2022-12-29 19:54:24

@PrincessQi 数据范围？

by lsj2009 @ 2022-12-29 19:54:27

草，这不是我下午想到的题吗

by PrincessQi @ 2022-12-29 19:55:25

@lsj2009 就是我们从你那搞到了题，然后有几个人讨论了很久，发现不会才问的

by PrincessQi @ 2022-12-29 19:55:49

@WZKQWQ 数据范围不知道，能做多少算多少

by gapeqi @ 2022-12-29 19:57:16

如果 n 巨小是可以做的，20？

剩下的不会。。。。。。

by lsj2009 @ 2022-12-29 19:57:17

有结果了踹我一脚

by gapeqi @ 2022-12-29 19:57:55

@lsj2009 Cu

by gapeqi @ 2022-12-29 20:00:40

我敲打了发现 DAG 似乎可做？不知道有没有神仙撕烤。

by poly @ 2022-12-29 20:03:00

盲猜需要解方程。

| 下一页