题解

思路

把每个数值看成会沿有向边传播的单位。图是 DAG 且只有一个汇点，所以每个点都能到达汇点。经过 $n$ 秒后，若仍有剩余数值，汇点之后会一直工作到全部清空，不再出现空档。

设 $ways_u$ 是从 $u$ 到唯一汇点的路径数。在模 $998244353$ 意义下，当前位于 $u$ 的一个剩余单位最终会使汇点多工作 $ways_u$ 秒。

做法

子任务 1 直接按秒模拟，直到所有数值为零。

子任务 2 中每个点到汇点只有一条路，因此模拟至多 $n$ 秒后，剩余时间就是 $\sum a_i$。

满分做法先模拟至多 $n$ 秒；若已清空则直接输出。否则按逆拓扑序计算

汇点的 $ways$ 为 $1$。答案是已模拟的 $n$ 秒加上 $\sum a_uways_u$。

复杂度

满分算法时间复杂度 $O(n(n+m))$，空间复杂度 $O(n+m)$。