#P11765. 「KFCOI Round #1」回首

    ID: 12987 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>洛谷原创O2优化矩阵加速矩阵乘法洛谷比赛

「KFCOI Round #1」回首

题目背景

控制住不爱一个人很难,因为爱是自由意识的沉沦。

其实从始至终,只要你回首,他就永远都陪伴在你身后。

题目描述

你一共有 nn 条重要的回忆,每条回忆有一个重要系数 kik_i,并且这 nn 条回忆彼此之间有 mm 个前后关系。

每一条关系 u,v(1u,vn)u,v(1\le u,v\le n) 表示 uu 发生的时间恰好vv 前。

可能是因为时间过久导致你的记忆错乱,在时间线中可能会出现环。

一开始,所有点的重要度均为 00,一共你会进行 TT 次回想操作。

若当前正在进行第 tt 次操作:

  • 操作前,对于一条回忆 xix_i,它的重要度会乘上重要系数 kik_i

  • 操作中,对于一条回忆 xix_i,如果有恰好发生在回忆 xix_i 前的回忆 yiy_i,那么将回忆 xix_i 的重要度增加 yiy_i 在本次乘上重要系数 kik_i 之前的重要度。否则回忆 xix_i 的重要度增加 tt

当然,为了防止一条回忆过于重要,输出每条回忆的重要度对 998244353998244353 取余的结果。


形式化题意:

给定一个 nn 个节点,mm 条边的有向图,并保证不会出现重边。初始所有点的点权都为 00

一共将进行 TT 次操作。

对于第 tt 次操作,首先将所有点的点权乘上一个给定的值 kik_i

接下来,对于一个点 xix_i,如果有连向它的点 yiy_i,那么将 xix_i 的权值加上 yiy_i 在本次乘上 kik_i 之前的权值。否则如果没有连向它的点,xix_i 的权值加上 tt

输出的所有点的权值对 998244353998244353 取余的结果。

输入格式

本题输入均为正整数。

第一行三个数 n,m,Tn,m,T,表示一共有 nn 条回忆,mm 个关系,以及一共进行 TT 次回想操作。

第二行 nn 个数,表示重要系数 kik_i

接下来 mm 行,每行两个数 xi,yix_i,y_i,表示 xix_i 发生的时间恰好先于 yiy_i

输出格式

输出共一行 nn 个数,第 ii 个数表示第 ii 个点的重要度对 998244353998244353 取余的结果。

5 5 3
1 2 3 4 5
1 2
2 3
1 4
2 4
4 5
6 5 1 8 1

提示

样例解释 1:

第一次操作时,所有的点重要度为 00

乘上重要系数后依旧为 00

第一个点的重要度加上当前正在进行的回想操作次数 11

其余点均加上 00

第一次操作后,所有点的重要度分别为 1,0,0,0,0

类似的,第二次操作后,所有点的重要度分别为 3,1,0,1,0

第三次操作后,所有点的重要度分别为 6,5,1,8,1


数据范围

本题采用捆绑测试

  • Subtask 1(20 points):1n101\le n \le 101T101\le T \le 10
  • Subtask 2(20 points):1T1051\le T\le 10^5
  • Subtask 3(60 points):无特殊限制。

对于所有测试数据,1n1001\le n\le1001m3001\le m\le3001T10181\le T\le10^{18}1ki1091\le k_i\le10^91xi,yin1\le x_i,y_i\le n