#P11765. 「KFCOI Round #1」回首
「KFCOI Round #1」回首
题目背景
控制住不爱一个人很难,因为爱是自由意识的沉沦。
其实从始至终,只要你回首,他就永远都陪伴在你身后。
题目描述
你一共有 条重要的回忆,每条回忆有一个重要系数 ,并且这 条回忆彼此之间有 个前后关系。
每一条关系 表示 发生的时间恰好在 前。
可能是因为时间过久导致你的记忆错乱,在时间线中可能会出现环。
一开始,所有点的重要度均为 ,一共你会进行 次回想操作。
若当前正在进行第 次操作:
-
操作前,对于一条回忆 ,它的重要度会乘上重要系数 。
-
操作中,对于一条回忆 ,如果有恰好发生在回忆 前的回忆 ,那么将回忆 的重要度增加 在本次乘上重要系数 之前的重要度。否则回忆 的重要度增加 。
当然,为了防止一条回忆过于重要,输出每条回忆的重要度对 取余的结果。
形式化题意:
给定一个 个节点, 条边的有向图,并保证不会出现重边。初始所有点的点权都为 。
一共将进行 次操作。
对于第 次操作,首先将所有点的点权乘上一个给定的值 。
接下来,对于一个点 ,如果有连向它的点 ,那么将 的权值加上 在本次乘上 之前的权值。否则如果没有连向它的点, 的权值加上 。
输出的所有点的权值对 取余的结果。
输入格式
本题输入均为正整数。
第一行三个数 ,表示一共有 条回忆, 个关系,以及一共进行 次回想操作。
第二行 个数,表示重要系数 。
接下来 行,每行两个数 ,表示 发生的时间恰好先于 。
输出格式
输出共一行 个数,第 个数表示第 个点的重要度对 取余的结果。
5 5 3
1 2 3 4 5
1 2
2 3
1 4
2 4
4 5
6 5 1 8 1
提示
样例解释 1:
第一次操作时,所有的点重要度为 。
乘上重要系数后依旧为 。
第一个点的重要度加上当前正在进行的回想操作次数 。
其余点均加上 。
第一次操作后,所有点的重要度分别为 1,0,0,0,0
。
类似的,第二次操作后,所有点的重要度分别为 3,1,0,1,0
。
第三次操作后,所有点的重要度分别为 6,5,1,8,1
。
数据范围
本题采用捆绑测试。
- Subtask 1(20 points):,。
- Subtask 2(20 points):。
- Subtask 3(60 points):无特殊限制。
对于所有测试数据,,,,,。